usaco-1.1.4 破碎的项链

题目描述

有一条长为 $n$ （ $1 \leqslant n \leqslant 350$ ）的环形项链，珠子颜色为 r（红）、b（蓝）、w（白），从环上某处顺时针读出一串颜色。在某个位置把环剪开拉直成一条线段，然后从两端各自向中间收集珠子：一端遇到的第一颗非白珠决定这一端收集的颜色（白珠可当作红或蓝），之后沿该方向一直收集同色（含白珠）的珠子，直到遇到一颗既非白色、也非该颜色的珠子就停下。任何一颗珠子只能被收走一次，两端合计不超过 $n$ 。问如何断开能使收集到的珠子数最多，输出这个最大值。输入格式：第一行一个整数 $n$ ；第二行一个长度为 $n$ 的颜色字符串。输出格式：一个整数，即能收集到的最大珠子数。

样例 #1：输入 8 + rwrrbbrw，输出 8。样例 #2：输入 29 + wwwbbrwrbrbrrbrbrwrwwrbwrwrrb，输出 11。

思路

把项链接成两倍长的直线串，这样枚举断点 $k$ 就变成"从位置 $k$ 出发的直线扫描"。白珠在两种颜色假设下属于不同的连续段，所以对"可当红"和"可当蓝"各预处理一套连续段的段首/段尾位置，再顺、逆两个方向各记一下第一颗非白珠的位置；于是每个断点处顺时针一端能吃到本色段的段尾、逆时针一端能吃到本色段的段首，各自一次查表 $O(1)$ 得到，逆时针一端还要用 $n - left$ 封顶防止与顺时针重叠，总复杂度 $O(n)$ 。整串全白时答案直接是 $n$ 。

参考代码

Python 版：

python

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87#!/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-01 02:48
# update_at: 2026-10-01 02:55

import sys


def run_edge(color: list[bool]) -> tuple[list[int], list[int]]:
    """求"可当某种颜色"的极长连续段的两端。

    `color[i]` 为 True 表示第 i 颗能当这种颜色（本色或白珠）。返回 `(start, end)`：
    `start[i]`/`end[i]` 是含 i 的那个连续段的首尾下标，`color[i]` 为 False 时两者
    都是 -1（该格不属于这种颜色）。
    """
    size = len(color)
    start = [0] * size
    for i in range(size):
        if not color[i]:
            start[i] = -1
        elif i and color[i - 1]:
            start[i] = start[i - 1]         # 与左邻同段，继承段首
        else:
            start[i] = i                    # 本色段从这里起头
    end = [0] * size
    for i in range(size - 1, -1, -1):
        if not color[i]:
            end[i] = -1
        elif i + 1 < size and color[i + 1]:
            end[i] = end[i + 1]             # 与右邻同段，继承段尾
        else:
            end[i] = i
    return start, end


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    s = next(data).decode()[:n]

    r = s + s                               # 项链是环：接成两倍当成直线扫
    total = 2 * n
    missing = total + 1

    # next_nonwhite[i]：i 起向右第一颗非白珠；prev_nonwhite[i]：i 起向左第一颗非白珠
    next_nonwhite = [missing] * (total + 1)
    for i in range(total - 1, -1, -1):
        next_nonwhite[i] = i if r[i] != 'w' else next_nonwhite[i + 1]
    prev_nonwhite = [-1] * (total + 1)
    for i in range(total):
        prev_nonwhite[i] = i if r[i] != 'w' else (prev_nonwhite[i - 1] if i else -1)

    # 白珠两色都算，所以"可当红/可当蓝"是两条不同的连续段序列
    as_red = [ch != 'b' for ch in r]
    as_blue = [ch != 'r' for ch in r]
    red_start, red_end = run_edge(as_red)
    blue_start, blue_end = run_edge(as_blue)

    best = 0
    for k in range(n):
        # ---- 顺时针：从 k 出发，遇白珠吸收，直到颜色冲突 ----
        first = k if r[k] != 'w' else next_nonwhite[k]
        if first >= total:                  # 全是白珠
            best = n
            break
        end = red_end if r[first] == 'r' else blue_end
        left = min(end[first] - k + 1, n)
        if left >= n:                       # 整条项链都能收走
            best = n
            break

        budget = n - left                   # 逆时针最多还能收这么多颗
        back = prev_nonwhite[k + n - 1]
        if back < 0:
            right = budget
        else:
            start = red_start if r[back] == 'r' else blue_start
            right = min(k + n - start[back], budget)
        best = max(best, left + right)

    print(best)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103// main.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-06 09:19
 * update_at: 2026-10-06 09:19
 */

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 355;       // n <= 350，两倍串长 <= 700
const int MAX2 = 2 * MAXN;

