石环

GitHub跳转原题关系图返回列表

把环展成 s+s 并按相邻相同的断点切段;段内长为 m 的子串只有首尾可能冲突,用 KMP 的 border 链一次扣掉全部坏长度,得到 O(n)。

OJ: roj

题目 ID: 1699

难度:提高

标签:字符串KMPpython

创建: 2026-10-07 16:05

更新: 2026-10-07 16:05

形式化题目

给定一个长度为 nn 的环形字符串 ss(下标 00 起,字符集为 2626 个小写字母), 把它的位置看成 0,1,…,n−10, 1, \dots, n-1,且认为 n−1n-1 与 00 相邻。

若环上每对相邻位置的颜色都不同,称这个环是美丽的。一次操作允许拿走一段连续的 石头,长度记作 kk,kk 可以是 00(一个都不拿);剩下 m=n−km = n - k 个石头仍然按原来的 相对顺序围成一个环。

对每个 k∈[0,n−1]k \in [0, n-1] 回答:是否存在一种拿走恰好 kk 个连续石头的方案, 使得剩下的环是美丽的。把答案按 kk 从 00 到 n−1n-1 拼成一个长度为 nn 的 0101 串输出 (第 kk 位为 11 表示可行)。输入含多组数据,读到文件结束为止, 每组输出一行 Case i: 加这个 0101 串。

约束:组数不超过 66,1⩽n⩽1061 \leqslant n \leqslant 10^6。

注意 k=n−1k = n-1 时只剩 m=1m = 1 个石头,环里没有任何一对相邻的石头, 按定义"所有相邻对都不同色"是空真,因此 m=1m = 1 恒为可行。

正解

思路

朴素做法与它的瓶颈。 直接按定义检查即可:枚举 kk(等价于枚举剩下的长度 mm), 再枚举保留下来的弧的起点,花 O(m)O(m) 逐对验证相邻颜色是否不同以及首尾是否不同。 kk 有 nn 种、起点有 nn 种、单次检查 O(n)O(n),总计 O(n3)O(n^3);即使把"枚举弧"改成 “枚举起点 + 增量检查”,也只有 O(n2)O(n^2)。n=106n = 10^6 时这是 101210^{12} 量级,不可行。

慢的根源是同一个字符被反复比较:每个长度 mm 都要把整条弧重新扫一遍, 而"弧内部相邻是否不同"这件事其实与 mm 无关——相邻两个字符合法与否, 只取决于它在 ss 里的位置,跟这条弧取多长根本没关系。先把这一点利用干净,就能一次省掉一层循环。

关键观察一:破环成链。 令 s2=s+ss_2 = s + s(长度 2n2n)。因为 m=n−k⩽nm = n - k \leqslant n, 环上长度为 mm 的连续弧,与 s2s_2 中某个长度为 mm 的连续子串一一对应。 于是问题变成:s2s_2 上是否存在长度为 mm 的子串,满足

内部相邻位置都不同,首尾两个字符也不同.\text{内部相邻位置都不同}, \qquad \text{首尾两个字符也不同}.

关键观察二:相邻相同的位置是断点。 在 s2s_2 上,把所有满足 s2[i]=s2[i−1]s_2[i] = s_2[i-1] 的位置 ii 当作断点,它把 s2s_2 切成若干个极大段。每个段内部任意两个相邻字符都不同 (这正是"极大"的含义),所以段内任意子串都自动满足第一条约束,只剩下"首尾是否相同"要查。

关键观察三:首尾条件等价于 border。 设某段 TT 长为 LL,考察段内长度 mm 的子串。 段内长度 mm 的子串共有 L−m+1L - m + 1 个,它们由起点 p∈[0,L−m]p \in [0, L-m] 标号。 第 pp 个子串首尾相同的条件是 T[p]=T[p+m−1]T[p] = T[p + m - 1],也就是"TT 的从 pp 开始的、 长为 mm 的窗口两端相等"。这里有一个熟知的字符串等价:

