铁大第5届程序设计竞赛题解

Posted:   December 21, 2021

Status:   Completed

Tags :   算法 校赛

Categories :   题解

Were equations, pictures or diagrams not properly rendered, please refresh the page. If the problem persists, you can contact me.

石家庄铁道大学第五届程序设计竞赛题解

本次校赛出题人有7个，每人2道（一道中文，一道英文），总共14道，题目中间更正了一些小问题，对大家造成的不便深感抱歉

A-SOUL Eileen Fan F

题意：

第1行输入一个字符串，代表每一位加法运算所遵循的进制表规则，第2,3行输入两个运算数，按照进制表规则输出运算结果

思路：

先把2个字符串都在开头补0，使其等长，然后把这2个数加起来，之后进制转换，最后注意输出格式就可以了

#include <bits/stdc++.h>
using namespace std;
int main(){
    string a,b,c;
    cin>>c>>a>>b;
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    reverse(c.begin(),c.end());
    string s;

    int up=0,sum,k;
    while(a.length()!=b.length()){
        if(a.length()>b.length())
            b += '0';
        else
            a += '0';
    }
    for(int i=0;i<a.length();i++){
        sum = a[i]-'0'+b[i]-'0'+up;
        if(i>c.length()-1 || c[i]=='0')
            k=10;
        else
            k=c[i]-'0';
        up = sum/k;
        sum %= k;
        s = (char)(sum + '0') + s;
    }
    if(up > 0)
        s = (char)(up + '0') + s;
    int count = 0;
    while(s[count] == '0' && s.length() > 1)
        s.erase(count, 1);
    cout<<s<<endl;
    return 0;

}

打牌

思路：

每个人都可以拿（给自己加分）或者禁（不让对分加禁了的数字的分），所以是拿还是禁就是看能拿的选择和能禁的选择中谁的贡献大（就是面值大），确定了操作方式就可以模拟了

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        ll diff = 0,n;
        cin >> n;
        ll arr[200005];
        for(ll i = 0; i < n; i++){
            cin >> arr[i];
        }
        sort(arr,arr + n);
        for(ll i = n - 1; i >= 1; i -= 2){
            ll a = 0,b = 0;
            if(arr[i] % 2 == 0)
                a = arr[i];
            if(arr[i - 1] % 2 != 0)
                b = arr[i - 1];
            diff = diff + a - b;
        }
        if(n % 2 == 1)
            if(arr[0] % 2 == 0)
                diff += arr[0];
        if(diff > 0)
            cout << "T" << endl;
        else if(diff < 0)
            cout << "X" << endl;
        else cout << "Tie" << endl;
    }
    return 0;
}

BJS and HT

题意：

一共有N组条件，每一组有2个字符串（B和H），若H可以由B截取其中K个连续字符并放到最前面得到，那么这组就可以匹配成功，问这N组中有几组可以匹配成功

思路:

考点：字符串哈希

  • 直接使用unsigned long long储存Hash值，计算时不处理算术溢出问题(产生溢出时相当于自动对2^64^取模，这样可以避免低效的mod运算)，且一般取哈希进制数P为131或13331
  • 区间$[l,r]$的字符串哈希值公式为：$(H[r]-H[l]*P^{r-l+1}+M)mod\,M$
  • 在 $B$ 串中找连续的 $K$ 个字符，和 $H$ 串前 $K$ 个字符匹配上，之后检验其余部分是否能匹配上即可，最终复杂度为$O(n)$，其中 $n$ 为字符串总长度

代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=5e5+10;
int t,k,n;
ll ha[N],hb[N],po[N];
char a[N],b[N];
ll hasha(int l,int r){
	l--;
	return ha[r]-ha[l]*po[r-l];
}
ll hashb(int l,int r){
	l--;
	return hb[r]-hb[l]*po[r-l];
}
int cnt=0;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%s%s%d",a+1,b+1,&k);
		int n=strlen(a+1);
		
		if(strlen(b+1)!=n || k>n){
			continue;
		}
		
		po[0]=1;
	    for(int i=1;i<=n;i++)
			ha[i]=131*ha[i-1]+a[i],  
        	hb[i]=131*hb[i-1]+b[i],   
        	po[i]=po[i-1]*131;
			
	    ll val=hashb(1,k);//H最前面一段
	    
	    bool flag=0;
        
	    //枚举截取B的左端点i
	    for(int i=1;i+k-1<=n;i++)
	    	if(hasha(i,i+k-1)==val)
                //其他部分匹配上
	    	    if(hasha(1,i-1)==hashb(k+1,k+i-1) && hasha(i+k,n)==hashb(i+k,n)) 
                    flag=1;
	    	    
	    if(flag) {
	    	cnt++;
	    }
	}
	cout<<cnt<<endl;
	return 0;
}

