前言

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

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

题意

[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)$
  • 学有余力的同学请用搜索算法完成此题