2022/10/25 做题记录

Posted on Disqus:

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.