记录在这的都是感觉比较妙的或者看了题解的(
CF2155D Batteries
有 \(n\) 个元素,其中有 \(a\) 个是好的( \(a\) 未知)。
每次你可以询问一对元素,返回1当且仅当两个元素都是好的,否则返回0。
在 \(\lfloor\frac{n^2}{a}\rfloor\) 次询问内获得一次返回值为1。
多测,\(\sum n<=200\)。
首先,看似是交互题,实际上这种询问不能获得任何有效信息的,本质上是构造题。
关键观察:如果把序列头尾相连看作一个环,则环上存在两个好的元素,距离不超过n/a。
直接枚举距离 \(k\),然后枚举每一个元素 \(i\),询问元素 \(i\) 与 \(((i+k-1) \mod n) +1\)。