Educational Codeforces Round 159 (Rated for Div. 2)
内容提要
A. 二进制不平衡：给定一个二进制字符串，判断在相邻字母之间插入01字符后是否可能有更多的0比1。解决方案计算0的数量，如果有任何0则输出“YES”，否则输出“NO”。 B. 获取积分：给定一个包含n天的学期，每天可以是学习或休息。学习可以获得l个积分，完成任务可以获得t个积分。任务每7天生成一次。解决方案计算需要学习的天数，以达到至少p个积分。 C. 插入和平衡：给定一个初始具有不同值的数组，添加一个值，然后执行t个操作，通过选择一个值并将x添加到它来执行。解决方案计算使所有值相等所需的最小操作数。 E. 折叠字符串：给定一组字符串，定义了一个函数C(a, b)。解决方案计算所有字符串对的C(s_i, s_j)长度之和。可以使用trie数据结构来实现。
延伸解读
题目A的判定逻辑
题目A要求判断经过任意次操作后，字符串中0的数量能否超过1。操作规则是：在相邻字符间插入，若相邻字符不同则插入0，否则插入1。文章指出，只要原字符串中存在至少一个0，就总能通过操作增加0的数量，从而输出“YES”；否则输出“NO”。这一结论基于操作可以不断在0旁边插入0来累积0的个数。
题目B的贪心策略
题目B中，学期有n天，每天可选择学习或休息。学习得l分，并可完成至多两个任务，每个任务得t分。任务每7天生成一个，第一个在第1天。目标是至少得p分，最大化休息天数。文章分析认为，由于任务生成频率低而每天可完成两个，所有任务最终都能完成，因此只需考虑最后需要多少天学习来凑够分数，从而最小化学习天数。
题目C的数学转化
题目C要求通过添加一个不同的值，然后执行操作（每次选一个值加x）使所有值相等，求最小操作次数。文章指出，若不考虑添加值，问题等价于找所有相邻差值的最大公约数作为x，然后计算每个值到最大值的步数。添加值需选择a_max - c*x且不与原数组重复，c尽可能小。代码中通过检查连续值是否覆盖所有步长来调整答案。
题目E的字典树应用
题目E定义函数C(a,b)折叠字符串，要求计算所有字符串对的C(s_i,s_j)长度之和。文章解释，这实质是求任意两个字符串前后重叠的部分。解决方案使用字典树：每个节点记录有多少字符串在此结束、多少经过此节点、以及子节点总字符数。然后遍历所有字符串，在字典树上查询匹配的后缀，从而高效计算总长度。
Q&A
Codeforces Round 159 的 A 题 Binary Imbalance 的解题思路是什么？
只要字符串中有 0，就输出 YES，否则输出 NO。因为可以在相邻不同字符间插入 0，从而增加 0 的数量。
B 题 Getting Points 中，如何计算最多可以休息多少天？
先计算任务总数 cnt = (n+6)/7，以及需要学习的天数 d = (cnt+1)/2。如果 d*l + t*cnt >= p，则学习天数为 (2*t + l + p - 1) / (2*t + l)；否则学习天数为 (p - cnt*t + l - 1) / l。最后用 n 减去学习天数得到休息天数。
C 题 Insert and Equalize 中，如何确定每次操作加上的值 x？
x 是所有相邻元素差值的最大公约数（gcd）。
C 题 Insert and Equalize 中，加入一个新值后，如何计算最小操作次数？
先计算原数组所有元素变为最大值所需的操作次数。然后尝试插入 a_max - c*x（c 尽可能小且不与原数组重复），并计算额外增加的操作次数。如果所有差值相同，则额外增加 n 次；否则从后往前找到第一个不满足等差的位置，额外增加相应次数。
E 题 Collapsing Strings 中，函数 C(a, b) 的定义是什么？
C(a, b) 递归定义：若 |b|=0 返回 a；若 |a|=0 返回 b；若 a 的最后一个字符等于 b 的第一个字符，则递归调用 C(a[1..|a|-1], b[2..|b|])；否则返回 a+b。
E 题 Collapsing Strings 中，如何高效计算所有字符串对的 C(s_i, s_j) 长度之和？
使用字典树（trie）。在每个节点记录有多少字符串在此结束、多少字符串经过此节点、以及子节点中的字符总数。然后遍历所有字符串，在 trie 中查询重叠部分，累加长度。
