「NEERC2015」Jump 题解

LinkAnother 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<<endl;
	int ret;scanf("%d",&ret);
	if(ret==n) exit(0);
	return ret;
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=499;i++) {
		for(int j=1;j<=n;j++) ch[j]=rng()%2+'0';
		int Q=query();
		if(Q==n/2) break;
	}
	ch[1]^=1;
	ans[1]=ch[1];
	for(int i=2;i<=n;i++) {
		ch[i]^=1;
		int Q=query();
		if(Q==n/2) ans[i]=ch[i]^1;
		else ans[i]=ch[i];
		ch[i]^=1;
	}
	for(int i=1;i<=n;i++) putchar(ans[i]);
	cout<<endl;
	int ret;scanf("%d",&ret);
	if(ret==n) exit(0);
	for(int i=1;i<=n;i++) putchar(ans[i]^1);
	cout<<endl;
	scanf("%d",&ret);
	if(ret==n) exit(0);
}
上一篇:leetcode 5. Longest Palindromic Substring/ 1254. Number of Closed Islands/ 45. Jump Game


下一篇:vue实现锚点滚动