A. Grasshopper on a Line

如果 ，直接走 ；否则走 。

B. Comparison String

令  为最长连续段长度，则答案是 。

显然答案至少是 ，因为长为  的递增/递减数列中每个数互不相同。

【资料图】

可以只用  到  的数构造数列，只需令每个转折处都是  或 。

C. Best Binary String

首先，对于确定的  序列，不妨开头加上 ，末尾加上 ，设相邻不同的字符有  对，则答案为 。这个结论只需注意到每次翻转只能将  减少 ，而最终变成 。方案是每次翻转第一个  到最后一个  的区间。

显然尽可能和前一个字符（开头是 ）相同是最优的。

D. Bracket Coloring

答案不超过 。答案是否为  只需判断  或  是否为合法括号序列。

构造答案为  只需贪心匹配合法的括号对，剩下的字符形如 )))(((，其翻转是合法括号序列。

E. Playoff Fixing

令 。编号为  到  的队伍的 seed 必须是  中各选一个。如果一个集合中两个数都被选则无解。否则假设有  个集合还没选数，则方案数为 ，其中  是第  个还没选数的集合中能选的数的个数。

确定这些队伍的编号后变成了大小为  的子问题，递归求解即可，复杂度为 。

F. F. Editorial for Two

枚举数列的一个分割点，则应当在前缀中选择  个数，后缀中选择  个数。

显然前后缀中都会选择最小的若干个数。前缀中选的数的和关于  递增，后缀递减，所以只有交点处的前后两个  可以成为答案。用数据结构维护选的数，二分  即可，时间复杂度 。

直接用 std::multiset在分割点移动的过程中维护选择的数可以做到 。