题解

admin 2024-12-21 18:52:20

I. 早操

题目要意:有一个有个错误的01字符串,每次可以询问一个字符串和正确字符串不同的位置有几个,你需要回答正确字符串

预期通过数:3

实际通过数:4

关键词:交互,二分,字符串

感谢zyx和憧憬成为魔女的碳钾钨提供的idea

事实上,这个询问允许我们询问一些位置的错误个数和

具体的,我们需要将我们想询问的位置翻转(异或1),设翻转了个数,翻转前的字符串有个错误,返回的错误数为,则翻转的数中的错误数为

所以我们可以通过二分询问前缀错误个数,确定当前最后一个错误的位置,这样是单次

只需要问次即可

根据idea提供人的说法,似乎存在一种二分递归的做法,但具体我也不会