I. 早操
题目要意:有一个有个错误的01字符串,每次可以询问一个字符串和正确字符串不同的位置有几个,你需要回答正确字符串
预期通过数:3
实际通过数:4
关键词:交互,二分,字符串
感谢zyx和憧憬成为魔女的碳钾钨提供的idea
事实上,这个询问允许我们询问一些位置的错误个数和
具体的,我们需要将我们想询问的位置翻转(异或1),设翻转了个数,翻转前的字符串有个错误,返回的错误数为,则翻转的数中的错误数为
所以我们可以通过二分询问前缀错误个数,确定当前最后一个错误的位置,这样是单次的
只需要问次即可
根据idea提供人的说法,似乎存在一种二分递归的做法,但具体我也不会