比赛链接
Review
上周末的比赛，然后拖到现在才写博，就像喊了一周加训然后因为时间调不开没有任何进展！！！注定度过失败的人生！
前两个半小时算正常进度吧，过了 6 题也能识别出诈骗。
后面就开始降智，C 先往曾经模拟赛题想，发现用不了（赛后 Kaguya 指导一下好像能用了？）。J 也是很快曼哈顿转切比雪夫，也是很快放弃了，封榜后好久好久才有 \(O(1)\)，然后紊乱到式子一些独立的地方没注意到，然后就光荣下播了。
zzz 大神独立做出交互题，在封榜前拯救！！！
校内排名仅 15/23，快第二场了，加把劲！！！
Solution
A. Who Can Win
依题意模拟。
B. Creating Chaos
这题是很神秘的，因为输出 \(1\sim k\) 即可，证明感性理解就是扩大段不会变优。
C. Canvas Painting
不会贪心。
注意到连边一定是相邻更优（位阻更小云云），由于顺序任选，就一定能把一个连续段染成同色。（而非神秘顺序染成神秘结果）
那么把相邻看作 \(n-1\) 个位置，就是区间与点的二分图匹配。（此时狂写线段树优化建图，狂写不对）
后续牛子想了一个“最大流等于最小割！”的神秘线段树优化 DP。
以下是正解：枚举每个位置，选区间右端点最小的那个。可能的位置以区间左端点为主，如果还有区间可覆盖，再往右移动，否则直接跨到下一个左端点。
D. Min-Max Tree
考虑 DP，把贡献提前计算，\(f_{u,0/1,0/1}\) 表示 \(u\) 子树内进行一些划分，且 \(u\) 所在连通块有无最大/最小值，此时的最优结果。由于要求结果最大值，因此不必关心产生贡献的是否真的是最值，否则一定不优。转移实际就是简单讨论，某子树贡献最值。
G. Sorting
显然必须有 \((i,i+1)\)。
I. Knapsack Problem
比较诈骗，尝试能不能转成单源，发现同一方案下所用背包数相同。
J. Moving on the Plane
先考虑转成切比雪夫距离，\(x'=x+y,y'=x-y\)，这样好处是每次移动两维都是 \(\pm 1\)，而距离又是两维中的 \(\max \le k\)，所以可以分开考虑。
于是现在问题变为一维移动任意次，要求最终落在长度不超过 \(k\) 的区间内。显然计算过程中，贡献是若干段组合数和的累积，还需要考虑去重。这里很好的方法是直接 \(k\) 时答案减去 \(k-1\) 时答案，实际上每个小区间会被记录 \(k-len+1\) 次。
M. Teleporter
考虑直接 DP，一定存在走树边产生层内贡献的情况，注意到一次树上路径一定是先上后下，所以上下更新两次。