CodeForces 1384总结

这是一场我打的不怎么成功也不怎么失败的比赛，虽然只出了一个题，而且半个来小时才出，但是居然奇迹般地加分了。这场比赛讲实话确实有的题我到现在也没大读懂题意，道行尚浅，还需修炼啊。
A. Common Prefixes
给你一串数字，第i个数字代表第i个字符串和第i+1个字符串前缀字母相同地个数，输出符合题意的一组字符串即可。
水过，自定义一串原始字符串，下面的第i个字符串前ai个字母直接输出上面字符串的ai个即可，后面随便稍微一改就可以。
B. Koa and the Beach
共a1~an代表n片水域的深度，以2*k秒为一个单位时间，前k秒每秒深度+1，后k秒每秒深度-1。现有人想从海的岸边游到岛上，他可以每秒游1米或者不游，如果当前海域深度大于 l 他会被淹死，问他是否能成功游到岛上。
看了题解，可以用dp解决，dp[ i ][ j ] 表示第 j 秒 在第 i 片海域，如果此时海域高度小于 l ，状态转移方程为

dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]);

下面是ac代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstdio>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=200005;
typedef long long ll;
ll t,dp[105][maxn],a[maxn],b,c,d,id,temp,h,n,m,i,j,k,x,y,z,ans,cnt,sum,Max1,Max2,Min,ji,ou,l,index;
int main()
{
    ios::sync_with_stdio(false);
	cin >> t;
	while (t--)
	{
        memset(dp, -1, sizeof(dp));
        cin>>n>>k>>l;
        for (i = 1; i <= n; i++)
            cin>>a[i];
        for (i = 0; i <= 2 * k * n; i++)
            dp[0][i] = 0;
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= 2 * k * n; j++)
            {
                if (dp[i - 1][j - 1] == -1 && dp[i][j - 1] == -1) continue;
                if (j % (2 * k) < k) h = a[i] + j % k;
                else h = a[i] + k - (j % k);
                if (h <= l) dp[i][j] = 0;
            }
        }
        int fl = 0;
        for (i = 0; i <= 10000; i++)
        {
            if (dp[n][i] == 0) fl = 1;
        }
        if (fl == 1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
	}
	return 0;
}

C. String Transformation 1
给你两个长度相同字符串，你可以将a中的几个相同字母改成任意一个大于a的字母，问经过几次修改才能使a变成b
无解情况：a的某个位置的字母大于b的那个位置的字母。其余情况均有解，每次把a中需要修改的字符改成所需要改成的最小的字符，慢慢后续再不停变大（好难叙述，叙述的好不清楚）。
D. GameGame
两人游戏，游戏从一个由非负整数组成的长度为n的数组a开始，最初二人得分都是0，从Koa开始游戏，每人可以在一步中选择数组中的任何元素并将其从数组中移除，并使用玩家当前的分数对其进行异或，数组a空了的时候游戏结束，得分高的人获胜，问Koa是输了还是赢了（或者平局）。
E. String Transformation 2
与c题类似，唯一不同的地方在于移动方式，本题中在一次移动中，（1≤pi≤n;pi≠pj if i≠j这句话我理解了好久，大致应该就是选出来的字母各不相同的意思吧)，选出各不相同的几个字母全部改成另一个字母，问几次修改能使a变成b
F. Rearrange
有一个nm的矩阵a，矩阵内包括1~nm的整数（每个数只出现一次），S（A）=（X，Y）代表A的谱，其中X是A行中最大值的集合，Y是A列中最大值的集合。现题目要求找出n行m列的矩阵A′，这样从1到n⋅m的每个数字在矩阵中只出现一次，剩下的题意我还没看懂…等看懂了再回来写…

本文地址：https://blog.csdn.net/weixin_46434074/article/details/107590776