Codeforces 1244F. Chips

传送门

显然可以注意到连续的两个相同颜色的位置颜色是不会改变的，并且它还会把自己的颜色每秒往外扩展一个位置

同时对于 $BWBWBW...$ 这样的序列，它每个位置的颜色每一秒变化一次

然后可以发现，对于一个位置 $x$，在 $x$ 左边和右边 连续两个相同颜色 扩展到 $x$ 之前， $x$ 的颜色一定是每秒变化一次

考虑每个位置 $x$ 第 $k$ 秒时的颜色，如果 $x$ 初始往 左或者往右的连续两个相同颜色 扩展到 $x$ 的时间都大于 $k$ ，那么我们可以通过 $k$ 的奇偶性和 $x$ 的初始颜色 求出最终的颜色

如果 $x$ 初始往左或者往右的 连续两个相同颜色 扩展到 $x$ 的时间小于 $k$ ，那么需要时间比较小的那边就会先把 $x$ 同化

所以我们可以通过预处理出每个位置往左和往右第一个 连续两个相同颜色 来判断每个位置最终的颜色

实现看代码吧

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+;

int n,m,L[N],R[N];

char s[N],ans[N];

vector <int> pos;

bool vis[N];

int main()

{

    n=read(),m=read();

    scanf("%s",s+);

    for(int i=;i<=n;i++)

    {

        int l=(i+n-)%n+,r=i%n+;

        if(s[l]==s[i]||s[r]==s[i]) pos.push_back(i),vis[i]=;

    }

    int len=pos.size();

    if(!len)

    {

        for(int i=;i<=n;i++)

            ans[i]= (s[i]=='W' ^ (m&)) ? 'W' : 'B';

        for(int i=;i<=n;i++) printf("%c",ans[i]); puts("");

        return ;

    }

    int las=pos[len-];

    for(int i=;i<=n;i++)

        if(vis[i]) las=i;

        else L[i]=las;

    las=pos[];

    for(int i=n;i>=;i--)

        if(vis[i]) las=i;

        else R[i]=las;

    for(int i=;i<=n;i++)

    {

        if(vis[i]) { ans[i]=s[i]; continue; }

        int Ld=(i-L[i]+n)%n,Rd=(R[i]-i+n)%n;

        if(min(Ld,Rd)>m)

            ans[i]= (s[i]=='W' ^ (m&)) ? 'W' : 'B';

        else

            ans[i]= (Ld<Rd) ? s[L[i]] : s[R[i]];

    }

    for(int i=;i<=n;i++) printf("%c",ans[i]); puts("");

    return ;

}