T 的每个长为 m 的子串都首尾相同  ⟺  T 有周期 m−1  ⟺  T 有长度 L−m+1 的 border.T \text{ 的每个长为 } m \text{ 的子串都首尾相同} \iff T \text{ 有周期 } m - 1 \iff T \text{ 有长度 } L - m + 1 \text{ 的 border}.

L−m+1L - m + 1 恰好就是"子串个数",这个巧合是 KMP 能接手的原因。 于是段内所有长为 mm 的子串都坏掉   ⟺  \iff TT 有长度 b=L−m+1b = L - m + 1 的 border, 反过来 m=L−b+1m = L - b + 1。TT 的全部 border 长度就是它的 KMP 前缀函数 π\pi 的 border 链, 个数与 LL 同阶,链上的每个 bb 各贡献一个"坏长度"。注意这里只需要真 border (b<Lb < L,即 m⩾2m \geqslant 2)——b=Lb = L(m=1m = 1)虽然形式上成立, 但 m=1m = 1 时环里没有相邻对,按题意必须判为可行,所以 m=1m = 1 从不被扣掉。

把三段观察拼成算法。 只维护一个数组 res[1..n]res[1..n]:res[m]res[m] 表示"有多少个段可以取出 一个合法的长度为 mm 的弧",res[m]>0res[m] > 0 即可行。对每个段 TT(长 LL):

  1. 整体加一:只要 m⩽min⁡(L,n)m \leqslant \min(L, n),段内就有长为 mm 的子串,先乐观地加上 res[m]+=1res[m] \mathrel{+}= 1;
  2. 逐个扣掉坏长度:沿 π\pi 的 border 链取出每条真 border 长度 bb, 令 m=L−b+1m = L - b + 1,若 m⩽nm \leqslant n 则 res[m]−=1res[m] \mathrel{-}= 1。

第 1 步的"整体加一"如果逐项写就是 O(L)O(L) 次加法,所有段加起来是 O(n)O(n),已经足够。 最后对每个 kk 输出 res[n−k]>0res[n-k] > 0 的 0101 值即可。

样例 abab 的完整推演(n=4n = 4)。$s_2 = $ abababab,相邻字符两两不同, 所以它整体就是一个段,L=8L = 8:

ii(段内前缀长度) 1 2 3 4 5 6 7 8
前缀内容 a ab aba abab ababa ababab abababa abababab
π[i]\pi[i] 0 0 1 2 3 4 5 6

π[8]=6\pi[8] = 6,所以 border 链是 6→4→2→06 \to 4 \to 2 \to 0,三条真 border 对应 m=8−6+1=3m = 8 - 6 + 1 = 3、8−4+1=58 - 4 + 1 = 5、8−2+1=78 - 2 + 1 = 7;只有 m=3⩽nm = 3 \leqslant n 需要扣。 第一步对 m⩽min⁡(8,4)=4m \leqslant \min(8, 4) = 4 全部 +1+1,于是

mm 1 2 3 4
整体加一后 1 1 1 1
扣掉 m=3m = 3 后 res[m]res[m] 1 1 0 1

按 m=n−km = n - k 从大到小读出:k=0→m=4→1k=0 \to m=4 \to 1,k=1→m=3→0k=1 \to m=3 \to 0, k=2→m=2→1k=2 \to m=2 \to 1,k=3→m=1→1k=3 \to m=1 \to 1,答案是 1011,与样例一致。 m=3m = 3 被扣掉的原因可以直接看出来:abababab 里所有长度为 33 的子串只有 aba 和 bab 两种,首尾分别是 a/a 和 b/b,全部首尾同色。

