Codeforces Round #821 (Div. 2) 程序精注

竞赛情况和最终结果

原来只是Codeforces为了防止大佬注册小号随便AK所以故意设了一个新手期机制，新号初始没有Rating（以前是直接按1400算第一次Rating），需要六次比赛之后才会使用正常Rating机制。不过还是菜。

AC A – Consecutive Sum
AC* B – Rule of League
CE C – Parity Shuffle Sorting
WA D1 – Zero-One (Easy Version)
-- D2 – Zero-One (Hard Version)
-- E – Conveyor

分题总结

A – Consecutive Sum

签到题，只需要把每个可取到的余数的可找到的最大项找出来加一起就行了。

但是打题的时候突然层长进来宣布他上任的事情 :(，实在是被吓了一跳，以至于花了九分钟才把题目交上去。

/////////////////////////////////
// Codeforces Round #821 (Div. 2)
// Problem A
// 
// Powered by LoveLive Tokimeki Energy
/////////////////////////////////

#include<bits/stdc++.h>
using namespace std;

namespace lovelive{
    const int MAXN = 200;
    void main(){
        int ai[MAXN],n,k,maxi[MAXN];
        long long ans=0;
        cin>>n>>k;
        memset(maxi,0,sizeof(maxi));
        for(int i=1;i<=n;i++){
            cin>>ai[i];
            maxi[i%k] = max(maxi[i%k],ai[i]);
        }
        for(int i=0;i<k;i++){
            ans += maxi[i];
        }
        cout<<ans<<endl;
    }
}

int main(){
    int _t;
    scanf("%d",&_t);
    while(_t--){
        lovelive::main();
    }
    return 0;
}

B – Rule of League

思路

这是擂台竞技赛，不是瑞士轮、小组赛或者淘汰赛，理解成擂台赛就会好很多；
首先，有人赢就必有人输掉比赛，并且为了保持连胜，刚出场的人没有别的机会就领盒饭了，只会获得零胜一负的成绩；
（上一条的补充）就算只活一场也算成功，$n-1$轮的比赛只会有$n-1$个人有获胜纪录，必定会出现一场都没赢过的人；
在总共进行的$n-1$轮的比赛中，每一个守擂者都“必须有机会完成规定的次数”，不然这组数据非法。

实现

如果两个数都不是零，直接跳出报无解；
如果$\left(n-1\right)\space Mod \space a \ne 0$，直接报无解；
然后直接从第一个人开始按照连胜$a$场的方式输出。

赛后总结

为什么我要对这道模拟题BiBi半天？因为我不仅一开始没发现有人输的必然性，同时我甚至连输出都写了半天。菜出了一定的境界。

代码

/////////////////////////////////
// Codeforces Round #821 (Div. 2)
// Problem B
// 
// Powered by LoveLive Tokimeki Energy
/////////////////////////////////

#include<bits/stdc++.h>
using namespace std;

namespace tokimeki{
    void main(){
        //差点重构代码
    }
}

namespace lovelive{
    int n,x,y,z;
    void output(int x,int y,int mi){
        int curw = 1,cnt = 0;//老老实实模拟！
        for(int i=2;i<=n;i++){
            if(cnt == x){
                curw = i;
                cnt = 0;
            }
            printf("%d ",curw);
            cnt += 1;
        }printf("\n");
    }
    void main(){
        bool flag;
        cin>>n>>x>>y;
        if(x < y){
            z = x;x = y;y = z;
        }
        flag = false;
        if(x == 0){
            printf("-1\n");return;
        }
        if(y == 0){
            if ((n-1) % x){
                printf("-1\n");return;
            }else{
                output(x,y,n);return;
            }
        }
        printf("-1\n");return;
    }
}

int main(){
    int _t;
    scanf("%d",&_t);
    while(_t--){
        lovelive::main();
    }
    return 0;
}

C – Parity Shuffle Sorting

思路

这题其实不算难，因为：

Note that you do not have to minimize the number of operations.

请注意：你不需要使操作的次数最少。

直接构造一个必定满足的数组即可（不要像我一样试图去想贪心策略）。什么数组最无脑最好构建？当然是所有数字都一样的数组！

实现

首先处理首尾，按照规则把他们都变成一样的数；然后按照规则处理中间的每一个数，加起来和是奇数就和$1$号位赋值，否则就和$n$号位赋值。数量的确不是最少，但是最傻。

代码

/////////////////////////////////
// Codeforces Round #821 (Div. 2)
// Problem C
// 
// Powered by LoveLive Tokimeki Energy
/////////////////////////////////

/////////////////////////////////
// 赛后总结
// 竟然说的是“你不需要使变化次数最少”
// 不愧是Div.2 [汗]
/////////////////////////////////

#include<bits/stdc++.h>
using namespace std;

namespace tokimeki{
    const int MAXN = 100005;
    int ai[MAXN],n;
    void main(){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&ai[i]);
        }
        if(n==1){
            printf("0\n");
            return;
        }
        printf("%d\n%d %d\n",n-1,1,n);
        if((ai[0] + ai[n-1])%2==0){
            ai[0] = ai[n-1];//因为是以ai[0]为基准，所以反向的赋值没啥用
        }
        for(int i=1;i<n-1;i++){
            if((ai[0] + ai[i]) % 2){
                printf("1 %d\n",i+1);
            }else{
                printf("%d %d\n",i+1,n);
            }
        }
    }
}

