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.