[洛谷题解] CF1244F Chips

发布于 2019-10-14  574 次阅读

题目链接：CF1244F Chips

题目描述

有n个棋子排成环状，标号为1..n

一开始每个棋子都是黑色或白色的。随后有k次操作。操作时，棋子变换的规则如下：我们考虑一个棋子本身以及与其相邻的两个棋子（共3个），如果其中白子占多数，那么这个棋子就变成白子，否则这个棋子就变成黑子。注意，对于每个棋子，在确定要变成什么颜色之后，并不会立即改变颜色，而是等到所有棋子确定变成什么颜色后，所有棋子才同时变换颜色。

对于一个棋子i，与其相邻的棋子是i-1和i+1。特别地，对于棋子1，与其相邻的棋子是2和n；对于棋子n，与其相邻的棋子是1和n-1。

如图是在n=6时进行的一次操作。

给你n和初始时每个棋子的颜色，你需要求出在k次操作后每个棋子的颜色。

输入格式

第一行两个整数n\ (3 \leq n \leq 2\cdot 10^5)和k\ (1 \leq k \leq 10^9)，表示棋子总数与操作次数。

第二行是一个长度为n的，仅由字符B和W构成的字符串。如果第i个字符是B，表示第i个棋子位黑色，否则为白色。

输出格式

一行，长度为n的，仅由字符B和W构成的字符串，描述操作完成后每个棋子的颜色。

注意输出的顺序要和输入数据中的对应。

样例解释

  1. 就是题目描述中举的那个例子

  2. "WBWBWBW" \rightarrow "WWBWBWW" \rightarrow "WWWBWWW" \rightarrow "WWWWWWW"

  3. "BWBWBW" \rightarrow "WBWBWB" \rightarrow "BWBWBW" \rightarrow "WBWBWB" \rightarrow "BWBWBW"

提示

如果棋子数量是偶数，并且任意两个相邻棋子颜色不同，那么答案只和k的奇偶性有关。否则，棋子的状态将呈收敛趋势，最终达到一个“稳定状态”，不再改变。

重要的结论与证明

不难发现，随着不停地操作，我们可以将棋子的变化规律分为以下两类：

  1. 如果棋子数是偶数，并且任意两个相邻棋子颜色不同，那么答案只和k的奇偶性有关。
  2. 否则，棋子的状态将呈收敛趋势，最终达到一个“稳定状态”，不再改变。

理由？

对于第一类：显然，假设一开始状态是BWBWBWBW...BWBW，那么操作偶数次后，状态是 BWBWBWBW...BWBW，否则状态是 WBWBWBWB...WBWB。

对于第二类：

如果开始时就是“清一色”，那么必然已经是稳定状态。

否则我们根据颜色对这个棋子环划分“连通块”。比如下图：

（其中长度为1的连通块用一个小圆圈表示）

不难发现，如果一个棋子已经处于长度大于1的连通块中，那么在一次操作后其颜色不会改变，并且将仍然处于一个长度大于1的连通块中。

并且如果一个长度为1的连通块与一个长度大于1的连通块相邻，那么一次操作后，这个长度为1的连通块中的那个棋子就会变色，而与其相邻的，长度大于1的那个连通块却不会变色。那么，这个棋子就被加入到了与其相邻的连通块中。

这样，只要图中同时存在长度大于1（这个一定存在，否则就不是我们讨论的情况了）和等于1的连通块，每操作一次，其中长度等于1的连通块数量至少减少1。最终，一定会到达一个不存在长度等于1的连通块的状态。这就是“稳定状态”，到达这个状态后再进行操作，则没有棋子会再改变颜色。

解题方法

我们将所有长度为1的连通块提出来，构成连通块。为了防止混淆，我们称这种连通块为“相间区间”。

这句话可能有点晕，但是可以借助图片理解（蓝色表示构成的相间区间）：

根据上面的证明，每次操作时，只有相间区间中的棋子会且一定会改变颜色。相间区间中的棋子改变颜色后，其两端的（指区间中的两端）的棋子将不再属于相间区间。

设dist_i表示第i个棋子离其两侧的，长度大于1的连通块的距离中较小的一个。

从此处开始，用0表示白色，1表示黑色。

