题目传送门

A 多项式输出

B 潜伏者

C 细胞分裂

D 道路游戏

T1多项式输出

思路

这道题虽然体面很复杂，但是在看懂后很好理解如下

1. 位置为i的数，次幂是n-i+1;$( 0 \le i \le n )$,也可以i从后往前直接枚次幂
2. 系数等于0跳过
3. 系数小于0存负号
4. 系数大于0且不是第一个，存加号
5. 系数绝对值不等于1，存下系数绝对值
6. 次幂>1存 x^ 次幂
7. 次幂=1存x
8. 次幂=0且系数绝对值为1存1
9. 输出

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
	freopen("poly.in","r",stdin);
	freopen("poly.out","w",stdout);
	cin>>n;
	m=n;
	n++;
	string k;
	while(n--){
		int d;
		cin>>d;
		if(d==0)continue;
		if(d<0)k+='-';
		else if(d>0&&n!=m)k+='+';
		if(abs(d)!=1)k+=to_string(abs(d));
		if(n>1)k=k+"x^"+to_string(n);
		if(n==1)k+='x';
		if(n==0&&abs(d)==1)k+='1';
	}
	cout<<k;
	return 0;	
}

错误与感想

我在写的时候，读了一会半小时题才看懂，然后写代码时，脑子里一片乱麻，只拿了一点分。

错误主要原因还是因为思路不清晰，要多打草稿，把情况列出来，正确几率才大

注：此题为字符串处理

T2潜伏者

思路

这里我们可以建立映射数组,如下

$$s1 = ABCA$$ $$s2 = CABD$$ $$mp1[s1[i]] = s2 s1 ==> s2的映射$$ $$mp2[s2[i]] = s1 s2 ==> s1的映射$$

如果重复映射且映射值不相等，输出Failed

如果映射个数小于26，输出Failed（在映射时操作）

然后我们通过映射数组逐个替换，最后输出

代码

#include<bits/stdc++.h>
using namespace std;
char m1[1000],m2[1000],st[1000],c;
string m,y,h;
int main(){
	freopen("spy.in","r",stdin);
	freopen("spy.out","w",stdout);
	memset(m1,'*',sizeof m1);
	memset(m2,'*',sizeof m2);
	cin>>m>>y>>h;
	for(int i=0;i<m.size();i++){
		if(m1[m[i]]=='*'){
			m1[m[i]]=y[i];
			c++;
		}
		else if(m1[m[i]]!=y[i]){
			cout<<"Failed";
			return 0;
		}
	}
	for(int i=0;i<y.size();i++){
		if(m2[y[i]]=='*')m2[y[i]]=m[i];
		else if(m2[y[i]]!=m[i]){
			cout<<"Failed";
			return 0;
		}
	}
	if(c<26){cout<<"Failed";return 0;}
	for(int i=0;i<h.size();i++)cout<<m1[h[i]];
}

错误与感想

这道题思路还是想到了，但写的很复杂，最后WA成功gg,然后还自以为是的加了个判断，又丢了10分，得不偿失

以后做题要尽量把思路想简单点，避免冤屈gg丢分，也要想一些方能满足代码不同部分功能要求，就可以不被代码长找错难而满江红WA 注：此题为字符串处理

T3细胞分裂

思路

题意很简单，就是求$s_i^{k} | m1^{m2}$最小的k 如果$A^x|B$那么A有B的所有制因子，比如120|20

$$120:\ 2 \ 2 \ 2 \ 3 \ 5$$ $$20: \ 2 \ 2 \ 5$$

所以120可以整除20

1. m1质因数分解，求出每个质因数 j 的个数，记作 f[j]，注：除时要加 m2
2. $s_i^k∣m1^m2$ 成立，则 $s_i$ 的每个质因子的指数都大于 m1 对应质因子的指数，即需要求得一个k 使得所有的 质因子j 都有 s[j] >= f[j]，其中 s[j] 表示 s_i 的j质因子个数， f[j] 表示 m1 的 j 质因子个数。所以有：k = max((f[j]+s[j]-1) / s[j], k) 注：此为向上取整
3. $s_i$ 的 k，求最小值

代码

#include<bits/stdc++.h>
using namespace std;
unordered_map<long long,long long>s;
long long n,m1,m2,x,c=0,cc,mi=(long long)(5e18),m3,bf;
long long g(long long x){
	long long mii=0;
	cc=c,bf=x;
	for(auto it:s){
		long long i=it.first,z=it.second,c=0;
		if(x%i==0){
			cc--;
			while(x%i==0)c++,x/=i;
			if(c<s[i])mii=max(mii,(s[i]+c-1)/c);
		}
	}
	if(cc!=0)return (long long)(5e18);
	return mii;
}
int main(){
	freopen("cell.in","r",stdin);
	freopen("cell.out","w",stdout);
	cin>>n>>m1>>m2;
	m3=m1;
	for(long long i=2;i<=m1/i;i++){
		if(m3%i==0){
			c++;
			while(m3%i==0)s[i]+=m2,m3/=i;
		}
	}
	if(m3!=1)s[m3]+=m2,c++;
	for(long long i=1;i<=n;i++){
		cin>>x;
		mi=min(mi,g(x));
	}
	if(mi==(long long)(5e18))cout<<-1;
	else cout<<mi;
}

错误与感想

这道题只骗分了一下，没认真思考在摆烂所以导致才错失良机想到数学了，可想的是gcd,不是正解的分解质因数

以后不能空题不写，，要多思考一下，可能会有新的方法，如果在比赛结尾实在想不到了，那就暴力一下，骗分，分数也会高起来的

注：此题为数学题

T4 道路游戏

思路

这是一道经典的DP题

f[i]表示第 i 时刻能够收集的最大金币数 cost[i]表示从第i个点购买机器人的花费

状态转移： f[i] = max(f[i-k] + sum - cost[i-k+1] sum表示从 i - k 走过来搜集的金币总数 第 i 时刻的最大值 = max(i-k时刻的最大值 + 走过来收集的金币 - 买机器人金币) 注：在逆时针回溯时（走过来时），碰到环要特判，还有sum有两种写法，一种斜缀合，麻烦，，但我们可以枚举一步加一步的值

代码

#include<bits/stdc++.h>
using namespace std;
int l[1111][1111],f[1111],z[1111],n,m,p;
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	memset(f,-2e9,sizeof f);
	f[0]=0;
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>l[i][j];
	for(int i=1;i<=n;i++)cin>>z[i];
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			int sum=0;
			for(int b=1;b<=i&&b<=p;b++){
				int w;
				if(j-b<=0)w=(j-b)%n+n;
				else w=j-b;
				sum+=l[w][i-b+1];
				f[i]=max(f[i],f[i-b]+sum-z[w]);
			}
		}
	}
	cout<<f[m];	
}

错误与感想

在写的时候，这道题我没做，感觉太难，没有希但如果在想一下，就会发现思路还简单，只要认真的去做，就可以做出来

以后的话，在其他题被攻克完后，就可以去写一写，DP本质就是暴力的优化，还是可以被攻克的，不要觉得DP难，要努力