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)\) 了。或者直接打表都知道能过。