ARC 题目选做
ARC059
A. いっしょ
枚举选哪个数即可，暴力计算贡献。
B. アンバランス
记 \(sum_{i,j}\) 表示前 \(i\) 个字符中 \(j\) 出现的次数。
对于每个字母 \(i\)，一个区间 \([l+1,r]\) 满足条件当且仅当 \(sum_{r,i}-sum_{l,i}>\frac{r-l}{2}\)。
化简式子可得 \(2\times sum_{r,i}-r>2\times sum_{l,i}-l\)。
记录前缀最小值即可。
另一种思路：一种可行解中一定包含两个连续的字母或者两个相同字母中间夹着另一个字母，找是否有满足条件的即可。
代码
C. キャンディーとN人の子供
一道 DP 好题。
设 \(dp_{i,j}\) 表示前 \(i\) 个小朋友分到了 \(j\) 个糖果时的答案。
枚举当前小朋友分到了多少个糖果，利用前缀和转移即可。
代码
ARC062
A. AtCoDeerくんと選挙速報
计算现在的比例乘多少会超过以前的票数即可。
即：对于一个比例 \(t:a\)，已知之前计算出来的最少票数分别为 \(l\) 和 \(r\)，我们就是要求最小的 \(x\) 和 \(y\)，使得 \(t\times x\ge l\) 且 \(a\times y\ge r\)。
代码
B. AtCoDeerくんと変なじゃんけん
我们发现出布不会使答案变劣，只会使输的局数减少一或者赢的拘束增加一。
那么按照 石头 布 这样的顺序肯定就是最优解，正确性显然。
代码
ARC063
A. 一次元リバーシ
可以发现答案就是字符串中颜色段个数 \(-1\)。
代码
B. 高橋君と見えざる手
最优解一定是从某个点买进再从这个点之后的卖出收入最高的点卖出。
记录一下后缀最大值 \(suf_i\)，统计 \(suf_i - a_i\) 最大值的个数就是答案。
代码
C. 木と整数
开一个优先队列，每次取出已标号的最小的点，将它相邻的点的编号设为它的编号 \(+1\)，不合法就说明无解。可以证明这样做一定是最优的。
代码
ARC064
A. Boxes and Candies
贪心地想，两个相邻的点优先操作靠后的点，因为这样做还会影响后面一组对答案的贡献。
代码
B. An Ordinary Game
你会发现最终状态的奇偶性是确定的：
- 如果两端字符相同，那么最终状态就是奇数，类似于样例一（
aba）； - 如果两端字符不同，最终状态就会是偶数，类似于
abcd。
然后直接判断即可。
代码
ARC065
A. 白昼夢
直接递推即可。
代码
B. 連結
把道路和铁路看成两个图，答案就是统计有多少个点在两个图中都与当前点在同一连通块中。
代码
ARC067
A. Factors of Factorial
对于 \(1\sim n\) 的每一个数，分别统计它的质因子个数，然后根据约数个数定理计算。
代码
B. Walk and Teleport
直接遍历一遍取 \(\min\) 即可。
代码
ARC068
A. X: Yet Another Die Game
每次操作 \(6\) 和 \(5\) 最优。
代码
B. Card Eater
对于出现次数 \(\ge 2\) 的数，分类讨论一下：
- 如果是奇数，那么最终肯定会剩下一个数字；
- 如果是偶数，它还会影响一个别的数字，应优先选择出现次数 \(\ge 2\) 的数。
开一个 vector 记录一下出现次数 \(\ge 2\) 的数即可。
代码
C. Snuke Line
首先，对于每一个 \(d\)，\(\ge d\) 的线段一定会覆盖到，因此把这些线段先删掉，可以倒序处理。
然后用一个树状数组维护，对于每一个区间 \([l,r]\)，我们在 \(l\) 处 \(+1\)，在 \(r+1\) 处 \(-1\)，这也是一个差分的思路。
至于这样做为什么是对的？每一个线段长度已经 \(\le d\) 了， 它最多只会覆盖到一个点，因此这样做是正确的。
代码
ARC103
A. ////
分奇偶考虑，显然替换的数一定是整个序列的众数或者第二众数，讨论一下即可。
代码
C. Tr/ee
无解的情况当且仅当：
- \(s_1=0\) 或 \(s_n=0\)；
- \(s_i=1\) 且 \(s_{n-i}=0\)。
如果 \(s_i=1\)，我们就把当前节点向上伸出一个节点作为它的父亲；否则 \(s_i=0\)，我们就让当前节点增加一个儿子。
代码