把环展成 s+s 并按相邻相同的断点切段;段内长为 m 的子串只有首尾可能冲突,用 KMP 的 border 链一次扣掉全部坏长度,得到 O(n)。
OJ: roj
题目 ID: 1699
难度:提高
标签:字符串KMPpython
创建: 2026-10-07 16:05
更新: 2026-10-07 16:05
形式化题目
给定一个长度为
若环上每对相邻位置的颜色都不同,称这个环是美丽的。一次操作允许拿走一段连续的
石头,长度记作
对每个 Case i: 加这个
约束:组数不超过
注意
正解
思路
朴素做法与它的瓶颈。 直接按定义检查即可:枚举
慢的根源是同一个字符被反复比较:每个长度
关键观察一:破环成链。 令
关键观察二:相邻相同的位置是断点。 在
关键观察三:首尾条件等价于 border。 设某段
把三段观察拼成算法。 只维护一个数组
- 整体加一:只要
,段内就有长为 的子串,先乐观地加上 ; - 逐个扣掉坏长度:沿
的 border 链取出每条真 border 长度 , 令 ,若 则 。
第 1 步的"整体加一"如果逐项写就是
样例 abab 的完整推演(abababab,相邻字符两两不同,
所以它整体就是一个段,
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| 前缀内容 | a |
ab |
aba |
abab |
ababa |
ababab |
abababa |
abababab |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 整体加一后 | 1 | 1 | 1 | 1 |
| 扣掉 |
1 | 1 | 0 | 1 |
按 1011,与样例一致。
abababab 里所有长度为 aba 和 bab
两种,首尾分别是 a/a 和 b/b,全部首尾同色。
几个必须照顾到的边界。
- 全同色串:所有相邻位置都同色,
处处是断点,每个段长 , 只能提供 ,输出形如 00...01(数据点里aaaa给0001、rrrrr给00001)。 : 只有 , ,答案为 1(样例a)。此时没有相邻对, 与"恒可行"一致。 - 段长可能超过
: 的段最长可达 (例如 全是由两种颜色严格交替时, 相邻全部不同,只有一段长 )。此时长度 的弧仍然取得到, 所以"整体加一"的上界取 ,而扣坏长度时也要判 , 否则会去扣一个根本不在 定义域里的下标。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 16:05
# update_at: 2026-10-07 16:05
import sys
from collections.abc import Iterator
from itertools import accumulate
CASE_PREFIX = "Case" # 输出格式里的固定前缀,行号紧跟其后
def prefix_function(text: str) -> list[int]:
"""pi[i] = text[:i] 的最长真 border 长度(pi[0] = pi[1] = 0)。"""
pi = [0] * (len(text) + 1)
k = 0 # 当前已匹配上的 border 长度
for i in range(2, len(text) + 1):
while k > 0 and text[k] != text[i - 1]:
k = pi[k] # 失配就沿 border 链往回跳
if text[k] == text[i - 1]:
k += 1 # 接上了,border 长度加一
pi[i] = k
return pi
def bad_lengths(seg: str, n: int) -> Iterator[int]:
"""产出本段完全不可行的长度 m:段内所有长为 m 的子串首尾都相同。
段 T 有长度 b 的真 border 时,T 有周期 L-b,于是长度 m = L-b+1 的每个子串
首尾都相同;反之 m 不可行也一定对应一条 border,所以 border 链就是全部答案。
"""
pi = prefix_function(seg)
border = pi[-1]
while border > 0:
m = len(seg) - border + 1
if m <= n: # 只剩下 m <= n 个石头是有意义的
yield m
border = pi[border]
def ring_segments(s2: str) -> Iterator[str]:
"""把 2n 长的串按"相邻字符相同"的断点切开,产出每个极大段。"""
start = 0
for i in range(1, len(s2)):
if s2[i] == s2[i - 1]:
yield s2[start:i]
start = i
yield s2[start:]
def solve_case(s: str) -> str:
"""返回这组数据的答案串:第 k 位表示拿走 k 个连续石头后剩下的环能否美丽。"""
n = len(s)
# 差分数组:diff 前缀和的前 n 项就是 res[1..n],
# res[m] = "能取出合法的长度为 m 的弧"的段数,"整体 +1、坏长度扣 1" 用区间加实现。
diff = [0] * (n + 3)
for seg in ring_segments(s + s):
last_m = min(len(seg), n) # 本段能提供的最大剩余长度
diff[1] += 1 # m 不超过 last_m 时本段就取得到
diff[last_m + 1] -= 1
for m in bad_lengths(seg, n):
diff[m] -= 1 # 长度 m 在本段全部不可行
diff[m + 1] += 1
res = list(accumulate(diff))
# 第 k 位对应 m = n - k,所以按 m 从大到小读出答案
return ''.join('1' if res[m] > 0 else '0' for m in range(n, 0, -1))
def solve() -> None:
# 每组数据一行的字符串,EOF 结束;直接按空白切分即可原样拿到每个串
cases = sys.stdin.read().split()
out = [f"{CASE_PREFIX} {i}: {solve_case(s)}" for i, s in enumerate(cases, 1)]
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 16:05
* update_at: 2026-10-07 16:05
*/
// main.cpp:石环(ROJ 1699)。
// 题意:n 个石头围成环,可以有 0 个石头(n=1 时)以外的任意情况;
// 对每个 k(0 <= k <= n-1)判断能否拿走恰好 k 个连续石头(k=0 表示不拿),
// 使剩下的环中任意相邻两个石头颜色都不同。
//
// 算法(KMP 前缀函数 + 断点切段):
// 1. 把环展成 s2 = s + s(长度 2n)。拿走 k 个连续石头等价于在 s2 上取一段
// 长度 m = n - k 的连续子串当作剩下的环;因为 m <= n,子串起点可以落在
// [0, n-1] 内且不越出 s2。
// 2. s2 中 s2[i] == s2[i-1] 的位置是"断点",把 s2 切成若干极大段,段内任意
// 相邻字符都不同。于是段内长度为 m 的子串只需要再检查"首尾字符是否相同"。
// 3. 段 T(长 L)内所有长度为 m 的子串都首尾相同,等价于 T 有周期 m-1,
// 也等价于 T 有长度 L-m+1 的 border。T 的全部 border 长度就是 KMP
// 前缀函数的 border 链,于是这些坏的 m 只有 O(L) 个,可以逐个扣掉。
// 4. 每个段先把 m <= min(L, n) 的计数整体 +1,再对每条真 border 把
// m = L - b + 1 减 1;最终 res[m] > 0 即表示"剩 m 个石头"可行。
// 注意 m = 1 时环里只有 1 个石头,没有相邻对,恒为美丽,不会被扣掉。
// 5. 输出第 k 位对应 m = n - k。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000005; // n 的上限为 10^6,多留几个位置给 1-indexed 的下标
ll n; // 当前这组数据的环长 |s|
char s2[2 * MAXN + 5]; // 环展开得到的 2n 长串 s + s,字符值域小,用 char 省内存
int pi_arr[2 * MAXN + 5]; // KMP 前缀函数数组,处理每个段时复用:pi_arr[i] 是段内
// 前 i 个字符的最长真 border 长度(段内下标从 0 起)
int res[MAXN]; // res[m] 表示"能取出合法的长度为 m 的弧"的段数,>0 即可行
// 处理 s2 上的一段 [l, r](闭区间),它满足段内任意相邻字符都不同。
// 段内每个长度为 m 的子串只剩"首尾字符是否相同"这一个约束,
// 本函数把"本段对长度 m 可行 / 不可行"记进 res。
void process_segment(ll l, ll r) {
ll L = r - l + 1;
// 段内的 KMP 前缀函数:pi_arr[i] 是最长真 border 长度
pi_arr[0] = 0;
pi_arr[1] = 0;
int j = 0;
for (ll i = 2; i <= L; i++) {
j = pi_arr[i - 1];
while (j > 0 && s2[l + i - 1] != s2[l + j]) {
j = pi_arr[j]; // 失配就沿 border 链往回跳
}
if (s2[l + i - 1] == s2[l + j]) {
j++; // 接上了,border 长度加一
}
pi_arr[i] = j;
}
// 段内长为 m 的子串共有 L-m+1 个,只要 m <= min(L, n),本段就能提供长度 m 的弧。
// 这里只关心"是否存在",所以先用整体 +1 表示"本段可以提供",坏长度稍后逐条扣掉。
ll cap = min(L, n);
for (ll m = 1; m <= cap; m++) {
res[m]++;
}
// 段 T 有长度 b 的 border <=> T 有周期 L-b <=> 段内所有长度为 L-b+1 的
// 子串首尾相同,也就是长度 m = L-b+1 在本段完全不可行,扣掉它。
// border 链上的 b 恰是全部真 border 长度,故坏长度只有这么多。
j = pi_arr[L];
while (j > 0) {
ll m = L - j + 1;
if (m <= n) {
res[m]--;
}
j = pi_arr[j];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
int case_no = 0;
while (cin >> s) { // 多组数据,读到 EOF 结束
case_no++;
n = s.size();
for (ll i = 0; i < 2 * n; i++) {
s2[i] = s[i % n]; // 环展开
}
for (ll m = 0; m <= n; m++) {
res[m] = 0; // 只清本组实际用到的范围
}
// 按"相邻字符相同"的断点把 s2 切成极大段
ll l = 0;
for (ll i = 1; i < 2 * n; i++) {
if (s2[i] == s2[i - 1]) {
process_segment(l, i - 1);
l = i;
}
}
process_segment(l, 2 * n - 1);
cout << "Case " << case_no << ": ";
for (ll k = 0; k < n; k++) {
cout << (res[n - k] > 0 ? '1' : '0'); // 拿走 k 个后剩 m = n-k 个
}
cout << '\n';
}
return 0;
}复杂度
- 时间:每个段内部跑一次 KMP 前缀函数的均摊代价为
( 每次循环至多 , 回跳总量不超过 的次数),"整体加一"是 ,border 链总长为 , 三段相加仍是 。所有段长度之和为 ,故每组数据 , 最坏 的规模。实测最坏数据点 problem10(全同色串 + 严格交替串, 各,单段长 、border 链最长)C++ 约 0.06 s。 - 空间:
与前缀函数数组各 、 为 ,均摊 ; C++ 用全局静态数组( MAXN = 10^6 + 5),实测峰值约 10 MB(限时 256 MB)。 - 两种语言的关系:
main.py与main.cpp是同一算法的两种落地。Python 用生成器ring_segments按断点产出段、bad_lengths产出坏长度,并用差分数组 (diff+itertools.accumulate)替代"整体加一"的逐项循环; C++ 直接用循环对逐项 ,因为 的加法在这个规模下毫无压力。 两者对全部 10 个数据点的输出逐字节一致。 - Python 的时限风险:算法同为
、没有任何退化成暴力枚举的地方, 但纯 Python 循环在 字符上实测约 3.3 s,会超过本题 1000 ms 的限时。 这份 main.py定位是教学短解法,实际提交请用同算法的main.cpp。
总结
- 先找出与参数无关的部分:朴素解每次换一个
都要重扫整条弧, 但"内部相邻是否不同色"只由位置决定、与 无关。把与参数无关的约束提前处理掉, 是本题从 掉到 的第一步。 - 环形问题的标准动作是破环成链:因为
, 上的长度 子串 与环上的弧一一对应,写起来只多一个长度 的数组。 - "所有长为
的子串都首尾相同"就是 border:这句话把 个候选长度 一次压缩成 KMP 前缀函数的一条 border 链。 这个换算关系的存在, 以及 border 链长度与 同阶,是它能把复杂度压住的原因。 - 只统计"是否存在",用计数比用布尔更好写:
记录"可行的段数", 整体加一后逐个扣坏长度,就不必为每个段维护一个布尔数组。 - 边界要单独过一遍:
(环里没有相邻对,恒可行)、 ( )、 全同色串(段长全为 )、段长超过 (上界要取 )四处都容易写错。
图示解析
下图用样例 abab(
flowchart LR S["s2 = abababab, L = 8, 只有一个段"] --> B["pi[8] = 6"] B --> B2["border 链: 6 -> 4 -> 2 -> 0"] B2 --> M["坏长度 m = 3, 5, 7"] M --> F["只扣 m <= n = 4 的 m = 3"] S --> A["整体加一: res[1..4] = 1"] F --> R["res = [1, 1, 0, 1] (m = 1..4)"] A --> R R --> O["k = 0..3 -> m = 4, 3, 2, 1 -> 1011"]
观察重点有两个。第一,border 链给出了全部坏长度,一个不多一个不少:
链上的 res 的策略是"先乐观地认为每个