rank | solved | A | B | C | D | E | F | G | H | I | J | K |
---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 6 | O | . | . | O | O | O | O | . | . | . | O |
A
Solved by XLor (02:52, +1).
显然是一个二分题。
考虑单组询问的暴力做法,我们一个接着一个在 $S$ 串上滑动,遇到空位则检查串长,直到找到最终位置。
但是,单组询问的复杂度是 $O(k)$ 的,因为有可能每次都是递归到最深处。
考虑离线所有询问,对询问点排序(归并),批量递归处理询问。此外,我们不需要暴力在 $S$ 串上滑动,预处理前缀的空位符个数,即可 $O(\log n)$ 的时间内二分出递归点。
D
Solved by czswez and XLor (02:36, +4).
将数组划分为不降的段,先手玩家在数组内选择端点时,后手玩家因为要最大化因此一定是选择左右端点的最大值。因此,先手玩家的目标就是枚举数组中的每个点,最小化左右端点的最大值。观察到对于左端点,往右是递增的,对于右端点,往左是递增的,合并一下是一个单峰函数。函数只会在最值处出现阶梯状,其余一定是单调的。预处理一些前缀和,三分即可。
E
Solved by miaojie (03:00, +1).
F
Solved by XLor (04:55, +3).
显然有 $O(n^2k)$ 的 DP 做法,考虑决策单调性。
令 $f(i, j)$ 表示考虑到前 $i$ 个有 $j$ 个不选的最优解。
考虑对某个容量,观察决策点 $i+1$ 比 $i$ 优的话,后续就会一直是 $i+1$ 更优,抄一个整体二分的决策单调性。
注意,如果第二维是选的个数,不满足决策单调性,因为即使 $i+1$ 比 $i$ 优,后面因为个数的变化不一定会使用到这个信息。
G
Solved by miaojie (00:40).
nim 博弈。
K
Solved by miaojie and template (03:42, +3).
模板:求矩阵特征多项式。