CodeForces 1244F Chips

题意

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

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

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

分析

假设某个点在第一轮操作时不需要改变，然后以后其均不需要改变
假设某个点在第$x$轮操作后不需要改变，那么其两边的点至少会在第$x+1$轮操作后不需要改变。

先统计一开始不变的点，然后统计其他点不变的轮数，然后输出即可

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
int vis[maxn];
int l[maxn], r[maxn];
char s[maxn];

void solve() {
    int n, m;
    cin >> n >> m;
    cin >> (s + 1);
    memset(vis, -1, sizeof(vis));
    rep(i, 1, n)l[i] = i - 1, r[i] = i + 1;
    l[1] = n, r[n] = 1;
    queue<int> q;
    rep(i, 1, n)
        if (s[l[i]] == s[i] || s[r[i]] == s[i]) {
            vis[i] = 0;
            q.push(i);
        }
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (vis[l[now]] == -1)
            vis[l[now]] = vis[now] + 1, q.push(l[now]);
        if (vis[r[now]] == -1)
            vis[r[now]] = vis[now] + 1, q.push(r[now]);
    }
    rep(i, 1, n) {
        if (vis[i] > m || vis[i] == -1) {
            if (m & 1)
                cout << (char) ('W' + 'B' - s[i]);
            else
                cout << s[i];
        } else {
            if (vis[i] & 1)
                cout << (char) ('W' + 'B' - s[i]);
            else
                cout << s[i];
        }
    }
}

signed main() {
    while (T--)
        solve();
    return 0;
}