前言

环是竞赛题当中一个比较常见的条件，在不同情况下需要不同的处理方法，最常见的是下标取余和破环成链，别的技巧因为涉及更多算法暂且不提，大家之后遇到可以自行整理归纳

第一节结束，大家应该基本掌握了语法，从本篇开始，基本不再放出具体的题目代码，只讨论思路和算法，或者给出部分核心代码，有些单纯练习，并没有新鲜技巧或者新内容引入的题也会跳过

题意

[Broken Necklace]

有一条由N个红色的，白色的，或蓝色的珠子组成的项链，要求在某点打破项链，展开成一条直线，从两端往里收集珠子，收集珠子的时候，一个被遇到的白色珠子可以被当做红色也可以被当做蓝色，每端收集珠子时当遇到不同颜色的珠子就停止收集，问能够收集到的最多的珠子数量

题目分析

首先有一个非常简单的思路，枚举每一个断点，然后往两边获取珠子直到不能获取为止，但是本题给出的是一个环，如果获取珠子的过程中跨越了n-1分界线，就要用取余来计算下一个位置，并且比较容易写错

这里有个比较好的方法就是，破环成链，这是一个非常常用的技巧，具体做法就是，将表示环的数组复制一遍，接在原来的数组后面，那么不需要跨越分界线，原来所有环的遍历情况在链上就能处理

但是在这里就会出现一个问题，如果往两边取珠子的过程在原来的环上会相遇，那么在链上，就会得到大于环长度的答案，这个其实是很好处理的，和链的长度取个min就可以了

以上的思路实现的时间复杂度是$O(n^2)$，相信大家在实现中应该不会遇到太大的困难

接下来我们考虑优化：答案应该是相邻的连续红色珠子和连续蓝色珠子(考虑白珠)之和的最大值

那么就不断地交替处理连续的红色珠子和蓝色珠子即可，我们以红色珠子为例，那么很容易想到的策略就是，将所有的白色和红色珠子统计进来，遇到蓝色珠子结束计数

但是我们在执行中，会发现一个问题

举个例子，如下的珠串

bbwrrrrwwwbbbbwwwrrrwwwrrrww

答案应该是由第二个红色串和蓝色串组成的，但是第2,3,4个w会在计算第一个红珠串的时候被划入红色珠串，所以，在统计红色珠串的时候，将遇到的所有白色珠串都算作红色的做法是不可行的，最后的白色珠串是需要复用的，因此还要统计最后一串连续的白色珠串

KEY CODE (以红色珠子为例)

1
2
3
4
5
6
7
8
9
10
11
12
13
if (isRed) {
    if (s[i] == 'b') {
        b = w + 1;
        w = 0;
        isRed = false;
    } else if (s[i] == 'w') {
        w++;
    } else {
        r += w + 1;
        w = 0;
    }
    ans = max(ans, r + b + w);
}

连续蓝色珠子部分和预处理部分请自行实现

任务清单

  • 实现朴素的$O(n^2)$做法
  • 优化算法的复杂度到$O(n)$
  • 学有余力的同学请用搜索算法完成此题