USACO (USA Computing Olympiad) 是知名的美国中学生信息学竞赛网站，网站内提供的算法问题由易到难，涉及的算法类型全面。
本文是 USACO Training Section 1.1 的问题解答。 Section 1.1 的大部分问题很基础，文章中重点探讨了 Broken Necklace 问题的三种解法。
我的 C++ 实现代码放在 USACO-Training-Solutions。
引言
实际工作中遇到的很多问题都能抽象成算法问题，算法能力实际上贯穿程序员职业生涯的始终。然而，对于算法（甚至是整个计算机学科）的学习而言，只通过理论的学习并不能让人得到对知识的完整认知。实践是学习过程中的重要一环，很多知识在实际运用中才能被深刻地理解与掌握。
在 OJ (Online Judge) 上做题是提高算法能力的一个实践途径。在此过程中，也经常能碰到令人眼前一亮的有趣问题，或是工作中实际面临的问题。
当然，在学习算法的同时，也不能降低编码的质量。在实现过程中，我不会特地去做常数上的优化，以尽量保持代码的可读性。
Your Ride Is Here
问题描述
有这样一种映射：给定一个字符串，将其所有字母所代表的数字相乘，并模 47，得到一个数。判断在此映射规则下，两个字符串得到的数是否相同。
分析解答
第一题自然很简单，模拟即可。
值得注意的是，问题描述中从字符串到数字的映射，其实就是一种 Hash。
另外需要注意的是，模 47 要在计算过程的每一步进行，避免因数字过大而造成溢出。
Greedy Gift Givers
问题描述
若干朋友互相各发一次红包，计算最后每个人的收入。
分析解答
模拟即可。
需要注意的是除数不能为 0，在编程过程中一定要对这类边界条件敏感，并做出处理。
Friday the Thirteenth
问题描述
统计 N 年内每个月的 13 号周一，周二，……，周日出现的次数。
分析解答
判断闰年，模拟即可。
Broken Necklace
问题描述
由红蓝白三种颜色的珍珠组成的项链，从中间某处断开，得到一条链子。分别从两端向中间收集珍珠，直至遇上与端点颜色不同的珍珠为止，特别地，遇到白色珍珠时不需要停止，可以继续收集。在这种情况下，试求可收集的珍珠的最大值。
分析解答
终于碰到需要思考的问题了，其实这个问题可以抽象成：在仅由 rbw 构成的循环字符串中，找到最长的形如 b … br … r 的子串。
在实际解决问题之前，为了方便处理，避免考虑首尾的循环问题，可以先把字符串 s 重复一次，得到 ss。
下面给出 3 种方法解决这个问题。
1. 暴力搜索
面对所有问题，最简单最直接的做法就是暴力搜索。在这个问题中，可以遍历每个位置，并从此位置分别往左往右统计字符，依此得到最长子串。
但是这个方法有 $ O(N^2) $ 的时间复杂度，能通过只是因为测试的数据规模太小而已。
2. 动态规划
USACO 的官方题解给出了一个时间复杂度为 O(N) 的动态规划方法，这个方法逐步计算出每个位置的左右两边的最长 r 子串和最长 b 子串长度。
以左边为例，对位置 i - 1， left[i - 1][0] 代表左侧的最长 r 子串长度， left[i - 1][1] 代表左侧的最长 b 子串长度。
则对位置 i， 根据字符串 s 中 s[i - 1] 的值，可以直接计算出 left[i][0] 和 left[i][1] 的值。
if (s[i - 1] == 'r')
{
left[i][0] = left[i - 1][0] + 1;
left[i][1] = 0;
}
else if (s[i - 1] == 'b')
{
left[i][1] = left[i - 1][1] + 1;
left[i][0] = 0;
}
else
{
left[i][0] = left[i - 1][0] + 1;
left[i][1] = left[i - 1][1] + 1;
}
由此，遍历所有位置，可以在 O(N) 的时间内计算出每个位置的左右最长子串长度，再用 O(N) 的时间求和，即可找到最长总子串长度。
3. 我的方法
动态规划的方法虽然已经把时间复杂度降到了 O(N)，但它在空间上引入了 O(N) 的复杂度。而我的方法在保持 O(N) 时间复杂度的同时，把空间复杂度降到了 O(1)。
直观地考虑这个问题，在不考虑 w 字符的情况下，原字符串应该由 r 串与 b 串交替构成。在这种情况下，只需要遍历一遍字符串，计算出每组相邻的 r 串与 b 串的长度和即可。
问题中引入的 w，实际上充当了 r 串与 b 串的公共部分，但我们仍然可以沿用这个思路来解决问题。
我们先定义两个概念。
- c 子串：全部由字符 c 和 w 构成的子串。
- 极大 c 子串：若一个 c 子串的前一个字符与后一个字符不是 c 或 w， 则称它为极大 c 子串。
事实上，原字符串由极大 r 子串 与极大 b 子串 交替构成。我们只需要求出相邻的极大 r 子串 与极大 b 子串的合子串的长度最大值。但是，合子串的长度并不简单等于两个子串的长度之和，因为极大 r 子串 与极大 b 子串可能产生重合部分，重合部分为极大 w 子串。
考虑一段相邻的极大 b 子串与极大 r 子串，局部的字符串形如
r1 … b1 … b2 … r2 … r3 … b3
其中，在 r1 和 r2 之间是一个极大 b 子串， b1 是这个极大 b 子串的第一个 b 字符， b2 是其最后一个 b 字符，换言之， r1 与 b1 之间， b2 与 r2 之间只有 w 字符。
同理，在 b2 和 b3 之间是一个极大 r 子串， r2 是其第一个 r 字符， r3 是其最后一个 r 字符。
那么这一段极大 b 子串与极大 r 子串 的合子串长度为 b3 - r1 - 1。
接着考虑下一组相邻的极大 r 子串与极大 b 子串，下一个局部字符串形如
b2 … r2 … r3 … b3 … b4 … r4
同理可得这一段合子串长度为 r4 - b2 - 1。
通过上面的分析可以看到，我们只需要在遍历一遍原字符串的过程中，维护 6 个关键点的数据，就可以得到所有合子串长度，并找到其中最大值。
while (FindNextColorIndex(necklace, pointIndex))
{
int length = pointIndex[5] - 1 - pointIndex[0];
maxLength = maxLength > length ? maxLength : length;
for (int i = 0; i < 4; ++i)
{
pointIndex[i] = pointIndex[i + 2];
}
}
在维护过程中，每次需要找到两个新的关键点，这就是 FindNextColorIndex 的功能。
bool FindNextColorIndex(const string &necklace, int pointIndex[])
{
char color = necklace[pointIndex[3]];
char stopColor = color == c_color1 ? c_color2 : c_color1;
for (int i = pointIndex[3]; i < necklace.length(); ++i)
{
if (necklace[i] == color)
{
pointIndex[4] = i;
}
else if (necklace[i] == stopColor)
{
pointIndex[5] = i;
return true;
}
}
return false;
}
这样，就以 O(N) 的时间复杂度， O(1) 的空间复杂度解决了问题。