Educational Codeforces Round 123 (Rated for Div. 2)

前言：这场\(CF\)不知道是良心发现还是什么的，突然变简单了（bushi

A-Doors and Keys

有\(R,G,B\)三扇门，每扇门对应\(r,g,b\)三把钥匙，钥匙和门按顺序排在一个狭窄的走廊中，只有有了钥匙才能打开对应的门。有\(n\)组询问，每次有一个长度为\(6\)的字符串，问能否走过整条走廊。\((1\leq n\leq720)\)

思路

这题就是一个非常简单的题目啦，稍微想想就能过啦。

代码

#include<bits/stdc++.h>
using namespace std;
char s[10];
int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        scanf("%s",s+1);
        bool r=0,g=0,b=0;
        bool ck=1;
        for(int i=1;i<=6;i++)
        {
            if(s[i]=='r')r=1;
            else if(s[i]=='g')g=1;
            else if(s[i]=='b')b=1;
            else if(s[i]=='R'){if(!r){ck=0;break;}}
            else if(s[i]=='G'){if(!g){ck=0;break;}}
            else if(s[i]=='B'){if(!b){ck=0;break;}}
        }
        if(ck)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

B-Anti-Fibonacci Permutation

有\(t\)组数据，对于每一个给定的\(n\)，你需要输出\(n\)个不同的\(1,2,...,n\)的某排列使得\(\forall i>2,a_i\not=a_{i-1}+a_{i-2}\)。\((1\leq t\leq48,3\leq n\leq50)\)

思路

稍微想一想其实就是倒着的排列，然后把\(1\)的位置换来换去就行了。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            for(int j=n;j>i;j--)printf("%d ",j);
            printf("%d ",1);
            for(int j=i;j>=2;j--)printf("%d ",j);
            printf("\n");
        }
    }
    return 0;
}

C-Increase Subarray Sums

有\(t\)组询问，每次给你一个长度为\(n\)的序列\(a_1,a_2,...,a_n\)，然后定义一个函数\(f(k)\)表示对序列中任意\(k\)个数增加\(x(已给出)\)后所有连续的字串的和中的最大值，对于\(k=0,1,2,...,n\)，输出\(f(k)\)。\((1\leq k\leq5000,1\leq n\leq5000,0\leq x\leq10^5,-10^5\leq a_i\leq10^5,\sum n\leq5000)\)

思路

这题我已经不想说什么了，就是一个非常暴力的方法然后赛时怎么也想不出来，哭死……

代码

#include<bits/stdc++.h>
using namespace std;
int a[5005],b[5005],c[5005];
int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        int n,x;
        scanf("%d%d",&n,&x);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[i]=b[i-1]+a[i];
            c[i]=-1e9;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j+i-1<=n;j++)
            {
                c[i]=max(c[i],b[j+i-1]-b[j-1]);
            }
        }
        int ans=0;
        for(int i=0;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                ans=max(ans,c[j]+i*x);
            }
            printf("%d ",ans);
        }
        printf("\n");
    }
    return 0;
}

D-Cross Coloring

有\(t\)组数据，每次有一个\(n*m\)的方格，初始为白色，然后又给你\(k\)种颜料和\(q\)个格子，每次按给的格子的顺序，选一种颜色，把这一行和这一列都涂成这个颜色。涂色结果不同当且仅当有至少一个格子的颜色不同。问对于每一组数据，有多少种不同的涂色结果。\((1\leq t\leq10^4,1\leq n,m,k,q\leq2*10^5,\sum q\leq2*10^5)\)

思路

这题其实就是想让我们找到方格中有多少只能涂相同颜色的格子组成的集合。那么我们可以从后往前找，然后进行一定的标记，然后就能\(AC\)啦，只不过要想清楚，不然会\(WA\)的很惨……

代码

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int s=0,w=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return (w==-1?-s:s);
}
bool xx[200005],yy[200005];
int x[200005],y[200005];
const long long mod=998244353;
long long poww(long long a,long long n)
{
    long long ans=1;
    while(n)
    {
        if(n&1)ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
int main()
{
    int _=read();
    while(_--)
    {
        int n=read(),m=read(),k=read(),q=read();
        for(int i=1;i<=n;i++)xx[i]=0;
        for(int i=1;i<=m;i++)yy[i]=0;
        for(int i=1;i<=q;i++)x[i]=read(),y[i]=read();
        int cnt=0;
        int xxx=n,yyy=m;
        for(int i=q;i>=1;i--)if((!xx[x[i]])||(!yy[y[i]]))
        {
            cnt++;
            if(!xx[x[i]]){xx[x[i]]=1;xxx--;}
            if(!yy[y[i]]){yy[y[i]]=1;yyy--;}
            if(xxx==0||yyy==0)break;
        }
        printf("%lld\n",poww(1ll*k,1ll*cnt));
    }
    return 0;
}

E-Expand the Path

有\(t\)组询问，每次给一个\(n*n\)的方格，有一个机器人从\((1,1)\)点出发，按照\(“RD”\)字符串所给的指令向右向下走，现在能进行操作把某个单个的指令变成两个同样的指令，保证机器人不走出方格。每次问你经过若干次操作之后机器人能经过的点有几个。

思路

其实就是一道简单的想法题，在草稿纸上画一画就能知道情形并且\(AC\)了。

代码

#include<bits/stdc++.h>
using namespace std;
char s[200005];
int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        int n;
        scanf("%d",&n);
        scanf("%s",s+1);
        int len=strlen(s+1);
        int r=0,d=0;
        int x=1,y=1;
        int rr=0,dd=0,rrr=0;
        for(int i=1;i<=len;i++)
        {
            if(!r&&s[i]=='R')r=i;
            if(!d&&s[i]=='D')d=i;
            x+=(s[i]=='D');
            y+=(s[i]=='R');
            if(r)dd+=(s[i]=='D');
            if(!d)rr+=(s[i]=='R');
            if(d)rrr+=(s[i]=='R');
        }
        long long ans=len;
        if(r)
        {
            ans+=1ll*(dd+1)*(n-y);
            if(d)
            {
                ans+=1ll*(n-rr)*(n-x);
            }
            printf("%lld\n",ans+1);
        }
        else
        {
            ans+=1ll*(rrr+1)*(n-x);
            printf("%lld\n",ans+1);
        }
    }
    return 0;
}