D. Red-Blue Matrix
赛时没看，发现 E 比 D 简单就一直在看 E。
显然列分割线是 \(O(m)\) 的，可以依次枚举。问题在于行的涂色方案是 \(2^{n}\) 种。
不妨考虑一下，有没有什么办法可以将其优化到 \(O(n)\) 呢？我们很容易想到对所有行进行排序预处理。这样的确是可行的，因为对于任意一种分割方案，只需要分别判断左右两个子矩阵的某个行集合 \(a\) 的最值和剩下的行组成的集合 \(b\) 的最值之间的大小关系，与行的顺序是毫无关系的。
因此，我们可以先只考虑让左子矩阵性质满足：将所有行按照开头元素大小升序排序（同时记录原来位置的映射），此时我们会发现：如果将某一行涂红色，那么它的下面所有行必须也涂成红色，不然下面未涂红的一行只能涂蓝，其首元素 \(\geq\) 这一行的首元素，性质不再满足（\(min_{红} > max_{蓝}\)）。也就是说，涂红色的行一定对应所有行的某个后缀。于是我们只需要 \(O(n)\) 枚举后缀端点就行了。这样，我们便做到了 \(O(nm)\) 枚举所有合法的涂色与切割方案，剩下的任务就是 \(O(1)\) 判断左右两个子矩阵是否均满足要求，也就相当于：
- 左子矩阵：\(min_{红} > max_{蓝}\)
- 右子矩阵：\(min_{蓝} > max_{红}\)
在枚举每个切割点前，分别对每一行做一下前缀最值的预处理就行了。具体实现见代码。
code
E. Arena
又双叒叕被 dp + 组合数学 类型题单杀了。赛时一直在纠结状态定义，想了半天想不出来。
这里记录多种做法，每一种做法的状态定义都不一样。
1 (官解)
\(dp_{i,j}\)：可以进行到 “还剩下 \(i\) 个人存活，且每个人已经承受了 \(j\) 点伤害” 这一状态，设置初始生命值 导致 死掉的所有人 的方案数（想不到，真想不到qwq）。显然 \(ans = \sum_{i=1}^{x} dp_{0,x}\)，初始时有 \(dp_{n,0}=1\)（注意这里初值并不是 \(x^{n}\)，因为状态转移决策的是每轮死掉的人的方案数，因此方案数应当体现在所有死掉的人身上。初始时无人死亡，方案数就是 1）。
状态转移部分见 code1。
感觉这个状态定义太抽象了。。。
code1
2
\(dp_{i,j}\)：有 \(i\) 个人，最大生命值为 \(j\)，最后存在赢家的方案数。显然 \(ans=x^{n}-dp_{n,x}\)，初始时有 \(\forall i \in [1, x], dp_{1,i}=i\)。
状态转移和上一种方法类似，都是决策每一轮死掉的人的情况，具体实现见 code2。
code2
summary
做出本题的关键是如何设置状态定义。而把哪些信息作为 dp 转移的状态，需要我们去衡量哪些信息在我们决策转移过程中的变化是简单清晰的。对于本题，关键的地方在于：每一轮前的存活人数 \(k\) 直接决定了当前这一轮所有人受到的伤害均为 \(k-1\)；而 “最大生命值” 这个状态定义的可行性也是因为这一点：所有人在每一轮受到的伤害是一样的，因此这一轮结束后的最大生命值也应当恰好减去这一轮的伤害值，变化是非常清晰的，可以作为 dp 数组里的其中一个维度；而另一个维度就是当前轮存活的人数。
这种题还是欠练。。。