Codeforces Round #627 (Div. 3)(CF1324)

sdxjzsq · 2020-03-14 03:33:28 · 个人记录

题目链接:https://codeforces.com/contest/1324/problems

A - Yet Another Tetris Problem

#include<cstdio>
using namespace std;
int n,t,a[105],flag;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        flag=1;
        scanf("%d",&n);
        for(register int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(i>1&&(a[i]&1)!=(a[i-1]&1))flag=0;
        }
        if(flag)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

B - Yet Another Palindrome Problem

开始以为要DP，后来发现长度大于3即可，那么直接判断有没有两个不相邻的相同字符就行了。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn= 5005;
int t,num[maxn],a[maxn],n,flag;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        flag=0;
        scanf("%d",&n);
        memset(num,0,sizeof(num));
        for(register int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            num[a[i]]++;
            if((num[a[i]]==2&&a[i-1]!=a[i])||num[a[i]]>2)flag=1;
        }
        if(flag)printf("YES\n");
        else printf("NO\n");
    }
}

C - Frog Jumps

并不会往左跳...

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn= 2e5+7;
int t,len,num,maxx;
char s[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s+1);
        len=strlen(s+1);
        num=maxx=0;
        for(register int i=1;i<=len;i++)
            if(s[i]=='R')maxx=max(maxx,num),num=0;
            else num++;
        maxx=max(maxx,num);
        printf("%d\n",maxx+1);
    }
}

D - Pair of Topics

之前NOJ邀请赛柏老板出过类似的题目，直接做差排序（或按照差值排序）计数即可。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2e5+7;
int n,a[maxn],x;
long long ans,orz=1;
int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(register int i=1;i<=n;i++)scanf("%d",&x),a[i]-=x;
    sort(a+1,a+n+1);
    bool flag=true;
    x=upper_bound(a+1,a+n+1,0)-a;
    ans+=1ll*(n-x)*(n-x+1)/2;
    int l=x-1,r=x;
    while(l>0&&r<=n)
    {
        if(a[l]+a[r]<=0)r++;
        else l--,ans+=n-r+1;
    }
    printf("%lld",ans);
    return 0;
}

E - Sleeping Schedule

DP即可。

#include<cstdio>
#include<cstring>
#include<algorithm> 
#define check(x) (x>=l&&x<=r)
using namespace std;
const int maxn = 2005;
int n,h,l,r,a[maxn],dp[maxn][maxn],ans;
int main()
{
    scanf("%d%d%d%d",&n,&h,&l,&r);
    for(register int i=1;i<=n;i++)scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));dp[0][0]=0;
    for(register int i=1;i<=n;i++)
        for(register int j=0;j<h;j++)
            if(dp[i-1][j]!=-1)
                ans=max(ans,dp[i][(j+a[i])%h]=max(dp[i][(j+a[i])%h],dp[i-1][j]+check((j+a[i])%h))),
                ans=max(ans,dp[i][(j+a[i]-1)%h]=max(dp[i][(j+a[i]-1)%h],dp[i-1][j]+check((j+a[i]-1)%h)));
    printf("%d",ans);
    return 0;
}