namespace lovelive{
    // 赛时死活调不出来的丑旧代码
}

int main(){
    int _t;
    scanf("%d",&_t);
    while(_t--){
        tokimeki::main();
    }
    return 0;
}

D – Zero-One

总体思路

这题既然分成了两种难度，正好就可以顺着题意根据两种情况分别处理。

最明显的，由于每次操作需要取两个数，而如果位数不同的数量是个奇数，操作中一定会出现落单者，所以对于每一个奇数项不同的数据，直接报无解。

注意到如果在取反两个数位的时候涉及到了第三位，中间商自身会因为做了两次取反处理负负得正。对于两个相隔万里的数，可以通过以下两种方法取反两个数的值：

不远万里通过 $r-l$ 次相邻数处理（以下简称多次X处理），以 $x \times \left(r-l\right)$ 的代价（一定不要忘掉两点之间的距离！）处理；
直接使用非相邻数处理（以下简称Y处理），以 $y$ 的代价一次性搞定。

而对于两个相邻的数，在数组足够大的时候也有多重处理方法：

直接使用 X处理 以$x$的代价一次搞定；
通过一个中间商，使用两次 Y处理，以$2\times y$的代价解决。

贪心思路（针对Easy Version）

因为$x \geq y$一定成立，所以1.1完全用不上，直接用Y处理即可。

看似情况还是很多，但一步步思考：

最特殊的，当整个01串只有两个位，并且都需要处理（很明显这两个位只能是相邻的）的时候，根本没得选，只能用 X处理；
当只有两个位需要修改，并且这两个位相邻的时候，这时01串足够长，需要比较一下$x$和$2\times y$决定一下要不要选取中间商；
如果需要修改的位达到了4个或更多（别忘了开头），一定可以通过两两配对的Y处理解决问题：对于4个及以上的位，一定可以在两两配对时，选不到相邻的两点。

动态规划（针对Hard Version）

这题的动态规划大体上成两派：一派是通过二维dp左右边界处理状态转移，这种方法更为泛用但是复杂度达到了$O\left(n^2\right)$（这题也能过就是了）；另一派则仅适用于贪心思路覆盖不到的$x \lt y$的情况，但只有$O(n)$的复杂度。以下具体分析$O(n)$的处理方法。

该方法的dp公式来自知乎用户Ander的《Codeforces Round #821 (Div. 2) A~E》，本人在此对其的思路启发表示由衷感谢。

设dp[i]为处理到第$i$位的最小代价。对于直接对当前处理区间末尾的两个不同数位进行X处理DP的公式很显然：
$$dp[i] = dp[i-2] + x \times \left(dif[i]-dif[i-1]\right)$$
由于X处理处理的代价与距离有关，所以易得最优的多次X处理一定是选择两个次序相邻的不同数位进行处理。

但是对于不以距离为代价的Y处理怎么考虑？如何将其与多次X处理进行比较？

由于之前已经确保了需要处理位的数量是个偶数，所以我们DP到最后，通过X处理（多次X处理只计入首尾）和Y处理的节点一定是成对的。既然相邻两项的X处理已经决定根据上述的状态转移成对进行处理，那么最优解里剩下的位肯定是通过Y处理进行解决的，只不过可能有些位还没找到另一半。

既然这样，可以把一次Y处理拆成两个半次Y处理，并把这些半次Y处理分别给两个数位，最后在DP处理完成时，这些半次Y处理一定都可以拼成若干个完整的Y处理。

这样一来，选择就变成了下面的样子：

不远万里通过多次X处理，以 $x \times \left(r-l\right)$ 的代价（一定不要忘掉两点之间的距离！）处理，即：
$$dp[i] = dp[i-2] + x \times \left(dif[i]-dif[i-1]\right)$$
直接使用半次Y处理当前区间的最后一个点，以 $y/2$ 的代价一次性搞定：因为Y处理的代价与距离无关，所以直接加进去就可以了。
$$dp[i] = dp[i-1] + y / 2$$

最后检查一下极值，判断事情真的是这样子的：

尾部（$dp[m]$）： 如果最后一个结点决定使用半个Y处理，那么由于修改数位成对性，$dp[m-1]$一定存在一个落单的半个Y处理使得结果合法；如果最后一个结点决定使用 多次X处理 ，那么 $dp[m-2]$ 一定都是成对的节点，没有问题；既然这样，中间可能出现的落单的半个Y处理也就无需过度担心；