int n;                      // 项链珠子数
string r;                   // 项链接成两倍后的直线串，下标 0 ~ 2n-1
int next_nonwhite[MAX2];    // next_nonwhite[i]：i 起向右第一颗非白珠位置，没有则为 -1
int prev_nonwhite[MAX2];    // prev_nonwhite[i]：i 起向左第一颗非白珠位置，没有则为 -1
int red_start[MAX2], red_end[MAX2];     // "可当红"（本色红或白）连续段的首/尾下标
int blue_start[MAX2], blue_end[MAX2];   // "可当蓝"（本色蓝或白）连续段的首/尾下标

// 对布尔数组 c 求极长连续段两端：start[i]/end[i] 是含 i 的段首/段尾，c[i]=0 时为 -1
void run_edge(bool c[], int start[], int ende[]) {
    for (int i = 0; i < 2 * n; i++) {
        if (!c[i])
            start[i] = -1;
        else if (i && c[i - 1])
            start[i] = start[i - 1];    // 与左邻同段，继承段首
        else
            start[i] = i;               // 新段从这里起头
    }
    for (int i = 2 * n - 1; i >= 0; i--) {
        if (!c[i])
            ende[i] = -1;
        else if (i + 1 < 2 * n && c[i + 1])
            ende[i] = ende[i + 1];      // 与右邻同段，继承段尾
        else
            ende[i] = i;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> n >> s;
    r = s + s;                  // 项链是环：接成两倍当成直线扫，断点 k 对应起点 k

    // 顺 / 逆两个方向上第一颗非白珠的位置
    next_nonwhite[2 * n] = -1;
    for (int i = 2 * n - 1; i >= 0; i--)
        next_nonwhite[i] = (r[i] != 'w') ? i : next_nonwhite[i + 1];
    for (int i = 0; i < 2 * n; i++)
        // i == 0 时左边没有珠子，直接记 -1
        prev_nonwhite[i] = (r[i] != 'w') ? i : (i ? prev_nonwhite[i - 1] : -1);

    // 白珠两色都算，所以红、蓝各建一套连续段端点表
    bool as_red[MAX2], as_blue[MAX2];   // as_red[i]：第 i 颗可当红；as_blue 同理
    for (int i = 0; i < 2 * n; i++) {
        as_red[i] = (r[i] != 'b');
        as_blue[i] = (r[i] != 'r');
    }
    run_edge(as_red, red_start, red_end);
    run_edge(as_blue, blue_start, blue_end);

    int best = 0;
    for (int k = 0; k < n; k++) {
        // 顺时针：从 k 向右，第一颗非白珠锁定颜色，吃到该色段的末尾
        int first = (r[k] != 'w') ? k : next_nonwhite[k];
        int left;
        if (first == -1) {      // 整条项链全是白珠
            best = n;
            break;
        }
        if (r[first] == 'r')
            left = min(red_end[first] - k + 1, n);
        else
            left = min(blue_end[first] - k + 1, n);

        // 逆时针：从 k+n-1 向左收，颗数不超过 budget（与顺时针不重叠）
        int budget = n - left;
        int back = prev_nonwhite[k + n - 1];
        int right;
        if (back == -1)
            right = budget;     // 后半截全是白珠，budget 全收
        else {
            // 该珠锁定逆时针的颜色，吃到该色段的开头
            int seg_start = (r[back] == 'r') ? red_start[back] : blue_start[back];
            right = min(k + n - seg_start, budget);
        }
        best = max(best, left + right);
    }

    cout << best << endl;
    return 0;
}