Educational Codeforces Round 146 (Rated for Div. 2)

B

• 如果直接想答案，显然不好想。但如果逆向思考，如果固定了最终腿的长度，一定是尽可能用最长，再在中途走一步来补足余数。即对于长度 m，则答案为 $\lceil\frac{a}{m}\rceil + \lceil\frac{b}{m}\rceil + m - 1$
• 去掉 ceil，发现即是一个简单的不等式在 $m = \sqrt{a + b}$ 时取等，因为有 ceil，所以是在附近取最小值，但不管怎样，验证到 1e5 肯定是足够了

---

• 这题也体现了不精确的算法在算法竞赛中的使用！！！
• 注意此题不能三分，因为有 ceil 不满足性质

C

• 贪心就好
• 显然一定先装填查找次数多的盒子，所以先排序
• 在以上的基础上，加入到耗时较少的机器人上

D

• 很妙的一道题，主要是对题目条件的处理很妙
• 首先判断题目一定有解
• 想让尽量多的武器不变，如果至少有一个没变，则可以以此为基准，发现最终范围一定在 $p_i - k \le p \le p_i + k$。题目的 n 和 k 的范围都不大，所以显然可以枚举一个不变的武器，再在此基础上（$p_i - k \le p \le p_i + k$）微操，选择一个 k 长度的范围，统计不同的武器有多少
• 注意到一个性质，如果要让一个武器的 $p_i$ 值改变，则要么改成比 $p$ 值较小的数，要么改成相对较大的数（对于枚举的一个 $p_{min}$ 一定不会更优），或者说根本不会改变。
• 统计区间内每个武器的出现次数以及不同武器的个数即可

E

• 找题目性质，发现如果要使一个点从右边交换到左边，则必有一个点从左边交换到右边。所以如果一个边如果会被遍历到，则至少两次，发现总存在一个构造方法使遍历次数达到最少的 2 次
• 所以对于原问题的一个子问题，如果边权不变时的最小值可以 DP 出来，用 f 数组表示前后选择多少
• DP 递推的限制是当前边要选，则前面边可选可不选；当前边不选，则前边必须选
• 而对于可变化边权（点权值改变），即是 DDP，可以在线段树上线性规划，线段树上一个结点表示的是区间 DP 结果，而维护的值具有可结合性，可由子节点递推父节点。最终答案即是前后边权都选择的值

F

• 可以将 $l_i$ $r_i$ 看作一个在一个时间段的操作，即可转化为线段树分治问题

• 因为原题有边限制，所以变为只有右边的才会连接。即是线段树分治加并查集维护关系

• 此题难点在于如何统计答案。到了叶子结点，显然 1 所在的集合结点都是可行的，如果 $O(n)$ 遍历查询显然会超时。

  此题妙在一步步回溯将集合的可行最后分解为点的可行。即如果合并时可行，则分解后的两个集合都可行。关键在于按照 dfs 序分治时，如果简单粗暴地 bool 标记，则会统计出错误答案。而此题很巧妙地运用了差分的性质，统计集合被标记的次数，父亲合并后的标记次数减去合并前的标记次数加上自己原有的标记次数才是真正的标记次数

  傻了，直接记录之前的 bool 状态，最后如果合并后被标记了，就标记；如果合并后没标记，就回溯