欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CodeForces 1384总结

程序员文章站 2022-07-08 17:18:37
这是一场我打的不怎么成功也不怎么失败的比赛,虽然只出了一个题,而且半个来小时才出,但是居然奇迹般地加分了。这场比赛讲实话确实有的题我到现在也没大读懂题意,道行尚浅,还需修炼啊。A. Common Prefixes给你一串数字,第i个数字代表第i个字符串和第i+1个字符串前缀字母相同地个数,输出符合题意的一组字符串即可。水过,自定义一串原始字符串,下面的第i个字符串前ai个字母直接输出上面字符串的ai个即可,后面随便稍微一改就可以。B. Koa and the Beach共a1~an代表n片水域的深...

这是一场我打的不怎么成功也不怎么失败的比赛,虽然只出了一个题,而且半个来小时才出,但是居然奇迹般地加分了。这场比赛讲实话确实有的题我到现在也没大读懂题意,道行尚浅,还需修炼啊。
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

相关标签: CodeForces