Lovely_CatHxy 和 Ghost_Huang 已经大战数 10 局了，全部都是 LCat 胜利！！！
都是 hxy 为什么偏偏你这么厉害呢（（（
CF1257F
tag：简单题 *2000
推一下式子，设 \((i,j)\) 表示前面选 \([1,i]\) 后面选 \([j,n]\)。式子里面就尽量不要写和 2 有关的了。
考虑分析 1 和 3 需要进入的点有多少个，然后再加上需要给 2 放多少个即可。
预处理 \(f(i)\)，扫描 \(j\)，维护前缀 min 的 \(f(i)\)，答案就是 \(\min\{ g(j)+ \min_{i<j} f(i)\}\)。
CF233B
tag：dp，贪心 *1900
一定要设计对状态：包含第 \(i\) 位能匹配到的最大位置。对于前后缀分别求一次。判定就是：要求所有 \(pre_i\ge nxt_i\)。
考虑如何转移，显然可以从上一个字符相同的位置转移过来。凭直觉：还需要考虑前面最大的匹配位置能否扩展，可以就更新。容易证明这样转移是充分的。
CF138D
tag：sg，dp，翻转坐标 *2500
说实话还是没有搞懂坐标怎么翻的。
CF1866D
tag：dp 优化 *2300
按列 dp。设 \(f(i,j)\) 表示前 \(i\) 列选了 \(j\) 个位置。钦定前面位置不能选了。转移考虑枚举 \(i+1\) 列选几个位置，单次转移平方。整体三次方。
考虑状态数优化，发现一个 \(i\) 的合法 \(j\) 范围是 \([i-k+1,i+k-1]\)，是 \(O(k)\) 级别的。直接暴力 map 记录状态即可。时间复杂度 \(O(nmk\log ?)\)。
CF1901E
tag：树形 dp *2200
独立写出了需要换根的还没有写换根的做法。但是要维护 4 个东西的 mx 和 mxx，太懒了所以去看题解了。
发现不换根可以做，只需要不钦定当前点必选。
具体地，这个题本质就是不允许 deg = 2 的点出现。考虑 \(f(x,j),j\in [0,3]\) 表示有几个儿子，3 表示大于等于。
\(x\) 这个点自己的点权在转移最后加上，注意 2 不能加。
注意从 \(to\) 到 \(x\) 的时候 \(f(to,2)\) 要加上 \(a_{to}\)，1 不能选自己，要减去。
CF1114D
tag：区间 dp *1900
不要看错题了。注意一开始选定了一个位置。
容易发现一个区间最后的颜色是 \(a_{l/r}\)，根据这个可以 \(O(1)\) 转移。
CF856D
tag：树形 dp，LCA，树上操作/差分 *2400
1 个月没写树了居然一发过了。
考虑对于每个可加边，在 LCA 处考虑他的贡献。
标签：Duel,min,位置,大战,tag,别样,考虑,转移,dp From： https://www.cnblogs.com/LCat90/p/18542845