省选考的一塌糊涂，学了约半个月 whk。
模拟赛不知道有没有比较需要写的，看情况，更新可能很少，主要用来写题解。
目录2024.3.16
算是开始集训了，虽然还是不知道怎么训更高效点但是先暂时随便训训吧。实在想不到好办法。
把省选 D1T2 和 D2T1 补了。有点绷不住了。两题都没看题解就改完了，怎么说呢，略有点弱智吧。虽然以我场上的状态确实是做不完这两题了。
P10218 [省选联考 2024] 魔法手杖
考虑二分答案，假设最后答案 \(\ge v\)，那么所有值都需要 \(\ge v\)，注意到 \(a_i + x \ge a_i \oplus x\)，也就是说操作后一定更大，那么首先我们必须满足 \(a_i + x \ge v\)，否则答案一定不可能 \(\ge v\)。那么我们现在问题变成了，将所有 \(a_i \oplus x < v\) 的 \(i\) 加入 \(S\) 集合，然后看是否能满足 \(m\) 的限制，同时必须满足 \(x \ge v - \min a_i\)。我们记 \(v - \min a_i = l\)。
在 Trie 树上进行考虑，我们要把所有值全部异或一个 \(x\)，也就是将若干层的所有结点的左右儿子互换。考虑一层一层考虑，我们要统计的是 \(a_i \oplus x < v\) 的 \(b_i\) 和，假如当前 \(v\) 最高位为 \(1\)，那么注意到所有 \(a_i \oplus x\) 的最高位为 \(0\) 的值全部会被统计，也就是说左子树会全部统计上，然后再往右子树递归，同理，如果 \(v\) 最高位为 \(0\)，那么右子树全部不会统计，然后再往左子树递归。注意到我们每次只需要往一端递归，所以这样我们就可以得到子任务的结构了。我们可以确定 \(x\) 当前这一位填什么，如果填 \(1\) 那么就是交换当前点的左右子树，然后再根据 \(v\) 的值向左或向右递归。对于 \(x \ge l\) 的限制，我们类似于数位 DP 的处理方法，记录一下当前是否卡下界即可。那么这样我们就可以得到一个单次 \(O(n k)\) 的 DP 了。加上外层的二分，总复杂度 \(O(n k^2)\)。
二分答案看起来就不好优化，考虑优化 DP 的部分。发现问题在于 Trie 树上的二度点太多了，假如我们把它的二度点都压缩起来，点数就是 \(O(n)\) 的了，于是我们只需要把压缩 Trie 搞出来，然后每次能够快速计算一条链上的答案即可。计算链上的答案稍微比较麻烦，因为同时有左右子树、\(v\)、\(l\) 与卡下界这四个信息，不过通过一些精细的位运算处理可以快速计算出这一部分的答案。于是总复杂度就是 \(O(nk)\) 的了。
赛时我写了个 \(O(k(n+k))\) 的做法，我本来以为这和 \(O(nk)\) 是同阶的，但是没想到被出题人阴了一手，具体看 警惕 OI 中的多测陷阱。大概就是因为卡下界的信息处理太麻烦了，我赛时就想到，卡下界的只有一条链，那么把卡下界的暴力 DP，不卡下界的再去考虑就简单很多了，这样单次 DP 是 \(O(n + k)\) 的。唉，抽象了。虽然就算是不卡这个我赛时代码常数仍然很大，赛后又加了一些优化加剪枝才能把大样例跑进 1.5s。
P10220 [省选联考 2024] 迷宫守卫
赛时想这题的时候大脑确实不太活跃，跟我打模拟赛似的，过去半场了脑子才清醒
标签：2024.3,log,复杂度,右子,我们,ge,纪要,DP From： https://www.cnblogs.com/apjifengc/p/18082003