Codeforces 842D – Vitya and Strange Lesson

题目链接:CodeForces – 842D

两个性质:

  • 第i次询问时异或$x_i$,第$i+1$次异或$r_{i+1}$,那么相当于$x_{i+1} = x_i \oplus r_{i+1}$。
  • 然后还有一个就是所有长度为$k$的二进制数如果是一个集合,这个集合中的每一个数异或一个相同的$k$位二进制数$p$,那么得到的结果还是这个集合。

我们要找到从0开始第一个没有出现的数。search的时候从高位开始找,我们一定希望这个高位优先是0,如果不能是0,才变成1。当前询问的值记录为tag,是0的条件是找tag对应位置相同的,是1的条件是找tag对应位置相反的。

我们看字典树那个对应位置的子树如果是满二叉树,那么根据第二条性质,说明所有以当前搜完的前缀为高位的二进制数都是存在的。这种情况就往tag对应位相反的那一个分支搜。如果不满,说明就在这个子树里面,往tag对应位相同的那一个分支搜。

 

说点什么

avatar
50
  Subscribe  
提醒