上次图论还有一堆没写呢，怎么又来一个专题。

CF407D Largest Submatrix 3

考虑 $O(n^4)$ 做法，枚举左右端点然后双指针。
然后怎么优化？枚举 $u,l,r$ 表示上、左、右边界，能否快速求出下边界？
设 $dp_{u,l,r}$ 表示最大下边界，它可以从 $\min(dp_{u,l+1,r},dp_{u,l,r-1})$ 转移而来。
发现这里需要额外计算的限制是 $a_{u,l}$ 和第 $r$ 列、$a_{u,r}$ 和第 $l$ 列的重复计数。这可以开数组 $lst$ 优化转移。
复杂度 $O(n^3)$。非常逆天的是卡空间，要开 short。

CF559E Gerald and Path

这题数据测了五分钟。
首先对线段以左端点为关键字升序排序。
设 $dp_{i,j,0/1}$ 表示前 $i$ 条线段，最靠右的线段编号为 $j (j \lt i)$，它的朝向是左或右。
考虑转移，枚举 $i$ 后面线段的方向，由于选择的线段是一个前缀，所以要记录前缀最右线段的端点、长度、朝向等信息并转移。

CF868E Policeman and a Tree

设 $dp_{u,v,x,y}$ 表示警察从 $u$ 走向 $v$，$v$ 子树内有 $x$ 个罪犯，子树外有 $y$ 个罪犯。
考虑树上背包转移并记忆化优化。
终止状态为叶子节点，此时子树内所有罪犯全部被抓住，需要掉头抓其他子树的罪犯。
罪犯的最优策略是一定会跑到某个叶子节点，而警察的最优策略是向 $dp$ 最小的子树走。
不难写出状态转移方程，枚举是 $v$ 的前几个子树，第 $i$ 个子树内有几个罪犯。
统计答案需要枚举第一次往哪个方向走。

CF1830D Mex Tree

一道巧妙的树上背包。
题解。

CF1028G Guess the number

这不是若至题？然后发现 $k \leq x$ 红温了。
抽象交互题。考虑设 $dp_{t,i}$ 表示左端点为 $l$，还剩 $t$ 次查询机会，最多能确定的区间长度。
由于 $\gt 10000$ 的时候可以直接平均分，所以可以对 $10000$ 取最小值。
转移之后按照类似 DP 的转移模拟交互即可。

口胡

CF1993E

考虑一行的情况，相当于在后面加一个元素（所有元素的异或和），而操作相当于交换最后一个元素和前面一个元素。
行列是独立的，贡献可以分开算，所以下面以行为例，考虑枚举哪一列被替换成了异或和，然后相当于是一个 TSP（旅行商问题），状压即可解决。
那不就口胡完了，对行做一遍再对列做一遍即可。