T1

思路： 模拟所有情况即可

1. 从大到小遍历 $i: n \sim 0$
2. 系数小于0输出负号
3. 系数大于0且不是第一个，输出+
4. 系数等于1省略
5. 系数等于0跳过
6. 次幂i大于1时输出 x^i, 等于1时输出x，等于0时输出系数即可

#include <iostream>
#include <algorithm>
#define io(x); freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);
using namespace std;

int main()
{
	io("poly");
	int n;
	cin >> n;
	bool is_first = true;
	for (int i = n; i >= 0; i -- )
	{
		int a;
		cin >> a;
		if (!a) continue;
		if (!is_first && a > 0) printf("+");
		else if (a < 0) printf("-");
		if (abs(a) != 1 || !i) printf("%d", abs(a));
		if (i) printf("x");
		if (i > 1) printf("^%d", i);
		
		is_first = false;
	}
	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>  
#define io(x); freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);  
using namespace std;  
  
char mp1[100], mp2[100];  
  
int main()  
{  
    io("spy");  
    string s1,s2,s3;  
    cin >> s1 >> s2 >> s3;  
    int len = s1.size();  
    memset(mp1, '*', sizeof mp1);  
    memset(mp2, '*', sizeof mp2);  
    int cnt = 0;  
    for (int i = 0; i < len; i++)  
    {  
        if (mp1[s1[i]]=='*' && mp2[s2[i]]== '*')  
        {  
            mp1[s1[i]] = s2[i]; // 密文-->原文  
            mp2[s2[i]] = s1[i];             cnt ++;  
        }  
        else if(mp1[s1[i]] != s2[i])  
        {  
            cout << "Failed";  
            return 0;  
        }  
    }  
    if (cnt < 26) cout << "Failed";  
    else  
    {  
        for (int i = 0; i < s3.size(); i++)  
            cout << mp1[s3[i]];  
    }  
    return 0;  
}

T3

题意： 求 $s_i^k | m1^{m2}$ 成立的最小的 $k$

思路： 若 A | B，则 A 应该包含所有 B 的质因子。

比如： 120 | 20 120 : 2 2 2 3 5 20 : 2 2 5

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], k) ，其中 f[j] / s[j]需要上取整。
3. 对于所有 s_i 的 k，求最小值即为答案。

#include<bits/stdc++.h>  
#define io(x); freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);  
using namespace std;  
int a[10010],f[30010],ans=2e9;  
int main()  
{  
    io("cell");  
    int n,m1,m2,i,j=1,b,s,k;  
    scanf("%d%d%d",&n,&m1,&m2);  
    if(m1==1){  
        printf("0\n");  
        return 0;  
    }  
    for(i=1;i<=n;i++)scanf("%d",&a[i]);  
    while(m1>1){  // 质因数分解m1
        j++;  // m1 的质因子种类
        while(m1%j==0)m1/=j,f[j]++;  
        f[j]=f[j]*m2;  
    }  
    for(i=1;i<=n;i++){  
        b=0;  
        for(k=2;k<=j;k++){  // 枚举所有m1的质因子
            if(f[k]==0)continue;  
            s=0;  
            while(a[i]%k==0)a[i]/=k,s++; // s_i 的质因子k的个数
            if(!s){b=2e9;break;}  // s_i 不包含 k 这个质因子，跳过s_i
            b=max(b,(f[k]+s-1)/s);  
        }  
        ans=min(ans,b);  
    }  
    if(ans==2e9)printf("-1\n");  
    else printf("%d\n",ans);  
    return 0;  
}

T4

题意：

有n个工厂，第 j 个工厂与第 j + 1 个工厂之间有道路 i 。 道路上每个时刻都有金币，你可以在任意工厂购买机器人，并设定让它逆时针走 k 个时刻，机器人会收集走过道路上的金币，问m个时刻能收集的最大金币是多少？

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

思路：很典型的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时刻的最大值 + 走过来收集的金币 - 买机器人金币)

int f[N]; //f[i]表示时间为i的时候一共可以获得多少金币

枚举时间节点 i
    枚举机器人位置 j
        枚举步数 k

#include <iostream>  
#include <cstring>  
using namespace std;  
int g[1005][1005],cost[1005];  
int dp[1005]; int main()  
{  
    int n,m,p;  
    cin>>n>>m>>p;  
    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];  
    memset(dp,-0x3f,sizeof(dp));
    dp[0]=0;   //初始化     
    for(int i=1;i<=m;i++) //枚举时间，前i分钟     
    {  
        for(int j=1;j<=n;j++) //枚举结束位置，以j号工厂结束         
        {  
            int sum=0;  //sum表示走过来的过程中能收集多少金币  
            for(int k=1;k<=p && k<=i;k++)  
           //k表示走了k步到达j号工厂,同时,也表示走到的用时，所以有 k<=p && k<=i  
            {  
                int last;  //last表示走k步前，工厂是多少号  
                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]); 
                //状态转移方程，第i分钟的最大值=max(前i-k分钟最大值+走过来得到金币数-花销)             
             }  
        }  
    }  
    cout<<dp[m]; //第m分钟的最大值，及答案    
    return 0;  
}