Codeforces Round 1064 (Div. 2)
A. Same Difference
给定一个长度为 \(n\) 的字符串 \(\{s_i\}\)，一次操作可以将 \(s_i\) 替换为 \(s_{i+1}\)。求最终使得 \(\{s_i\}\) 内每个字符都相同的最小操作次数。
显然最后一个字符无法被修改，那么只能将其他字符都改成最后一个字符。答案即为 \(\sum [s_i \neq s_n]\)。
B. Tab Closing
有一个长度为 \(a\) 的浏览器窗口，共有 \(n\) 个网页标签。当窗口有 \(m\) 个网页标签时，
用提供的模拟器试一下可以发现：
- 当 \(b \leq \dfrac{a}{m}\)，只需要把鼠标移到 \(b\) 处，一直原地点击就好了。
- 当 \(b > \dfrac{a}{m}\)，需要把鼠标移到 \(a\) 处，一直点击直到 \(b \leq \dfrac{a}{m}\)，在按第一类处理。
简单分讨，答案不会超过 \(2\)。注意第二类请可能有不需要移动的情况，即 \(a==b\)。
C. Cyclic Merging
给出一个环形数组，目标为通过合并将其变为一个数。
每次合并可以选择环上相邻的两个数 \(x\)、\(y\)，将两个数替换为 \(\max(x,y)\)，并花费 \(\max(x,y)\) 的代价。
求达成目标所需的最小代价。
谁知道因为没开 \(\text{long long}\) 导致我花了 \(1 \text{h}\) 来调试的痛，后面的题都没得写。
贪心，尽可能用较小的数来进行较多的合并操作。所以把数按从小到大的顺序删去，删去时选择和较小的一边合并。
合并的过程用双向列表维护就好了。
以下题目为赛后完成
D. Marble Council
给定一个大小为 \(n\) 的可重集 \(\{a\}\)，把 \(\{a\}\) 分成任意多个可重集 \(x_i\)，对于每个可重集 \(x_i\)，将其众数加入到可重集 \(S\)，求有多少种不同的可重集 \(S\)。
看得出是 DP。
首先，我们可以从一个数是否可能在可重集 \(S\) 中的角度思考。
考虑集合 \(S\) 合法的条件。
对于不在集合 \(S\) 中的元素 \(t\)，必须存在至少一种构造，使在每个 \(x_i\) 中，\(t\) 都不为众数。
实际上，只需要对于 $ \forall t \notin S$，都有 $ \sum_{c \in S} cnt_c \geq cnt_t $，就可以找到一种合法构造方案。
等价于满足 \(\sum_{c \in S} cnt_c \geq \max_{t \notin S}(cnt_t)\) 成立，进一步等价于 $\sum_{c \in S} cnt_c \geq \max(cnt) $ 成立。
（分讨 \(\max(cnt)\) 是否在集合 \(S\) 可轻松证明）。
那么这就是一个 01 背包问题，状态数组为 \(dp[ \sum_{c\in S} cnt_c ]\)。答案为 \(\max_{ i \in [\max(cnt),n] } dp[i]\)。
以下题目尚未解决