题意
给定 $n$，你要猜一个长度为 $n$ 的 01 串。$n$ 是一个偶数。
每次你给出一个长度为 $n$ 的 01 串，如果
- 全部猜中，返回 $n$
- 你恰好猜中一半，返回 $\dfrac n2$
- 否则，返回 $0$
最多询问 $n + 500$ 次。
$2 \leq n \leq 1000$
题解
查看题解
随机至多 $499$ 次，找到一个二进制串 $S$，使得刚好才对一半。
然后把 $S_1$ 取反（0 变 1, 1 变 0）。
然后枚举 $2 \leq i \leq n$，把 $S_1$ 和 $S_i$ 取反后询问。如果得到 $\dfrac n2$，则表示 $S_i$ 和 $S_1$ 不同。否则说明 $S_i$ 和 $S_1$ 相同。
最后 $2$ 次，第一次尝试 $S_1 = 0$ 的情况。
若不成功，尝试 $S_1 = 1$ 的情况。
考虑随机 $499$ 次，恰好猜中一半的概率。
恰好对一半的 01 串的个数为 $n$ 个位置里选 $\dfrac n2$ 个取反的方案数，即 $\dbinom n{\dfrac n2}$。
每次猜中的概率就是
$$\frac{\dbinom n{\dfrac n2}}{2^n}$$
代入 $n = 1000$，每次猜中一半的概率大约是 $0.0252250181783608$。
为了方便下面的计算，我们设
$$f\left(n\right) = \frac{\dbinom n{\dfrac n2}}{2^n}\\g\left(n\right) = 1 - f\left(n\right)$$
精确计算猜 $499$ 次成功的概率：
猜 $499$ 次成功的概率就是 $1$ 减去猜 $499$ 次都不成功的概率，即
$$1 - g\left(n\right)^{499}$$
代入 $n = 1000$，概率是 $0.99999709408611$。相当高。
查看代码
// Please submit with C++17!
#pragma region HEAD // Spectre
#include <algorithm> // By rbtree (https://rbtr.ee)
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &__TEMP_READ_VALUE), __TEMP_READ_VALUE)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)
typedef long long tp;
tp __TEMP_READ_VALUE;
using namespace std;
#pragma endregion HEAD
////////////////////////////////////////////////////////////////////////////////
class RANDOM {
unsigned long long __seed, __coefficient;
public:
RANDOM() : __seed(217), __coefficient(17) {}
unsigned long long operator()(unsigned long long l, unsigned long long r) {
return rand() % (r - l + 1) + l;
}
} rd;
signed main() {
tp n = ra;
array<bool, 1003> a, diff;
function<tp()> q = [&]() -> tp {
for (tp i = 1; i <= n; ++i) {
printf("%lld", (tp)a[i]);
}
puts("");
fflush(stdout);
return ra;
};
while (1) {
for (tp i = 1; i <= n; ++i) {
a[i] = rd(0, 1);
}
if (tp x = q(); x == n) {
return 0;
} else if (x == n / 2) {
break;
}
}
a[1] ^= 1;
for (tp i = 2; i <= n; ++i) {
a[i] ^= 1;
diff[i] = q() == n / 2;
a[i] ^= 1;
}
a[1] ^= 1;
for (tp i = 2; i <= n; ++i) {
a[i] ^= diff[i];
}
if (q() != n) {
for (tp i = 1; i <= n; ++i) {
a[i] ^= 1;
}
q();
}
return 0;
}
////////////////////////////////////////////////////////////////////////////////