• https://codeforces.com/contest/1750
• https://t.me/algorithm_daily_of_minako/7364

Problem B. Elimination of a Ring

比赛的时候第一反应是 SPOJ. MUSKET，做法是破环为链 + O(n3) 区间 dp。（连数据范围也颇具迷惑性 Orz。。。）
不过感觉不太对劲… 因为求的是最大。。。那么如果有一个孤立元素，那么一定可以倚靠着这个元素作为墙，答案为 n。
进一步，我们可以证明，只要有大于等于 3 种以上元素，都可以最后归约到这种情况，答案同样为 n。
因此只剩下两种元素的情况，但是两种元素时 pattern 是固定的。。。是 1 2 1 2 … 答案为 n/2 + 1。

Problem D. Carry Bit

这个题 O(nk) 类 Pascal dp 很好想也好写，但是对我们解这道题并没有用，因为我们不知道怎么优化，
即使是更简单的情况，比如如何从组合数的递推公式直接得到通项解对我来说也是非常困难的。
（Induction 当然不算。）

所以看到这个范围应该直接考虑组合方法。
首先我们可以得到一个 raw 的公式。。。。Binom(n, k) * p3[n-k]。。
这个公式的问题是，对于一些连续出现的进位位置，不需要两个 1,。。因此我们少算了。
所以我们需要枚举有多少连续的 1。。而这等价于枚举 1 可以分成多少段。
大概这样 // ...
枚举之后，先固定上图位置的这些 0/1 状态，我们还需要讨论左边的 . 存不存在。。。
剩下就是有很多 * 和很多 . 需要丢到这些空里。。。那么就是经典的插板法。。
剩下就很 trivial 了。

Problem E. Make It Connected

1. 连通图,ans=0.
2. 分出几个联通图，如果其中有不是完全图的，ans=1
3. 如果全是完全图，如果是2个，那么小的那个全翻，ans=min.
4. 3个或以上的完全图，先随便翻一个，然后就变成2的情况了，ans=2

每一步都很 trivial（可能 2 稍微难一点，因为还要找判定条件，判定条件时，只要不是满度的，且没有一个挂载的叶子即可），连起来还是很难的。。。

Problem F. Anti-median (Easy Version)

开始上强度了。。。