Gym - 100851J [随机+01集合]

题目链接:https://vjudge.net/problem/Gym-100851J

解题思路:

出题故意不给501次，就是要让我们去随机找出值为n/2的串，每次最坏的情况随机一个串值是n/2的概率是:

约等于0.022。那我们随机400不中的概率是

 = 0.000309336，概率非常低，所以几乎是可以找到的。

找到之后s串后，同时改变0和i位置的值，询问此时值是否还是n/2，如果是，也就是说0和i是对立的，一个如果和原串相同，那么另一个就不同。如果不是，说明他们是相同的，相同一起相同，不相同一起不相同。

最后我们再枚举0位置的值是0或者1就可以找出原串了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
const int mx = 1e3+10;
int n,m,K;
char s[mx],ts[mx];	
int vis[mx];
int fa[mx*2];
int main(){
	srand(time(NULL));
	scanf("%d",&n);
	for(int i=0;i<n;i++) s[i] = '0';
	s[n] = 0,fa[0] = 1;
	bool ok = 0;
	int v;
	while(1){
		for(int i = 0; i < n; i++)
			s[i] =rand()%2+'0';
		printf("%s\n",s);
		fflush(stdout);
		scanf("%d",&v);
		if(v==n/2)	break;
		else if(v==n){
			ok = 1;
			break;
		}
	}
	if(ok) return 0; 
	char c1 = s[0];
	if(c1=='0') s[0] = '1';
	else s[0] = '0';
	for(int i=1;i<n;i++){
		char c2 = s[i];
		if(c2=='0') s[i] = '1';
		else s[i] = '0';
		printf("%s\n",s);
		fflush(stdout);
		scanf("%d",&v);
		if(v==n/2) fa[i] = 0;
		else fa[i] = 1;
		s[i] = c2;
	}
	s[0] = c1,ts[n] = 0;
	for(int i=0;i<n;i++){
		if(fa[i])
			ts[i] = s[i];
		else
			ts[i] = ((s[i]-'0')^1)+'0';
	}
	printf("%s\n",ts);
	fflush(stdout);
	scanf("%d",&v);
	if(v==n) return 0;
	for(int i=0;i<n;i++){
		if(fa[i]){
			ts[i] = ((s[i]-'0')^1)+'0';
		}else{
			ts[i] = s[i];
		}
	}
	printf("%s\n",ts);
	fflush(stdout);
	scanf("%d",&v);
	return 0;
}