那么，当k \leq dist_i时，第i个棋子仍然属于间隔区间，其值为val[i] ^ (k&1)。否则，这个棋子已经被离其较近的一个长度大于1的连通块给“同化”了（如果两侧的连通块离这个棋子一样近，显然两侧的连通块颜色相同）。

实现细节

方便起见，先将棋子标号改为0..n-1。设val[i]表示棋子(i%n+n)%n的颜色。

首先，特判掉“棋子数是偶数，并且任意两个相邻棋子颜色不同”的情况。

然后，我们找到任意一个满足val[i] = val[i-1]的位置。

从这个位置开始顺时针扫一遍，记录每个相间区间内的棋子离左侧的，长度大于1的连通块的距离，以及其左侧的，长度大于1的连通块的颜色。

再从这个位置的前一个位置开始逆时针扫一遍，记录每个相间区间内的棋子右侧的，长度大于1的连通块的颜色。另外，判断每个相间区间内的棋子离右侧的，长度大于1的连通块的距离是否小于上一轮记录的距离。如果小于，将距离更新为当前距离的相反数（使用正负两种数，以便判断一个棋子是离左边的连通块更近还是离右边更近）

其他细节可以见代码。

// status: [Accepted][unofficial]
// oj:     [Codeforces]

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

typedef long long ll;
#define int ll

const int MAXN = 200001;
int n,k;
// 棋子的初始颜色
int arr[MAXN];
// 棋子离左右侧长度大于1的连通块更近的那个距离
int dist[MAXN];
// 棋子左侧长度大于1的连通块的颜色
int lc[MAXN];
// 棋子右侧长度大于1的连通块的颜色
int rc[MAXN];

signed main() {
    ios::sync_with_stdio(false);

    cin>>n>>k;

    // 读入
    for(int i=0;i<n;i++) {
        char c;
        cin>>c;
        if(c == 'B') arr[i] = 1;
    }

    // 特判
    bool flag1 = (n%2 == 0);
    if(flag1) for(int i=0;i<n;i++) {
        if(arr[0] ^ arr[i] ^ (i&1)) {flag1 = false;break;}
    }
    if(flag1) {
        cerr<<"I AK IOI"<<endl;
        for(int i=0;i<n;i++) {
            if(arr[i] ^ (k&1)) cout<<'B';
            else cout<<'W';
        }
        cout<<endl;
        exit(0);
    }

    // 找到开始位置
    int bg = 0;
    for(int i=0;i<n;i++) {
        if(i!=0 && arr[i-1] == arr[i]) {bg = i;break;}
    }
    bg += n;

    // 顺时针遍历
    int lastpos = 0;
    int lastcol = 0;
    for(int i=bg;i<bg+n;i++) {
        if(arr[(i-1) % n] != arr[i % n] && arr[i % n] != arr[(i+1) % n]) { // 判断是否相间区间
            dist[i % n] = i - lastpos;
            lc[i % n] = lastcol;
        }
        else {lastpos = i;lastcol = arr[i % n];dist[i % n] = 0;}
    }
    bg += n;
    for(int i=bg-1;i>=bg-n;i--) {
        if(arr[(i-1) % n] != arr[i % n] && arr[i % n] != arr[(i+1) % n]) { // 判断是否相间区间
            if(lastpos - i < dist[i % n]) {
                dist[i % n] = i - lastpos; // 更新距离
            }
            rc[i % n] = lastcol;
        }
        else {lastpos = i;lastcol = arr[i % n];}
    }

    // 输出
    for(int i=0;i<n;i++) {
        if(dist[i] == 0) {
            if(arr[i]) cout<<'B';
            else cout<<'W';
        }
        else if(dist[i] > 0) {
            if(k < dist[i]) {
                if(arr[i] ^ (k&1)) cout<<'B';
                else cout<<'W';
            }
            else {
                if(lc[i]) cout<<'B';
                else cout<<'W';
            }
        }
        else {
            if(k < -dist[i]) {
                if(arr[i] ^ (k&1)) cout<<'B';
                else cout<<'W';
            }
            else {
                if(rc[i]) cout<<'B';
                else cout<<'W';
            }
        }
    }
    cout<<endl;
}

评测记录：R25183207

赏

undefined