2022/10/25 做题记录
D
http://47.92.197.167:5283/contest/270/problem/4
连成一个环就相当于给每一个点找一个出边连到的点匹配,
首先二分答案,这样的限制就是每个点和它的匹配点异或大于 mid
,在 trie 上 dfs,dfs(x,y)
表示 x
子树内的点和 y
子树内的点匹配,x
子树至少有多少个无法匹配(返回值为这个数的相反数)。
-
如果
mid
的下一位为1
,那么x
的左子树必须和y
的右子树匹配,x
的右子树必须和y
的左子树匹配。 -
如果
mid
的下一位为0
,那么任何一个极大匹配要不就是y
内的点全被匹配,要么就是x
至多有一个子树内有没有匹配的点,因为如果y
内还有点,那么x
的左右子树中至少有一个点可以匹配后通过这一位就使异或值大于mid
。首先将
ans
设为min(0,siz[y]-siz[x])
(这是y
全被匹配的答案, 真实答案一定不大于它),之后就考虑贪心的尽量匹配左子树或者右子树,答案就是它们的min
(因为最后的匹配一定把另一棵子树匹配满得到的(因为这一边已经无法加点了),所以不用考虑另一棵子树的匹配)
有点卡常,需要一些剪枝什么的,比如在贪心的时候发现一定能匹配就不向下 dfs
.