「NEERC 2015」Jump 题解
Link，Another Link。
一个长度为 \(n\) 的 \(01\) 串 \(S\) 被隐藏了起来，每次你可以询问一个 \(01\) 串 \(T\)，交互库会检测 \(T\) 与 \(S\) 的相同位数 \(k\)，若 \(k=\frac{n}{2}\) 或 \(n\)，他会直接返回，否则会返回零。
试在 \(n+500\) 次确定字符串 \(S\)。
Solution
考虑先求出一个 \(k=\frac n 2\) 的字符串，这个看起来一脸不可做的样子，我们考虑随机，每次随机一个字符串检验一下。
不难发现 \(k=\frac n 2\) 的字符串占比是 \(\frac{\binom{n}{\frac{n}{2}}}{2^n}\)，用 WolframAlpha 随便算一算，答案约为 \(0.0252\)，那么随机一次失败的概率 \(0.9747\) 的样子，那么随机 \(499\) 次，一定可以随到。
那么现在就有了一个 \(T\)，我们考虑将其第一位取反，接下来询问后面的所有位，每次考虑单次翻转一位，如果这位询问出来是 \(n/2\)，那么我们可以判断他和第一位所转换的方向相反，保留这一位。
最后留下串要么全对要么全错。
询问次数 \(n+500\)，复杂度 \(O(n^2)\)。
Code
const int N=1000;
int n;
mt19937 rng(time(0));
char ch[N+10],ans[N+10];
int query() {
for(int i=1;i<=n;i++) putchar(ch[i]);
cout<