感觉考场上做这题还是挺聪明的
答案显然满足二分的性质。考虑枚举答案mid,如果mid满足要求,那么就要满足如下条件:
\[\sum_{a_{i}\oplus x <mid} b^{i}<m \]\[\forall i,a_{i}+ x >= mid \]因为如果你这个\(a_{i}\)如果不能满足异或,那么肯定就需要加。
第一个条件即为:被定向加强的水晶在秘术后的魔力值大于等于 mid(对于未被定向加强的水晶,由于 \(a+x=(a\oplus x)+2(a\oplus x)≥(a\oplus x)≥mid\),其也满足该不等式。
第二个式子可以变成\(min\{ a_{i} \}+x>=mid\)将这个作为二分下界即可。然后对于这里,我们要搞的问题就变成了,找到一个x,使第一个式子尽量小。使用01trie,假设当前走到u(顶着走)
先要保证\(x>=mid-min\{ a_{i} \}\)
如果有两个儿子:
1.当前mid这位为1,如果我这位填0,那么左子树肯定都小于了,那么就将左子树的\(sum b_{i}\)加上,那后向右子树递归。如果这位填1,那么右子树肯定都小于,那么就将右子树加上,向左子树递归。所以这个子树的最小答案就是
\(min(sumb[son[u][0]]+dfs(son[u][1]),sumb[son[u][1]]+dfs(son[u][0]))\)
2.当前mid这位为0,如果我这位填0,那么右子树肯定都大于了,那么就向左子树递归。如果这位填1,那么左子树肯定都大于,向右子树递归。所以这个子树的最小答案就是
\(min(dfs(son[u][0]),dfs(son[u][1]))\)
如果只有左/右儿子:
1.当前mid这位为1,肯定要让异或起来更大,所以要相反着填,所以最小答案就是\(dfs(son[u][0/1])\)
1.当前mid这位为零,那么如果相反着填,那么就肯定是大于了,返回0即可。
如果没有儿子了:
根据建树代码可知,这是走到底层的情况,因为是顶着走的,那么就返回0即可。
所以我们就进行二分,然后每次跑一边trie树,这颗trie树应该是不变的。
时间复杂度 \(O(nk^{2})\) 期望得分 72 pts
————————————————————————————————————————————————
考虑如何优化。因为这个在trie上跑一遍是不太可能优化的,那么考虑怎么优化二分。考虑优先让高位为1,那么mid这一位就是1,然后跑一遍dfs,看下\(sumb_{i}\)是否小于m,如果小于,那么答案这位就是1,否则就是0。然后我们又得到了一个 \(O(nk^{2})\)算法 期望得分 72 pts。考虑贪心,在子树内,若当前填1,后面全填0,是否有解。
引理:首先我将这位和这位以后的所有位都填成0,那么sumb就是0
如果有两个儿子:
当前mid这位为1,后面都为0,那么如果我x填了1,那么右子树肯定都小于了,然后左子树是顶着的,根据引理,答案是0。所以答案就是sumb[son[u][1]]。如果我x填了0,那么左子树肯定都小于了,然后右子树是顶着的,根据引理,答案是0。所以答案就是sumb[son[u][0]] 然后看两个的min是否小于等于m,如果是,代表可行,m就减掉,这位是1,然后往下递归,否则mid这位就是0,往下递归。
如果只有左/右儿子:
只要反着填,这位mid肯定是1。然后向下递归
如果没有儿子了:
根据建树代码可知,这是走到底层的情况,因为是顶着走的,那么就返回0即可。
然后这题就做完了