模拟赛考的,先手是知更鸟,后手是旅行者。

注意按位与有什么特点,假设现在是知更鸟:

  • xi=0,zi=1x_i=0,z_i=1 那么有 yi=1y_i=1 也就是 x<yx\lt y
  • xi=1,zi=1x_i=1,z_i=1 那么 yiy_i 是不确定的,考虑继续让旅行者去考虑。
    • 因为知更鸟并不知道 yiy_i 是什么,那么 xix_i 就肯定是 11,所以旅行者就可以推断出知更鸟是什么。
    • 如果 yi=0y_i=0 那么可以确定 x>yx\gt y
    • 否则 ii1i\gets i-1,继续进行第一个操作。

发现就是统计第一个 0101 或者 1010 的前面有多少个 1111,可以 n2n^2 枚举然后 logV\log V 判断,可以拿 6060 分。

显然可以放到一个字典树上进行操作,但是写完了 6060 之后发下我不会字典树,所以就糖丸了。