Avito Cool Challenge 2018 F. Tricky Interactor(交互 构造)

题目

长为n(n<=300)的01串，初始情况下总共有t(t<=n)个1

你可以询问若干次，

当你询问的区间为[L,R]时，系统会等概率地从[L,n]和[1,R]里选取一个，

将区间的01翻转，翻转操作是可持久化的，即第i次的翻转会对第i+1次的询问生效

询问总次数要求不超过10000，

你需要在若干次询问后，输出原始的01串

特别地，当01串和询问序列顺序都固定的时候，系统随机的返回值序列也是固定的，

也就是说，不会出现ac代码重交wa了的情况

思路来源

乱搞AC

题解

官方题解比较复杂，这里是强行乱搞搞过去的，倒也没错，只是题解做得更优雅吧

搞过去了之后还看了一篇题解，感觉做法也挺好的

对于n=1的情况，直接输出答案即可

询问次数10000，串长300，所以每个位置可以问大概32次，

对于n>=2的情况，先问32次询问[2,n]，这样[L,n]对应[2,n]，[1,R]对应[1,n]

也就是[2,n]每次必翻，[1,1]有概率翻有概率不翻

这样翻32次，只取其中的偶数次来看，[2,n]一定不翻，[1,1]有概率翻，

试了16次，至少出现一次翻一次没翻的概率很高，那么

①如果b[1]一开始是1，总的1的个数是t，这16次只会出现t和t-1

②如果b[1]一开始是0，总的1的个数是t，这16次只会出现t和t+1，就求出了b[1]

后面求每位的情况也是类似，具体来说，

计[1,i-1]的1的个数为pre，当前无法确定第i位是什么，但是已知[i,n]的个数为suf

①如果b[i]一开始是1，那么翻之前为pre+suf，翻了[1,i]之后，总的1的个数为i-(pre+1)+suf-1

②如果b[i]一开始是0，那么翻之前为pre+suf，翻了[1,i]之后，总的1的个数为i-pre+suf

也就是询问的两种结果，一种结果一定是t，根据另一种结果是什么，去判断b[i]初始的值是什么

但是，这种情况下，需要保证pre和初始局面情况下前缀的1的个数相等，

所以，如果询问了32次后，[1,i]中1的个数pre和后缀个数suf之和(即a[32])与t的个数不等，

说明前缀被翻了，这个时候应该不断重试两次直至总和为t，

也就是，保证后缀没翻的情况下，前缀再被翻回来

而对于前缀01个数情况相等的情况，不会影响上面的两个式子的值，不会影响第i位初始的答案

插曲

一开始写的是固定下来询问[i,n]的次数，然后只用第偶数次的结果

询问16次wa3，24次wa9，30次wa86，32次超次数上限，

后来改成偶数次数、奇数次数的结果（奇数次数的时候[i,n]一定被翻）一起考虑，

此时，询问30次时，还是wa86

最后，加了一个剪枝，也就是，对于当前[i,n]偶数次的询问，

如果已经问出了两种不同的值就break，然后就ac了

最后，看了下ac链接里各样例的询问次数，

把询问10000次降到了4000次， 真·纯纯期望次数

心得

一开始学弟提了一个询问[1,i]32次的方法，

也是先询问[1,1]，[1,2]，...,直到[1,n]

但是这个做法有个问题，由于后缀是未求出的，并且有概率翻转

那么，如果询问[1,i]的时候，[i+1,n]中01的个数相同，就无法区别是否翻转，

也就是有了后效性，所以被否掉了，想了一下怎么修

于是，把翻前缀改成翻后缀，也就是把已经求出来的翻了，

这样前缀01个数相等的时候，并不会影响没求的数的正确性，因为没求的数没有翻过

并且能够根据前缀和后缀的1的个数推出，也就有了上面的做法

Another Solution

https://www.cnblogs.com/Kobe303/p/16749590.html

代码

#include
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pairint> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<" ";
#define dbg2(x) cerr<<(#x)<<":"<
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=305,M=33;
int n,t,a[M],b[N];
char ans[N];
int ask(int l,int r){
	printf("? %d %d\n",l,r);
	fflush(stdout);
	int v;
	scanf("%d",&v);
	return v;
}
void out(){
	rep(i,1,n)ans[i]=b[i]+'0';
	ans[n+1]='\0';
	printf("! %s",ans+1);
	fflush(stdout);
}
void sol(){
	sci(n),sci(t);
	int pre=0,suf=t;
	rep(i,1,n-1){
		int mn=n,mx=0,lasj=0;
		rep(j,1,32){
			a[j]=ask(i+1,n);
			if(j%2==0){
				mn=min(mn,a[j]);
				mx=max(mx,a[j]);
				if(mn!=mx){lasj=j;break;}
			}
		}
		int now=a[lasj];
		while(now!=t)now=ask(i+1,n),now=ask(i+1,n);
		int one=i-1-pre+suf-1;// zero=i-1-pre+suf+1;
		if(one==(mn^mx^t))b[i]=1;
		else b[i]=0;
		//printf("mn:%d mx:%d mn^mx^t:%d one:%d zero:%d b:%d\n",mn,mx,mn^mx^t,one,zero,b[i]);
		pre+=b[i];suf-=b[i];
	}
	b[n]=suf;
	out();
}
int main(){
	sol();
	return 0;
}