[洛谷题解] CF1244F Chips

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


题目链接:CF1244F Chips


题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

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

样例解释

  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