F爱玩炉石传说

思路:

也是签到题，认真想一下，从1到n检查有没有空缺就可以了

#include <iostream>
using namespace std;

bool a[1000000];
int n;
int main() {
	cin >> n;
	int t;
	bool flag = 0;
	int k = 0;
	for (int i = 0; i < n; i++) {
		cin >> t;
		//cout<<t;
		if (!a[t]) {
			a[t] = 1;
			k++;
		}
	}
	for (int i = 1; i <= k; i++)
		if (!a[i]) {
			flag = 1;
			break;
		}
	if (flag)
		cout << "Nevermind, just use the Twisting Nether." << endl;
	else
		cout << "This is a textbook-like blasphemy!" << endl;

}

A+B Problem

思路:

每个测试样例不超过 $10$ 组测试数据，实现实数长度 $len$ 不超过 $10^4$ 的大实数加法，注意是否输出小数点，省略无意义的0。时间复杂度 $O(10*len)$。

#include <iostream>
#include <algorithm>
#include <cstring>
#define pb push_back
using namespace std;

int main(){
	string a,b;
	while(cin>>a>>b){
		//补0和小数点
		int posa=-1,posb=-1;
		for(int i=0;i<a.size();i++){
			if(a[i]=='.'){
				posa=i;
				break;
			}
		}
		for(int i=0;i<b.size();i++){
			if(b[i]=='.'){
				posb=i;
				break;
			}
		}
		if(posa==-1){
			a.pb('.');
			a.pb('0');
		}
		else if(posb==-1){
			b.pb('.');
			b.pb('0');
		}
		
		if(a.size()<b.size()){
			swap(a,b);	
		}
		//看小数点的位置 
		posa=posb=0;
		for(int i=0;i<a.size();i++){
			if(a[i]=='.'){
				break;
			}
			posa++;
		}
		for(int i=0;i<b.size();i++){
			if(b[i]=='.'){
				break;
			}
			posb++;
		}
		if(posa<posb){
			string tem="";
			for(int i=0;i<posb-posa;i++){
				tem.pb('0');
			}
			tem+=a;
			a=tem;
		}
		else{
			string tem="";
			for(int i=0;i<posa-posb;i++){
				tem.pb('0');
			}
			tem+=b;
			b=tem;
		}
		
		int d=a.size()-b.size();
		for(int i=0;i<d;i++){
			b.push_back('0');
		}
		int x=a.size(),y=b.size();
		if(a.size()<b.size()){
			for(int i=0;i<(y-x);i++){
				a.pb('0');
			}
		}
		
		reverse(a.begin(),a.end());
		reverse(b.begin(),b.end());
		
		string ans="";
		int up=0;
		for(int i=0;i<a.size();i++){
			if(a[i]=='.'){
				ans.pb('.');
				continue;
			}
			ans.pb((a[i]-'0'+b[i]-'0'+up)%10+48);
			up=(up+a[i]-'0'+b[i]-'0')/10;
		}
		if(up){
			ans.pb(up+48);
		}
		reverse(ans.begin(),ans.end());
		
		int pos=-1;
		for(int i=0;i<ans.size();i++){
			if(ans[i]=='.'){
				pos=i;
				break;
			}
		}
		
		//去除后导零 
		bool flag=1;
		for(int i=pos+1;i<ans.size();i++){
			if(ans[i]!='0'){
				flag=0;
				break;
			}
		}
		if(flag){//全是0 
			for(int i=0;i<pos;i++){
				cout<<ans[i];
			}
			cout<<endl;
		}
		else{
			int len=ans.size();
			for(int i=ans.size()-1;i>=0;i--){
				if(ans[i]=='0'){
					len--;
				}
				else{
					break;
				}
			}
			for(int i=0;i<len;i++){
				cout<<ans[i];
			}
			cout<<endl;
		}
	}
	return 0;
}

