【解题报告】Public Round #1
$\text{orzpb}$。
$\text{Public Judge}$ 的第一场比赛/se。
A. 删数
感觉掉大智了，想了好久都没想到/kk。
首先明显把序列差分，变成“若相邻元素均为 $x$，则可以将他们合并为 $2x$，求最多合并次数”。
由于操作要求元素相邻，和元素相对位置相关，自然想到尝试将序列按照一定特征划分，使得每段独立。一开始一直在想根据极小值之类的东西进行划分，但元素大小会因为合并变化，不好下手。
此时应该转而仔细观察操作形式，注意到做的事情只有将 $x\to 2x$，意味着若两个元素去掉因子 $2$ 之后不相等，那他们一定不能合并。这样就将序列成功划分了。
划分的目的在于简化形式。完成划分之后，我们就不关心除了 $2$ 之外的因子了。于是他们全都可以看作 $2$ 的幂。然后又可以转化为“若相邻元素均为 $x$，则可以将他们合并为 $x+1$，求最多合并次数”。且此处的 $x$ 只有 $\mathcal{O}(\log v)$ 级别。
此时已经很简洁了，考虑如何进行最优化。一个非常显然，但是我没有利用好的性质：最后序列中的一个数一定是原序列一段区间合成，一个暴力的想法就是设 $f(l,r,x)$ 表示 $l$ 到 $r$ 是否能拼成一个 $x$。这样暴力做可能是 $\mathcal{O}(n^2)$ 级别。
注意到 $f(l,r,x)$ 成立，一个必要条件是 $\sum_{i=l}^r 2^{a_i}=2^x$，于是对于固定的 $l$，可能的 $r$ 至多只有一个。于是就可以 $\mathcal{O}(n\log v)$ 地预处理并 $\text{dp}$ 了。
B. 守卫
首先，这相当于将图划分成若干联通块，每个联通块里有恰好一个标记点。然后求最小边权和。
非常显然，最后地每个联通块都是树。进一步，可以发现最后的边集 $\in$ $\text{MST}$ 的边集。可以用 $\text{MST}$ 的边来替换环上的边得到更优解。
于是，现在就将图转变成了森林，而森林和树没啥区别。有一个关键的性质：
“每个联通块里有恰好一个标记点”的最优解 $=$ “每个联通块里有至少一个标记点”的最优解。
如果一个联通块里有多个标记点，且标记点不重合，那明显可以通过断开更多的边得到更优的解。关键在于如果有标记点重合怎么办。
如果一组方案有解，至少要存在一组集合到点的匹配（否则标记点不可能两两不重合）。将一个重合的点拿出来，则一定存在一条增广路。增广路的意义在于，之前的标记点增广后还是标记点，但我们新增了一个标记点。
从这个角度貌似可以得到一个和拟阵相关的做法，但是我鸽了。
观察最后答案的形式，一定是将树拆成了若干森林，每个森林恰好一个标记点。把标记点看作根，那实际上就是给每个点确定一个父亲（或者把当前点确认为标记点）。考虑费用流，将点与连向他的边做匹配，$x$ 与 $(x,y)$ 匹配意味着 $x$ 的父亲是 $y$，当然还要加上将 $x$ 设为标记点的情况。
最后如果某一个点没有匹配，说明无解。如果某一个集合没有标记点，那么一定也是无解：这是因为根据上面的情况，如果不是无解，我们一定能找到一条增广路，从而多断一些边，得到更优解。