D1T1 – P10217 [省选联考 2024] 季风
约定：令 \(a_i,b_i\) 代替原来的 \(x_i,y_i\)，避免变量重名。
显然地，考虑按 \(m\bmod n\) 的值分类，那么每一类都相当于若干个整段 \(+\) 一段前缀。
假设加上的是 \([1,i]\) 前缀，选了 \(m’\) 个整段，那么 \(a\) 的和可以表示为\(m’\times suma_n+suma_i\)，\(b\) 同理。现在考虑如何对于一个 \(m’\) check，注意到 \(a’,b’\) 是实数，于是不难猜测，有解当且仅当：
\[|m’\times suma_n+suma_i-x|+|m’\times sumb_n+sumb_i-y|\le (m’n+i) \]
注：\(m’n+i\) 是实际的 \(m\)。
于是做一点转化，令 \(x\to x-suma_i,y\to y-sumb_i\)，那么不难发现此时绝对值内的 \(suma_i,sumb_i\) 消失了。于是只需要分四段大力分讨即可。
注意到答案实际上相当于维护 \(\le 3\) 个形如 \(ax\le b\) 的不等式的解集。这个随便做就行，我赛时写繁了，用了一个 pair<int,int> 和 array<int,3> 存储最终的解集（可以直接维护左右端点，比较好写），同时细节也很多，比如我就挂了 \(60\text{pts}\)。
复杂度 \(O(n)\)，可以通过。
D1T2 – P10218 [省选联考 2024] 魔法手杖
看到异或这种东西，考虑按位确定答案。
先特判掉 \(\sum b_i\le m\) 的情况，此时答案就是 \(\min a_i+2^k-1\)。否则可以注意到至少一个数不会参与加法。换句话说，答案的位数不会超过 \(k\) 位。
直接做貌似并不好处理，考虑放在 01-trie 上考虑。
具体来说，设计一个函数 solve(p,bit,cost,mn,x,ans) 表示当前走到节点 \(p\)，要确定 \(x\) 与 \(ans\) 在第 \(bit\) 位的取值。同时加法部分已经花费了 \(cost\)，加法部分最小值为 \(mn\)。加法部分始终要满足 \(mn+x\ge ans\)。
如果走到了叶子（即 \(bit=-1\)），就直接用 \(\min(mn+x,ans)\) 更新全局答案即可。
否则，假设当前节点只有一个儿子，分成两种情况：
-
只有左儿子：此时我们令 \(x_{bit}=ans_{bit}=1\)。不难发现此时 \(x\) 和 \(ans\) 的相对大小是不变的，所以不会影响加法部分，直接递归
sovle(ls,bit-1,cost,mn,x|(1<<bit),ans|(1<<bit))即可。 -
只有右儿子：考虑令 \(ans_{bit}=1\)，此时 \(x_{bit}=0\)，两者的相对大小关系发生了变化，因此需要重新判定。考虑最好情况，\(ans\) 的 \([0,bit-1]\) 位全取 \(0\)，\(x\) 的 \([0,bit-1]\) 位全取 \(1\)，需要满足 \(mn+x+2^{bit}-1\ge ans+2^{bit}\)，化简得 \(mn+x>ans\)。此时递归
solve(rs,bit-1,cost,mn,x,ans|(1<<bit))。否则，只能令 \(x_{bit}=1,ans_{bit}=0\)。此时可以证明，剩下的位置都选 \(1\) 更优，并且最小值为加法部分。原因下文会证。此时令 \(ans\to \max(ans,x+2^{bit}-1)\)，并调用solve(rs,bit-1,cost,mn,x|(1<<bit),ans)即可。
然后是有两个儿子的情况。显然，我们尽量要使得 \(ans\) 的当前位为 \(1\)。由于有两个子树，所以必然要有一个子树全部划入加法操作，记这种操作为“删除”。
以删除左子树为例。此时有 \(x_{bit}=0,ans_{bit}=1\)。思考一下需要满足哪些条件：首先肯定要满足 \(sum_{ls}+cost\le m\)，并且要满足最好情况下加法部分的最小值可以超过更新后的 \(ans\)。为什么是最好？因为我们首先要满足这一位是 \(1\)（否则答案一定更劣），然后再考虑后面的位往最好情况靠拢，这样后面的更劣也无所谓。写成式子就是 \(\min(mn_{ls},mn)+x+2^{bit}-1\ge ans+2^{bit}\)，即 \(x\) 的后面全是 \(1\)，\(ans\) 全是 \(0\)，化简得 \(\min(mn_{ls},mn)+x>ans\)。由于加法一定大于异或，直接递归 solve(rs,bit-1,cost+sum[ls],min(mn,mina[ls]),x,ans|(1<<bit)) 即可。
删除右儿子也是类似的，这里还是写一下，此时 \(x_{bit}=1\)，需要满足 \(sum_{rs}+cost\le m\) 且 \(\min(mn_{rs},mn)+x+2^{bit}>ans\)，递归 solve(ls,bit-1,cost+sum[rs],min(mn,mina[rs]),x|(1<<bit),ans|(1<<bit))。
如果进行了删除就可以退出了。考虑没有进行删除的情况，假设某个儿子的异或和的 \(bit\) 位为 \(0\)，那么根据上文的说法，其应该被删除，纳入加法部分。但是该子树并不满足条件。假设其满足第一个条件（和不超过 \(m\)），但不满足第二个条件，那么我们可以让 \(bit\) 位为 \(0\)，更低位都为 \(1\)。此时加法部分一定比异或部分小，所以直接用加法部分更新答案即可。对于左儿子，就用 \(\min(mn_{ls},mn)+x+2^{bit}-1\) 更新答案，右儿子就用 \(\min(mn_{rs},mn)+x+2^{bit}+2^{bit}-1\) 即可。
否则，什么都不进行，正常递归即可。写出来就是 solve(ls,bit-1,cost,mn,x,ans) 和 solve(rs,bit-1,cost,mn,x|(1<<bit),ans)。
最后调用 solve(1,k,0,inf,0,0) 即可。
这样每个点只会被遍历到一次，时间复杂度 \(O(nk)\)，可以通过。
现在解答一下上面的问题：为什么只有右儿子且 \(ans_{bit}=0\) 的时候，加法部分最小？首先此时必然有加法部分（\(mn\) 初始值为 \(+\inf\)，那么必然不会进入这个分支）。根据上文的算法流程，加法部分和当前这条路径必定在某个高位处不同。如果是异或，那么这个高位必然为 \(1\)；否则，如果是加法，那么必然要经过若干次进位，最好情况下才是 \(1\)。所以直接用加法部分更新答案即可。
D1T3 – P10219 [省选联考 2024] 虫洞
D2T1 – P10220 [省选联考 2024] 迷宫守卫
题目要求最大化字典序，不妨先考虑考虑如何最大化第一个数。
考虑二分，每次二分一个数 \(mid\)，考虑 dp 求解，设 \(f_u\) 表示 \(u\) 子树内最多需要花费多少代价，使得第一个能到的叶子 只能是 \(q\ge mid\) 的点。
根据是否封锁当前节点讨论，有 \(f_u=\min(f_{ls}+f_{rs},f_{ls}+w_u)\)。这样只要 \(f_{rt}\le k\) 就合法。
然后这个东西也是可以直接 dp 的，具体就是把 \(mid\) 扔到数组第二维。但是需要离散化 \(+\) 归并排序转移才能保证复杂度，很不优雅。
然后假设第一个走到的是叶子 \(p\)，考虑将根到叶子的路径拿出来，显然剩下的部分会分成 \(O(n)\) 个子树。那么根据 dfs 的性质，最终的序列显然就是 \(q_p\) 加上这些子树按根的深度从大到小排序得到的序列依次拼接。于是问题变为了 \(O(n)\) 个规模更小的子问题，可以考虑递归。
但是还有一个问题没有解决：就是删掉这条路径之后，\(k\) 的变化。显然直接减掉根的 \(f\) 不一定是最优的，我们考虑什么时候可以做到更优。考虑路径上（不包括根）的每一个点 \(x\)：
-
\(x\) 是右儿子。此时其父亲显然是没有封锁过的（否则会从左兄弟下去，\(p\) 就不是第一个点了），也就是 \(f_{fa}=f_x+f_{lbro}\)。此时我们直接把左兄弟的 \(f\) 值加回到 \(k\) 里即可。
-
\(x\) 是左儿子：此时父亲可能被封锁过。首先如果没被封锁和上面是一样的，此时有 \(f_{rbro}\le w_{fa}\)。否则，我们考虑把 \(w_{fa}\) 加回去，也就是撤销掉这次封锁，这样可以使右兄弟的答案变大。但是加回去需要满足从右兄弟下去只能走到 \(>q_p\) 的点，否则从右兄弟下去最优解就不是 \(p\) 了。判断很简单，只需要检验是否 \(f_{rbro}\le k+w_{fa}\) 即可。
复杂度：设 \(T(n)\) 为解决高度为 \(n\) 的满二叉树所需的时间复杂度，有：
\[T(n)=O(n2^n)+\sum_{i=1}^{n-1}T(n-i) \]
然后随便分析分析就知道 \(T(n)=O(n2^n)\) 了。或者直接打表都知道能过。
