题目传送门
题意
有一个大小为 \(n\) 的环，环上每个点有一个颜色（黑/白）。定义一次操作是，对于每个点 \(i\)，若他和他相邻的两个点中，白点多于黑点，则在新的环中， \(i\) 变成白色，否则变为黑色。
求进行 \(k\) 次操作后每个点的颜色。
\(n\le 2\times 10^5,k\le 10^9\)
题解
变色的条件相当于 \(i\) 相邻两个点的颜色都与 \(i\) 的颜色不同。对于一段长度 \(\ge 2\) 的颜色相同的段，显然颜色是永远不会变的。只有这样的段之间的这些颜色交替改变的点的颜色会发生变化。例如 WWWBWBWBWBBB -> WWWWBWBWBBBB -> WWWWWBWBBBBB -> WWWWWWBBBBBB。
考虑中间的颜色交替改变的一段（如上例中 BWBWBW），发现每进行一次操作，两边的点会向两边的颜色相同的连续段合并，中间的点会改变颜色。记这样的段中某个点 \(i\) 到两边颜色相同连续段的距离是 \(a_i,b_i\)，那么他会在第 \(\min(a_i,b_i)\) 次操作被合并，颜色要看两边段的颜色和具体往哪边合并，被合并之后颜色就不会再变化，而在被合并之前颜色则是交替变化。所以只要根据 \(k\) 和 \(\min(a_i,b_i)\) 的大小进行讨论即可。
要注意的是，可能题目给定字符串的最前面一段和最后面一段是可以拼起来的，所以要对顺序进行一定的调整。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <cstdio>
#include <algorithm>
#define N 400005
int n, k, d, dis1[N], dis2[N];
char a[N], b[N];
bool check(){
if (n & 1) return 0;
for (register int i = 2; i <= n; ++i)
if (a[i] == a[i - 1]) return 0;
return 1;
}
int main(){
scanf("%d%d%s", &n, &k, a + 1);
if (check()){
if (k & 1) std :: reverse(a + 1, a + 1 + n);
return printf("%s", a + 1), 0;
}
for (register int i = 1; i <= n; ++i) a[n + i] = a[i];
for (register int i = n + 2; i < (n << 1); ++i)
if (a[i - 1] != a[i] && a[i] != a[i + 1]) continue;
else{ d = i - 1; break; }
if (!d) d = (n << 1) - 1;
for (register int i = d - n + 1; i <= d; ++i)
if (a[i - 1] != a[i] && a[i] != a[i + 1]) dis1[i] = dis1[i - 1] + 1;
else dis1[i] = 0;
for (register int i = d; i > d - n; --i)
if (a[i - 1] != a[i] && a[i] != a[i + 1]) dis2[i] = dis2[i + 1] + 1;
else dis2[i] = 0;
for (register int i = d - n + 1; i <= d; ++i)
if (a[i - 1] != a[i] && a[i] != a[i + 1])
if (k >= std :: min(dis1[i], dis2[i]))
if (dis1[i] < dis2[i]) b[i] = a[i - dis1[i]];
else b[i] = a[i + dis2[i]];
else b[i] = a[i] == 'B' && (k & 1) || (a[i] == 'W' && (k & 1 ^ 1)) ? 'W' : 'B';
else b[i] = a[i];
for (register int i = 1; i <= d - n; ++i) putchar(b[i + n]);
for (register int i = d - n + 1; i <= n; ++i) putchar(b[i]);
}
|