懒虫读诗

思路:

考点：背包DP，树形 DP

我们可以抽象为有根树中一个点最多只有一个父亲结点，这是一个森林，方便起见，我们可以新增一篇开心度为 $0$ 的文章（设这篇文章的开心度为 $0$ ），作为所有无先导诗文篇章的先导诗文，这样我们就将森林变成了一棵以 $0$ 号诗文为根的树，而且恰好满足题意输入

设$f(i,u,j)$表示以 $i$ 号点为根的子树中，已经遍历了 $i$ 号点的前 $u$ 棵子树，选了 $j$ 篇文章的当前累计最大开心值之和，转移的过程中，我们枚举 $i$ 点的每个子结点 $v$，同时枚举以 $v$ 为根的子树选的文章数（设为 $k$ ），将子树的结果合并到 $i$ 上，另外，设以 $v$ 为根的子树大小为$size_v$，点 $v$ 的儿子个数为 $s_{v}$ ，有状态转移方程：

\[f(i,u,j)=\max _{k<size_v}f(i,u-1,j-k)+f(v,s_{v},k)\]

$f$ 的第二维可以用滚动数组的方式省略掉，这时设$f(i,j)$为在 $i$ 及 $i$ 以下的子树上选 $j$ 篇文章（范围在 $1$ 至 $m+1$ ）所能得到的当前累计最大开心值之和，注意这时需要倒序枚举 $j$ 的值，对于 $k$ ，从 $0$ 至 $j-1$ 枚举就好了，而且我们可以证明，该做法的时间复杂度为$O(nm)$

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=300+10;
int f[N][N];
vector<int> table[N];
int n,m;

void dp(int a){
	for(auto i : table[a]){
		dp(i);
        //类似背包
		for (int j=m+1;j>=1;j--)
			for(int k=0;k<j;k++)
				f[a][j]=max(f[a][j],f[a][j-k]+f[i][k]);
	}
}
int main(){
	cin>>n>>m;
	int ki=0;
	for(int i=1;i<=n;i++){
		cin >> ki >> f[i][1];
		table[ki].push_back(i);
	}

	dp(0);
	cout<<f[0][m+1];
}

A Hard Calculation Problem

思路：

签到题，直接输出对应校赛的举办时间即可

代码：

#include <bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define f(i,a,n) for(int i=a;i<n;++i)
#define ff(i,a,n) for(int i=a;i<=n;++i)
const int INF=0x3f3f3f3f;
using namespace std;
typedef long long ll;
typedef double dbl;
typedef pair<int, int> pi;
int t;
int q=2021-5;
int main(){
	cin>>t;
	int x;
	while(t--){
		cin>>x;
		cout<<x+q<<endl;
	}
    return 0;
}

水果蛋糕

思路：

本题所需解决的问题有3个：

  1. 计算蛋糕的大小：观察题目，我们可以知道蛋糕的宽都是相同的，因此判断每块蛋糕的面积的大小只需要判断蛋糕上下底边的和的大小即可
  2. 统计每块蛋糕上水果的个数：枚举每个水果的坐标，使用二分查找（通过向量的叉积判断水果在断口的左边还是右边）水果左边最右边的断口（或右边最左边的断口），统计每个断口被查找的次数即可求出每块蛋糕上水果的次数（蛋糕边缘的切割点的坐标可以利用前缀和求出）
  3. 找出所求蛋糕：可以通过记录当前最优解查找，也可使用结构体排序后直接选出

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
double us[10000020],ds[10000020];
double u[10000020],d[10000020];
int cnt[5000010];
double cj(double x1,double y1,double x2,double y2){
	return x1*y2-x2*y1;
}
double pd(double x1,double y1,double x2,double y2,double x3,double y3){
	return cj(x2-x1,y2-y1,x3-x1,y3-y1);
}
struct Cake{
	int cnt,sqr,num;
}c[10000020];

