多项式输出（枚举）

思路

分以下情况讨论即可：

• 系数小于0，输出负号；
• 系数大于0且不是第一个，输出加号；
• 系数等于1，可直接省略；
• 系数等于0，可直接跳过；
• 次幂i大于1时，输出 x^i；
• 次幂i等于1时，输出x；
• 次幂i等于0时输出系数即可。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
	freopen("poly.in","r",stdin);
	freopen("poly.out","w",stdout);
    int n;
    cin >>n;
    bool ans=true;
    for(int i=1;i<=n+1;i++){
        int x;
        cin >>x;
        int k=n-i+1;
        if(x!=0){
            if(ans!=0){
                if(x<0) cout <<"-";
                ans=false;
            }else{
            	if(x>0) cout <<"+";
            	else cout <<"-";
			}
            if(abs(x)!=1||k==0){
            	cout <<abs(x);
			}
            if(k==1){
            	cout <<"x";
			}
            if(k>1){
            	cout <<"x^"<<k;
			}
        }
    }
    return 0;
}

潜伏者（模拟）

思路没想到的原因

只忘了一个特判，具体见思路。

思路

我们要创造映射。

mp[a[i]]=b a-->b的映射

mp1[b[i]]=a b-->a的映射

若出现重复映射且映射值不相等，输出Failed（没想到）；

若不重复的映射个数小于$26$，输出Failed。

代码

#include <bits/stdc++.h>
using namespace std;

map<char,char> mp;
map<char,char> mp1;

int main(){
	freopen("spy.in","r",stdin);
	freopen("spy.out","w",stdout);
    string a,b,s;
    int cnt=0;
    string ans;
    bool flag=0;
    getline(cin,a);
    getline(cin,b);
    getline(cin,s);
    for(int i=0;i<=a.size();i++){
    	if((mp1[a[i]]!=0&&mp1[a[i]]!=b[i])||(mp[b[i]]!=0&&mp[b[i]]!=a[i])){
    		cout <<"Failed";
    		return 0;
		}else{
			mp1[a[i]]=b[i];
			mp[b[i]]=a[i];
		}
	}
	for(int i='A';i<='Z';i++){
		if(mp[i]==0){
			cout <<"Failed";
    		return 0;
		}
	}
	for(int i=0;i<s.size();i++){
		cout <<mp1[s[i]];
	}
    return 0;
}

细胞分裂（模拟）

思路没想到的原因

暴力写的，用了快速幂，所以时间复杂度很高，超时。

思路

我们知道，如果$a$能整除$b$，那么$a$应该包含$b$的所有质因子。

我们先求出$m1$的质因子各个数的数量，再来判断$a[i]$是否可以整除质因子。

如果可以，就输出所有合法的max值。

否则，continue继续遍历。

如果到了最后还没有满足条件的，输出-1。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=1e4+10;
pair<int,int> m[3*tt];
int m1,m2,op;
int a[tt];

void divide(int n){
	for(int i=2;i<=n-1;i++){
		if(n%i==0){
			int cnt=0;
			m[++op].first=i;
			while(n%i==0){
				n/=i;
				cnt++;
			}
			m[op].second=cnt*m2;
		}
	}
	if(n>1){
		m[++op].first=n;
		m[op].second=m2;
	}
}

int f(int t){
	int res=0;
	for(int i=1;i<=op;i++){
		if(t%m[i].first){
			return -1;
		}else{
			int cnt=0;
			int z=t;
			while(z%m[i].first==0){
				z/=m[i].first;
				cnt++;
			}
			res=max(res,(m[i].second+cnt-1)/cnt);
		}
	}
	return res;
}

signed main(){
	freopen("cell.in","r",stdin);
	freopen("cell.out","w",stdout);
    int n;
    int cnt=0;
    cin >>n;
    cin >>m1>>m2;
    int y=0x3f3f3f3f;
    divide(m1);
    for(int i=1;i<=n;i++){
    	cin >>a[i];
    	int w=f(a[i]);
    	if(w!=-1){
    		y=min(y,w);
		}
	}
	if(y==0x3f3f3f3f) cout <<"-1";
	else cout <<y;
    return 0;
}

道路游戏（DP）

思路没想到的原因

对$DP$的题型还不够熟练，在考试的时候也感觉太难了，所以没有做。

思路

状态表示：

• $f[i]$表示到第$i$个时间点能够收集到的最大金币数量；
• $cost[i]$表示从第$i$个点购买机器人的花费；
• $sum$表示从$i-k$走过来搜集的金币的数量。

状态计算：$f[i]=max(f[i-k]+sum-cost[last],f[i])$

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=1010;
int a[tt][tt];
int f[tt];
int cost[tt];

int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
    int n,m,p;
    cin >>n>>m>>p;
    f[0]=0;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		cin >>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
    	cin >>cost[i];
	}
	for(int i=1;i<=m;i++){
		f[i]=-2e9;
	}
	int sum=0;
	for(int i=1;i<=m;i++){//时间
		for(int j=1;j<=n;j++){ //位置 
			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+=a[last][i-k+1];
				f[i]=max(f[i-k]+sum-cost[last],f[i]);
			}
		}
	}
	cout <<f[m];
    return 0;
}

谢谢