[IOI 1993 / USACO1.1] 坏掉的项链 Broken Necklace

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

枚举每个断点，分别向左右按颜色和白珠规则模拟收集，并用终点位置避免两边重复计数。

OJ: luogu

题目 ID: P1203

难度:普及-

标签:模拟环形处理USACO

日期: 2026-05-31 16:58

题意

给出一条由 r、b、w 组成的环形项链。

你可以任选一个位置断开，然后从断口向左右两个方向收集珠子。

每个方向都只能继续收集：

白色珠子 w
和当前认定颜色相同的珠子

问最多能收集多少颗。

思路

n 很小，直接枚举断点模拟就够了。

最直接的教学版写法如下：

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// brute.cpp：枚举断点并直接按规则双向收集珠子，作为教学版和对拍基准程序。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 405;

int n;
char a[MAXN];

int next_idx(int x) {
    x++;
    if (x > n) {
        x = 1;
    }
    return x;
}

int prev_idx(int x) {
    x--;
    if (x <= 0) {
        x = n;
    }
    return x;
}

int collect_clockwise(int x, int &end_pos) {
    char color = a[x];
    int cnt = 1;
    end_pos = x;

    for (int p = next_idx(x); p != x; p = next_idx(p)) {
        if (color == 'w' && a[p] != 'w') {
            color = a[p];
        }
        if (a[p] == color || a[p] == 'w') {
            cnt++;
            end_pos = p;
        }
        else {
            break;
        }
    }

    return cnt;
}

int collect_counterclockwise(int x, int end_pos) {
    if (x == end_pos) {
        return 0;
    }

    char color = a[x];
    int cnt = 1;

    for (int p = prev_idx(x); p != x && p != end_pos; p = prev_idx(p)) {
        if (color == 'w' && a[p] != 'w') {
            color = a[p];
        }
        if (a[p] == color || a[p] == 'w') {
            cnt++;
        }
        else {
            break;
        }
    }

    return cnt;
}

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

    cin >> n;
    cin >> (a + 1);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int end_pos = 0;
        int total = collect_clockwise(i, end_pos);
        total += collect_counterclockwise(prev_idx(i), end_pos);
        ans = max(ans, total);
    }

    if (ans > n) {
        ans = n;
    }
    cout << ans << '\n';
    return 0;
}

对于每个断点：

从断口右边顺时针收集；
从断口左边逆时针收集；
两边数量相加更新答案。

实现时要注意三件事：

核心公式

枚举断点 $cut$ 。设从断口顺时针最多能收集 $R(cut)$ 颗，逆时针且不与右侧重复时最多能收集 $L(cut)$ 颗，则这个断点的贡献是：

ans(cut)=\min\{n,\ R(cut)+L(cut)\}

最终答案为：

\max_{0\leqslant cut<n} ans(cut)

项链是环形，下标要能绕回；
白色 w 可以当任意颜色；
两边不能重复收集同一颗珠子，所以顺时针先记录终点，逆时针不能越过它。

公式解释：每个断点都独立计算一次左右两边最多能拿多少。两边相加可能超过整条项链长度，所以要和 n 取最小值；最后再对所有断点取最大值，就是最优断开位置。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 405;

int n;
char a[MAXN];

int next_idx(int x) {
    x++;
    if (x > n) {
        x = 1;
    }
    return x;
}

int prev_idx(int x) {
    x--;
    if (x <= 0) {
        x = n;
    }
    return x;
}

// 从 x 开始顺时针收集，并记录最后一个被收集到的位置。
int collect_clockwise(int x, int &end_pos) {
    char color = a[x];
    int cnt = 1;
    end_pos = x;

    for (int p = next_idx(x); p != x; p = next_idx(p)) {
        if (color == 'w' && a[p] != 'w') {
            color = a[p];
        }
        if (a[p] == color || a[p] == 'w') {
            cnt++;
            end_pos = p;
        }
        else {
            break;
        }
    }

    return cnt;
}

// 从 x 开始逆时针收集，但不能和顺时针部分重叠到 end_pos。
int collect_counterclockwise(int x, int end_pos) {
    if (x == end_pos) {
        return 0;
    }

    char color = a[x];
    int cnt = 1;

    for (int p = prev_idx(x); p != x && p != end_pos; p = prev_idx(p)) {
        if (color == 'w' && a[p] != 'w') {
            color = a[p];
        }
        if (a[p] == color || a[p] == 'w') {
            cnt++;
        }
        else {
            break;
        }
    }

    return cnt;
}

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

    cin >> n;
    cin >> (a + 1);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int end_pos = 0;
        int total = collect_clockwise(i, end_pos);
        total += collect_counterclockwise(prev_idx(i), end_pos);
        ans = max(ans, total);
    }

    if (ans > n) {
        ans = n;
    }
    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

总结

这题是典型的环形模拟题。

把环形下标、白珠规则和“不重复计数”这三件事处理好，代码就很稳定。

P1203 [IOI 1993 / USACO1.1] 坏掉的项链 Broken Necklace

题目描述

You have a necklace of $N$ red, white, or blue beads ( $3 \le N \le 350$ ), some of which are red, others blue, and others white, arranged at random. Here are two examples for $n=29$ .

The beads considered first and second in the text that follows have been marked in the picture.

The configuration in Figure A may be represented as a string of b’s and r’s, where b represents a blue bead and r represents a red one, as follows:

text

1brbrrrbbbrrrrrbrrbbrbbbbrrrrb

Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end. The two ends might not be of the same color as the beads collected before this.

Determine the point where the necklace should be broken so that the most number of beads can be collected. No bead can be collected more than once.

Example

For example, for the necklace in Figure A, $8$ beads can be collected, with the breaking point either between bead $9$ and bead $10$ or else between bead $24$ and bead $25$ .

In some necklaces, white beads had been included as shown in Figure B above. When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration can include any of the three symbols r, b and w.

Write a program to determine the largest number of beads that can be collected from a supplied necklace.

输入格式

Line 1: $N$ , the number of beads.
Line 2: a string of $N$ characters, each of which is r, b, or w.

输出格式

A single line containing the maximum number of beads that can be collected from the supplied necklace.

输入输出样例 #1

输入 #1

text

1
229 
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

输出 #1

text

说明/提示

Output Explanation

Consider two copies of the beads (kind of like being able to run around the ends). The string of $11$ is marked.

text

1
2
3
4
5
6
7
8Two necklace copies joined here
                     v
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb|wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
               ******|*****
               rrrrrb|bbbbb  <-- assignments
           5xr .....#|#####  6xb

                5+6 = 11 total

USACO Training Section 1.1.

[IOI 1993 / USACO1.1] 坏掉的项链 Broken Necklace

目录

题意

思路

核心公式

代码

复杂度

总结