头部（$dp[0]$，$dp[1]$）：$dp[0]$只能选择 半个Y处理 ，因为修改数位成对性，之后一定存在另一个半个Y处理与之配对；$dp[1]$则只需要比较“直接与$dp[0]$使用多次X处理”和“单独使用半个Y处理”（这不就和$dp[0]$配上对了）。

特殊情况：如果两个数位是相邻的，那么他们将不得不使用X处理。不过由于前置条件$x \lt y$，那么一定会出现 $$ dp[i-2] + x \times \left(dif[i]-dif[i-1]\right) \lt dp[i-1] + y / 2$$的情况（别忘了不管是两个半个Y处理还是一个X处理本质上都只是一次处理）。

注：为了在处理时不出现小数以减少误差，代码里将dp数组设成了“答案的两倍”，所以最后需要除以2。

代码

/////////////////////////////////
// Codeforces Round #821 (Div. 2)
// Problem D
// 
// Powered by LoveLive Tokimeki Energy
/////////////////////////////////

#include<bits/stdc++.h>
using namespace std;

namespace kirakira{
    // 重构贪心代码
    const long long TWO = 2;
    string a,b;long long n,x,y,m;
    vector<long long> dif;//这次就不作死动用vector的删除节点了
                    //看清题目要求：简单版本不能也不用关心
    bool used[5005];
    long long dp[5005];               //注意dp为答案的两倍
    void tanxin(){
        int l=0,r=0,ans=0;
        if(dif.size() == 2 && dif[0] + 1 == dif[1]){
            if(n == 2 || x < 2 * y){
                printf("%lld\n",x);
            }else{
                printf("%lld\n",y * 2);
            }
        }else{
                printf("%lld\n",y * m / 2);     // 因为合法的対换点是成对出现的，
                                                // 所以一定能通过成对对换实现
            }
        //printf("%d\n",ans);
        return;
    }
    void dpi(){
        memset(dp,0x3f3f3f3f,sizeof(dp));
        dp[0] = y;
        dp[1] = min(dp[0] + y, TWO * x * (dif[1] - dif[0]));
        for(int i=2;i<m;i++){
            dp[i] = min(dp[i-2] + (dif[i]-dif[i-1]) * TWO * x,dp[i-1] + y);
        }
        printf("%lld\n",dp[m-1] / 2);
    }
    void main(){
        dif.clear();
        //memset(used,false,sizeof(used));
        cin>>n>>x>>y;
        cin>>a>>b;
        for(int i=0;i<n;i++){
            if(a[i]!=b[i]) dif.push_back(i);
        }
        m = dif.size();
        if(m % 2) {
            printf("-1\n");
            return;
        }
        if(m == 0){//记得特判
            printf("0\n");
            return;
        }
        if (x >= y){
            tanxin();
        }else{
            dpi();
        }
    }
}

int main(){
    int _t;
    scanf("%d",&_t);
    while(_t--){
        kirakira::main();
    }
    return 0;
}

E – Conveyor

既然模拟小球废代码还费力（虽然自己模拟一下似乎不会出现小球合并的情况），那么……为什么不用类似前缀和的方法解决呢？

因为所有的引导槽方向默认向右，第一个小球往右，第二个往下，第三个往右……所以经过每个点的共计$n$个小球，都会有$\lceil \frac{n}{2} \rceil$个小球向右跑，$\lfloor \frac{n}{2} \rfloor$个小球向下跑。这样就可以通过将当前点的所有小球都递推下去来计算在第$t$秒的时候到达$\left(x,y\right)$的点的总数。

由于从$\left(0,0\right)$到$\left(x,y\right)$至少需要消耗$x + y$的时间，所以在$t+1$（别忘了第0秒还有一个小球）秒时总共只有$(t+1)-x-y$个小球有机会到达点$\left(x,y\right)$，之后的小球虽然不会对答案造成影响，但是会对递推造成影响，所以应舍去这几个小球。

既然算出了这个值，那么如果$t$秒时经过该点的小球数量与$t-1$秒时的不同，就说明第$t$秒的时候有球在点上。

/////////////////////////////////
// Codeforces Round #821 (Div. 2)
// Problem E
// 
// Powered by LoveLive Tokimeki Energy
/////////////////////////////////

#include<bits/stdc++.h>
using namespace std;

namespace lovelive{
    long long dp[150][150];
    long long query(long long t,long long x,long long y){
        memset(dp,0,sizeof(dp));
        dp[0][0] = max(t-x-y+1,(long long)0);
        for(int i=0;i<=x;i++){
            for(int j=0;j<=y;j++){
                dp[i][j+1] += (dp[i][j] + 1)/2;
                dp[i+1][j] += (dp[i][j])/2;
            }
        }
        return dp[x][y];
    }
    void main(){
        long long n,x,y;
        cin>>n>>x>>y;
        if(query(n-1,x,y) == query(n,x,y)) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
        return;
    }
}

int main(){
    int _t;
    scanf("%d",&_t);
    while(_t--){
        lovelive::main();
    }
    return 0;
}