毕业了赶紧复健，不然队友都带不动我。
鉴定为普及组水平。
稍微难点的题先不开了！
CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)
D. Tenzing and His Animal Friends
首先不难想到要建个图。
对于一个选定的集合 \(S\)，对于所有满足 \(i\in S, j\not \in S\) 的边 \((i, j)\)，这次 game 的结果是将这些边的权值同时减同一个值。那么我们先使 \(S \leftarrow \{1, 2,\cdots, n-1\}\)，然后慢慢缩小这个集合。
每次遍历整个边集，将所有跨在 \(S\) 内外的边找出，game 时间就是这些边权的最小值。
每次至少缩掉一个点。复杂度 \(O(nm) = O(n^3)\)。
Submission #211053493 - Codeforces
E. Tenzing and Triangle
一个显然的结论：所有选择的三角形必定两两不交。因为出现这种情况的话就还不如直接合并，cost 只少不多而且面积更大。
然后考虑 dp。定义 \(f(i)\) 为消除所有 \(x \in [i, k]\) 的点所需最小代价。那么 \(i\) 从 \(k\) 到 \(0\)：
-
\(f(i) \leftarrow f(i-1) + \sum\limits_{x_j=i} c_j\)
表示 \(i\) 不用作任何三角形左边界。
-
\(f(i) \leftarrow f(j - 1) + (j - i)\cdot A + \sum\limits_{x_t\in[i, j], y_t\in[0, k-j)} c_t\)
表示 \(i\sim j\) 选个三角形。后面一串是三角形底下的点。
然后直接这样是平方级别的。尝试研究第二个式子进行优化：
这样拆开后，前面的两项只和 \(j\) 相关。然后对于后面一坨，注意到我们的 \(i\) 从 \(k\) 到 \(0\) 扫过来，其实 \(x_j\ge i\) 是没什么关系的，然后就也是只和 \(j\) 有关了。这些只和 \(j\) 有关的我们记一个 \(g(j)\)，然后每次搞出 \(g\) 中的最小值即可。
每次过掉一个 \(i\)，我们都加一个新的 \(j=i\)，然后把所有 \(x_t=i\) 的点都做一次对相应 \(g(j)\) 的更新。可以发现这是个区间加。线段树优化即可。\(O(n\log n)\)。
Submission #211090105 - Codeforces
Codeforces Round 881 (Div. 3)
E. Tracking Segments
单调性显然，越后面越可能 beautiful。
二分答案。
Submission #210720806 - Codeforces
F. Omsk Metro
因为边权是正负 \(1\)，所以对于一个路径，它的最大子段和以及最小子段和是 \(r, l\)，那么 \([l, r]\) 中的所有整数都是存在至少一条子段与之对应。从构造的角度解释：每次我们接一个 \(\pm 1\)， 新加入的是所有前/后缀，假如原前/后缀构成集合 \([l', r']\)，那么新的就是 \([l'\pm 1, r'\pm 1]\)，并入 \([l, r]\) 的话是不会断开的。
于是整个题就是树上链最大/小子段和问题。倍增/树剖等都可以。
Submission #210730221 - Codeforces
Codeforces Round 880 (Div. 2)
C. k-th equality
注意 \(C\) 要么 \(\max(A, B)\) 要么 \(\max(A, B)+1\)，否则无解。
枚举所有的 \(a\)，对于每个 \(a\)，计算出 \(b\) 的取值区间（根据 \(c\) 的上下界算），从而知道可以用的 \(b\) 的个数。如果合不到 \(k\) 就跳。
一旦合到了 \(k\)，枚举 \(b\) 即可。复杂度是 \(O(10^A+10^B)\)。
Submission #210193711 - Codeforces
E. Twin Clusters
值域 \([0, 4^k)\)。我们先看 \(2k\) 位的前 \(k\) 位：\(2^{2k}+1\)（含 0）个前缀中必定有重复，也就是说必定可以找 \(2^k+1\) 个前 \(k\) 位为 \(0\) 的区间。
算出这些区间的后 \(k\) 位 xor，必定又有一个重的。于是就找到了。