bool cmp(struct Cake a,struct Cake b){
	if(a.cnt != b.cnt )return a.cnt > b.cnt ;
	else if(a.sqr!=b.sqr )return a.sqr >b.sqr ;
	else return a.num<b.num;
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	int xx,yy;
	scanf("%d %d",&xx,&yy);
	for(int i=1;i<=n;i++){
		scanf("%lf %lf",&us[i],&ds[i]);
		u[i]=u[i-1]+us[i];
		d[i]=d[i-1]+ds[i];
		c[i].sqr=us[i]+ds[i];
		c[i].num=i;
	}
	c[n+1].sqr=xx-u[n]+xx-d[n]; 
	c[n+1].num=n+1; 
	for(int i=0;i<m;i++){
		double x,y;
		scanf("%lf %lf",&x,&y);
		int l=1,r=n+1;
		while(l!=r){
			int mid=(l+r)/2;
			if(pd(u[mid],yy,d[mid],0,x,y)>0){
				l=mid+1;
			}else{
				r=mid;
			}
		}
		c[l].cnt++;
	}
	sort(c+1,c+n+2,cmp);
	printf("%d",c[1].num);
}

Digital Logic and Bit Operation

题意：

找到[l,r]中的x、y，使得x y最大。

思路：

二分+位运算

给l的二进制补1，只要没超过r就一直补，最后得到的数和r或运算就是结果。

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

int main(){
    ll ans;
    ll l,r;
    int t;
    cin >> t;
    while(t--){
        cin >> l >> r;
        ll now = 0;
        while((l|(ll)1 << now) < r){
            l |= ((ll)1 << now);
            now++;
        }
        cout << (l|r) << endl;
    }
}

蛋糕惨案

思路：

本题所需解决的问题有2个：

  1. 快速的求出范围内的所有质数：很明显使用定义来判断质数的总时间复杂度为$O(n\sqrt n)$，而本题的数据范围在1e7，肯定会超时，接下来采用埃氏筛，其效率是$O(nlglgn)$，虽然已经很快了，但是在残暴数据1e7面前仍会超时，最后便是本题的正解：欧拉筛（线性筛）正如名字那样，他的时间复杂度为$O(n)$，在利用线性筛打好表后，我们只需要枚举每个数，判断他们是否是素数，如果是则把他们存在一个数组中
  2. 对数组进行排序：大概有$\dfrac{n}{ln(n)}$个素数，最后我们直接进行排序就好（排序使用时间复杂度不超过$O(nlgn)$即可）

代码：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
bool cmp(int a,int b){
	return a<b;
}
int primes[10000010], cnt;
bool st[10000010];
int s[10000010];
int main(){
	st[1]=1;
    for (int i = 2; i <= 1e7; i ++ ){
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= 1e7; j += i)
            st[j] = true;
    }
	int n;
	scanf("%d",&n);
	
	int top=0;
	for(int i=0;i<n;i++){
		int now;
		scanf("%d",&now);
		if(st[now]==0){
			s[top++]=now;
		}
	}
	sort(s,s+top,cmp);
	printf("%d\n",top);
	if(top==0)printf("-1");
	else {
		for(int i=0;i<top;i++){
			printf("%d ",s[i]);
		}
	}
}

Equation

题意：

输入y，找出输入后函数在0-100上的最小值

思路：

算法：二分法求解

给原方程求导之后运用二分法求解。

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define ll long long

double fx(double x,double y){
    return 6 * pow(x,7) + 8 * pow(x,6) + 7 * x*x*x + 5 * x*x - y * x;
}

double gx(double x,double y){
    return 42 * pow(x,6) + 48 * x*x*x*x*x + 21 * x*x + 10 * x - y;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        double y;
        cin >> y;
        if(gx(100,y) <= 0){
            cout << fx(100,y) << endl;
            continue;
        }
        else{
            double low = 0,high = 100,mid;
            while(high - low > 0.00001){
                mid = (high + low)/2;
                if(gx(mid,y) >= 0) high = mid;
                else low = mid;
            }
            printf("%.4lf\n",fx(mid,y));
        }
    }
    return 0;
}

树上宝藏

思路：

给定一颗 $n \leq 10^5$ 的无根树 ($a!=b$，保证无环)，注意到 $1 \leq m \leq 10^2$ ，题目要求 $O(m)$ 次树上修改，$O(m)$ 次树上询问。因此使用邻接表建图之后，对每次修改和查询暴力 $dfs$ 求解即可，注意开 $long long $，时间复杂度$O(n*m)。$

