交互题。
有一个隐藏的 01 序列 \(a\) ，你只知道 \(a\) 的长度，并记为 \(n\) 。保证 \(a_1=0\) 。你可以执行以下操作：
- 询问一个序列 \(b\) ，满足两两不同且长度在 \([2,1000]\) 之间。交互库会返回 \(\sum[a(b_i)\not=a(b_{i+1})]\) 。
请在 \(226\) 次操作内求出 \(a\) 中 \(0\) 的个数。
\(2\le n\le 20000\) 。
算法一
对于每个 \(i\in[2,n]\) ，把下标 \(1\) 和下标 \(i\) 放在一个序列里做一次询问。
操作次数：\(19999\) 。
算法二
这个算法一看上去非常蠢，能不优化一下？
事实上，算法一可以直接求出所有 \(a_i\) ，而我们只要求 \(\sum a_i\) 就好了，感觉上就很浪费。
基于这个思路，考虑这样一种操作：每次询问 0 A 0 B 0 C 0 ... ，发现如果每个数是 \(0\) 就会贡献 \(0\) ，是 \(1\) 就会贡献 \(2\) ，那么把结果除以二就是 A B C ... 的和。
直接做仍然要 \(20000\) 次左右（因为一次还是只能做一个，就是算法一），但是我们可以先用算法一问出一些值，然后再做上面那个操作。记先做 \(B\) 次算法一，不难发现我们只要做 \(O(B+\frac nB)\) 次操作就可以问出所有数的和。于是我们就得到了一个 \(O(\sqrt n)\) 的做法。
还有一个小问题，就是可能我们会得到很多 \(1\) ，但是没有 \(0\) ，这时我们直接每次问 1 A 1 B 1 C 1 ... 就好了。所以需要问出 \(2B\) 个位置才保险。最后需要 \(2B+\frac nB\) 次操作，\(B\) 取 \(\sqrt {2n}\) 最优，此时是 \(2\sqrt {2n}\) 。
操作次数：
标签：...,le,sqrt,Mushrooms,算法,qoj1138,序列,操作,Counting From： https://www.cnblogs.com/Z-301/p/18173793