A. 多项式输出

题目类型：分类讨论

思路

按照题意直接分类讨论即可，我们可以分为以下几种情况来讨论：

• 全为1以上。
• 包含0，1。
• 包含负数。
• 第一项为负数。
• 常数项为零。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int a[N];
int main(){
	freopen("poly.in","r",stdin);
	freopen("poly.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]!=0&&i!=n+1){
			if(i!=1&&a[i]>0) cout<<"+";
			if(a[i]==-1) cout<<"-";
			if(a[i]!=1&&a[i]!=-1) cout<<a[i];
			cout<<"x";
			if(i!=n) cout<<"^"<<n-(i-1);
		}
	}
	int b;
	cin>>b;
	if(b!=0){
		if(b>0&&n>0) cout<<"+";
		cout<<b; 
	}
	return 0;
}

这道题目我在写的时候忘写一些情况了，所以WA了，下次一定要看清题目。

B. 潜伏者

题目类型：字符串

思路

对于这道题目我们可以用两个数组来分别记录两个字符串中A~Z出现的次数，再用一个字符串来记录密文，再来根据题意来写即可。

代码

#include<bits/stdc++.h>
using namespace std;
int d[30],e[30];
char zm[30];
int main(){
	freopen("spy.in","r",stdin);
	freopen("spy.out","w",stdout);
	string a,b,c;
	cin>>a;
	cin>>b;
	cin>>c;
	bool flag=1;
	for(int i=0;i<a.size();i++){
		d[a[i]-'A']++;
		e[b[i]-'A']++;
		if(d[a[i]-'A']>1) if(b[i]!=zm[a[i]-'A']) flag=0;
		zm[a[i]-'A']=b[i];
	}
	for(int i=0;i<26;i++) if(d[i]==0||e[i]==0) flag=0;
	if(flag==0) cout<<"Failed";
	else for(int i=0;i<c.size();i++) cout<<zm[c[i]-'A'];
	return 0;
}

本题代码已AC，下一次继续保持。

C. 细胞分裂

题目类型：数学

思路

对于这道题目，我们可以想到：若b是a的倍数，那a的质因数b也有，那么只要一个数组中的数，是另一个数组的倍数，那么就输出所有合法情况的中的最大值，否则输出-1，那么我们可以先求出m1中的质因数与种数，再来判断a[i]是否能把质因数整除，如果可以，就按之前的方法输出所有合法情况的中的最大值，否则的话就continue继续遍历，若最后都没有合法的，就输出-1。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10,M=1e4+10;
int a[M],cnt_1[N],cnt_2[N],n,m1,m2;
vector<int> p;
void init(){
	for(int i=2;i<=m1;i++){
		if(m1%i==0) p.push_back(i); 
		while(m1%i==0) m1/=i,cnt_1[i]++;
		cnt_1[i]*=m2;
	}
}
bool check(int x){
	memset(cnt_2,0,sizeof cnt_2);
	for(int i=0;i<p.size();i++){
		if(x%p[i]) return 0;
		while(x%p[i]==0) x/=p[i],cnt_2[p[i]]++;
	}
	return 1;
}
int main(){
	freopen("cell.in","r",stdin);
	freopen("cell.out","w",stdout);
	cin>>n>>m1>>m2;
    init();
    int mn=2e9;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	    if(!check(a[i])) continue;
	    int mx=0;
	    for(int j=0;j<p.size();j++) mx=max(mx,(cnt_1[p[j]]+cnt_2[p[j]]-1)/cnt_2[p[j]]);
		mn=min(mn,mx);
	}  
	if(mn==2e9) cout<<-1;
	else cout<<mn; 
	return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。

D. 道路游戏

题目类型：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时刻的最大值 + 走过来收集的金币 - 买机器人金币)。

注意：机器人购买花费是最后来结算，所以不需要考虑是否买的起的问题。

代码

#include<bits/stdc++.h>
using namespace std;
int g[1005][1005],cost[1005],dp[1005];
int main(){
	memset(dp,-2e9,sizeof dp);
	int n,m,p;
	cin>>n>>m>>p;
	dp[0]=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>g[i][j];
	for(int i=1;i<=n;i++) cin>>cost[i];
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			int sum=0;  
            for(int k=1;k<=p&&k<=i;k++){
            	int last;  
                if(j-k<=0) last=n+(j-k)%n; 
                else last=j-k;                  
                sum+=g[last][i-k+1];                  
                dp[i]=max(dp[i],dp[i-k]+sum-cost[last]); 
			}
	    }	
	}
	cout<<dp[m];
	return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。