几个必须照顾到的边界。

  • 全同色串:所有相邻位置都同色,s2s_2 处处是断点,每个段长 11, 只能提供 m=1m = 1,输出形如 00...01(数据点里 aaaa 给 0001、rrrrr 给 00001)。
  • n=1n = 1:kk 只有 00,m=1m = 1,答案为 1(样例 a)。此时没有相邻对, 与"m=1m = 1 恒可行"一致。
  • 段长可能超过 nn:s2s_2 的段最长可达 2n2n(例如 ss 全是由两种颜色严格交替时, s2s_2 相邻全部不同,只有一段长 2n2n)。此时长度 m⩽nm \leqslant n 的弧仍然取得到, 所以"整体加一"的上界取 min⁡(L,n)\min(L, n),而扣坏长度时也要判 m⩽nm \leqslant n, 否则会去扣一个根本不在 resres 定义域里的下标。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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 前缀函数的均摊代价为 O(L)O(L)(jj 每次循环至多 +1+1, 回跳总量不超过 +1+1 的次数),"整体加一"是 O(min⁡(L,n))O(\min(L,n)),border 链总长为 O(L)O(L), 三段相加仍是 O(L)O(L)。所有段长度之和为 2n2n,故每组数据 O(n)O(n), 最坏 6×1066 \times 10^6 的规模。实测最坏数据点 problem10(全同色串 + 严格交替串, 各 n=106n = 10^6,单段长 2n2n、border 链最长)C++ 约 0.06 s。
  • 空间:s2s_2 与前缀函数数组各 2n2n、resres 为 nn,均摊 O(n)O(n); C++ 用全局静态数组(MAXN = 10^6 + 5),实测峰值约 10 MB(限时 256 MB)。
  • 两种语言的关系:main.py 与 main.cpp 是同一算法的两种落地。Python 用生成器 ring_segments 按断点产出段、bad_lengths 产出坏长度,并用差分数组 (diff + itertools.accumulate)替代"整体加一"的逐项循环; C++ 直接用循环对 resres 逐项 +1+1,因为 O(n)O(n) 的加法在这个规模下毫无压力。 两者对全部 10 个数据点的输出逐字节一致。
  • Python 的时限风险:算法同为 O(n)O(n)、没有任何退化成暴力枚举的地方, 但纯 Python 循环在 6×1066 \times 10^6 字符上实测约 3.3 s,会超过本题 1000 ms 的限时。 这份 main.py 定位是教学短解法,实际提交请用同算法的 main.cpp。

总结

  • 先找出与参数无关的部分:朴素解每次换一个 mm 都要重扫整条弧, 但"内部相邻是否不同色"只由位置决定、与 mm 无关。把与参数无关的约束提前处理掉, 是本题从 O(n2)O(n^2) 掉到 O(n)O(n) 的第一步。
  • 环形问题的标准动作是破环成链:因为 m⩽nm \leqslant n,s+ss + s 上的长度 mm 子串 与环上的弧一一对应,写起来只多一个长度 2n2n 的数组。
  • "所有长为 mm 的子串都首尾相同"就是 border:这句话把 O(n)O(n) 个候选长度 一次压缩成 KMP 前缀函数的一条 border 链。b=L−m+1b = L - m + 1 这个换算关系的存在, 以及 border 链长度与 LL 同阶,是它能把复杂度压住的原因。
  • 只统计"是否存在",用计数比用布尔更好写:res[m]res[m] 记录"可行的段数", 整体加一后逐个扣坏长度,就不必为每个段维护一个布尔数组。
  • 边界要单独过一遍:m=1m = 1(环里没有相邻对,恒可行)、k=0k = 0(m=nm = n)、 全同色串(段长全为 11)、段长超过 nn(上界要取 min⁡(L,n)\min(L, n))四处都容易写错。

图示解析

下图用样例 abab(n=4n = 4)画出算法的两步:左边是断点切段与 KMP 的 border 链, 右边是 resres 数组上"整体加一、再扣坏长度"的差分过程。

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 链给出了全部坏长度,一个不多一个不少: 链上的 b=6,4,2b = 6, 4, 2 换算成 m=3,5,7m = 3, 5, 7,三者都要扣(只是 m=7>n=4m = 7 > n = 4 超出取值范围的先判掉);如果只沿链跳一步、只拿最长的 border b=6b = 6, 就会漏掉 m=5,7m = 5, 7,而这些长度在更大规模的段上同样会被用到。第二, 扣减必须发生在加一之后:res 的策略是"先乐观地认为每个 mm 都能取到, 再把确定坏掉的扣掉",顺序反了就无法用最简单的整体加一实现第一步。