#include<iostream>
#include<cstring>
using namespace  std;
typedef long long ll;
const int N=1e5+10;

int h[N],e[N*2],ne[N*2],idx;
ll w[N],ans;
int n,m;

void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool flag=0;
void dfs(int u,int fa,int v,ll d){
	if(u==v){
		w[v]+=d;
		flag=1;
		return ;
	}
	w[u]+=d;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa)continue;
		dfs(j,u,v,d);
		if(flag)return ;
	}
	w[u]-=d;
}

void dfs_1(int u,int fa,int v,int res){
	if(u==v){
		res+=w[u];
		ans=res;
		return ;
	}
	res+=w[u];
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa)continue;
		dfs_1(j,u,v,res);
	}
	res-=w[u];
	return ;
}

int main(){
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	for(int i=0;i<n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);add(b,a);
	}
	for(int i=0;i<m;i++){
		int u,v;cin>>u>>v;
		ll d;cin>>d;
		flag=0;
		dfs(u,-1,v,d);
	}
	for(int i=0;i<m;i++){
		int u,v;cin>>u>>v;
		ans=0;
		dfs_1(u,-1,v,0);
		cout<<ans<<endl;
	}
	return 0;
}

Rescue Hostage

思路：

题目要求两个人到达同一地点所需时间最少，所以可以对每个人分别bfs一下，找到之和最小的那个点即可

#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int N = 1010;
int ansa[205][205];
int ansb[205][205];
char s[205][205];
const int dx[4] = { 1,-1,0,0 };
const int dy[4] = { 0,0,1,-1 };
int xy, yy, xm, ym;
int n, m;
struct node{
	int x, y;
};
int lans = 10010;
bool judge(int x0, int y0, int ans[205][205]){
	if (x0 < 0 || x0 >= n || y0 < 0 || y0 >= m)
		return false;
	if (ans[x0][y0])
		return false;
	if (s[x0][y0] == '#')
		return false;
	else
		return true;
}
void bfs(int x, int y, int ans[205][205]){
	queue<node> q;
	node p1;
	p1.x = x;
	p1.y = y;
	ans[x][y] = 0;
	q.push(p1);
	while (!q.empty()){
		node p2;
		p2 = q.front();
		q.pop();
		for (int i = 0; i < 4; i++){
			p1.x = p2.x + dx[i];
			p1.y = p2.y + dy[i];
			if (judge(p1.x, p1.y, ans)){
				ans[p1.x][p1.y] = ans[p2.x][p2.y] + 1;
				q.push(p1);
			}
		}
	}
}
int main(){
	cin >> n >> m;
		lans = 10010;
		memset(ansa, 0, sizeof(ansa));
		memset(ansb, 0, sizeof(ansb));
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++){
				cin >> s[i][j];
				if (s[i][j] == 'F'){
					xy = i;
					yy = j;
				}
				else if (s[i][j] == 'X'){
					xm = i;
					ym = j;
				}
			}
		}
		bfs(xy, yy, ansa);
		bfs(xm, ym, ansb);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++){
				if (s[i][j] == 'H' && ansa[i][j] != 0){
					int temp = ansa[i][j] + ansb[i][j];
					lans = min(lans, temp);
				}
			}
		cout << lans << endl;
}

嘉然的问题

思路：

签到题，为啥都不做捏QAQ，直接枚举所有的子串，然后判断是否回文就好了，因为输入字符串中间可能会有空格，所以输入方式推荐用getline

代码：

#include<bits/stdc++.h>
using namespace std;
string s;
void judge(int pos,int len){
	string s1=s.substr(pos,len);
	string s2=s1;
	reverse(s1.begin(),s1.end());
	if(s1==s2)cout<<s1<<endl;
}
int main(){
    getline(cin,s);
    int l=s.length();
    for(int i=2;i<=l;i++)
		for(int j=0;j+i<=l;j++)
			judge(j,i);
			
    return 0;
}

Comments

Be the first one to comment on this page!
You can use extended GitHub flavored markdown in your comment. Commenting FAQs & Guidelines