Python 题解 【P1203 [IOI 1993 / USACO1.1] 坏掉的项链 Broken Necklace】Joyce_Charlotte原创

一、问题核心分析

1. 关键规则理解

• 项链是环形的，所以需要处理 “首尾相连” 的情况；
• 白色珠子w可以被当作任意颜色（红r或蓝b）；
• 打破项链后，从断点向左、右两个方向收集珠子：
  • 从一端开始收集同色（含 w），直到遇到第一个不同的非 w 颜色；
  • 另一端同理，且两端收集的颜色可以不同；
  • 总数是两端收集的数量之和。

2. 解题核心思路

二、完整代码（带详细注释）

python

运行

def max_beads(n, s):
# 1. 环形转线性：拼接字符串，处理首尾相连的情况
double_s = s + s
max_count = 0 # 记录最大收集数

# 2. 遍历所有可能的断点（共n个）
for i in range(n):
right_color = None
right_count = 0
for j in range(i, i + n):
current = double_s[j]
if right_color is None:
if current != 'w':
right_color = current
right_count += 1
else:
if current == right_color or current == 'w':
right_count += 1
else:
break
left_color = None
left_count = 0
for j in range(i – 1, i – 1 – n, -1):
current = double_s[j]
if left_color is None:
if current != 'w':
left_color = current
left_count += 1
else:
if current == left_color or current == 'w':
left_count += 1
else:
break

# 3. 计算当前断点的总收集数（不超过n，避免拼接后重复计算）
total = min(right_count + left_count, n)
# 4. 更新最大值
if total > max_count:
max_count = total

return max_count

n = int(input())
s = input().strip()
print(max_beads(n, s))

三、关键步骤逐句解释

步骤 1：环形转线性（double_s = s + s）

• 作用：将环形项链转为线性字符串，比如项链是brw（n=3），拼接后是brwbrw；
• 原因：断点在最后一个珠子（索引 2）后，等价于处理拼接后字符串的索引 3（即原索引 0），无需单独处理 “从末尾回到开头” 的边界情况，简化代码逻辑。

步骤 2：遍历所有断点（for i in range(n)）

• 作用：枚举所有可能的打破位置（共 n 个）；
• 原因：项链有 n 个珠子，就有 n 个 “缝隙” 可以打破，必须检查每一个位置才能找到最大值。

步骤 3：处理右侧收集（内层第一个 for 循环）

• right_color = None：初始化右侧主颜色（还未确定）；
• for j in range(i, i + n)：从断点 i 开始向右遍历，最多遍历 n 个珠子（避免超过项链总长度）；
• if right_color is None：还没找到主颜色时，只要是珠子就收集（w 也收集），直到遇到第一个非 w 颜色，将其设为主颜色；
• else：已确定主颜色后，只收集主颜色或 w，遇到其他颜色立即停止（break）。

步骤 4：处理左侧收集（内层第二个 for 循环）

• for j in range(i – 1, i – 1 – n, -1)：从断点 i 的前一个位置（i-1）向左遍历，步长为 – 1（向左）；
• 逻辑和右侧完全一致：先找主颜色，再收集同色 + w，遇到不同非 w 颜色停止。

步骤 5：计算总收集数（total = min(right_count + left_count, n)）

• 作用：避免总数超过 n（比如项链全是 w，左右收集数之和可能超过 n）；
• 原因：项链总共只有 n 个珠子，最大收集数不可能超过 n。

步骤 6：更新最大值（if total > max_count: max_count = total）

• 作用：记录所有断点中能收集的最大数量。

四、样例验证（输入 #1）

输入：

plaintext

29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

• 拼接后字符串为原字符串重复 2 次；
• 遍历每个断点时，计算左右收集数之和，最终找到最大值为 11（和样例输出一致）。

五、总结