网站建设能用手机制作吗,建设工程消防设计备案哪个网站,专业网站设计制作优化排名,小程序源码之家题目
长为n(n300)的01串#xff0c;初始情况下总共有t(tn)个1
你可以询问若干次#xff0c;
当你询问的区间为[L,R]时#xff0c;系统会等概率地从[L,n]和[1,R]里选取一个#xff0c;
将区间的01翻转#xff0c;翻转操作是可持久化的#xff0c;即第i次的翻转…题目
长为n(n300)的01串初始情况下总共有t(tn)个1
你可以询问若干次
当你询问的区间为[L,R]时系统会等概率地从[L,n]和[1,R]里选取一个
将区间的01翻转翻转操作是可持久化的即第i次的翻转会对第i1次的询问生效
询问总次数要求不超过10000
你需要在若干次询问后输出原始的01串
特别地当01串和询问序列顺序都固定的时候系统随机的返回值序列也是固定的
也就是说不会出现ac代码重交wa了的情况
思路来源
乱搞AC
题解
官方题解比较复杂这里是强行乱搞搞过去的倒也没错只是题解做得更优雅吧
搞过去了之后还看了一篇题解感觉做法也挺好的 对于n1的情况直接输出答案即可
询问次数10000串长300所以每个位置可以问大概32次
对于n2的情况先问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和t1就求出了b[1] 后面求每位的情况也是类似具体来说
计[1,i-1]的1的个数为pre当前无法确定第i位是什么但是已知[i,n]的个数为suf
①如果b[i]一开始是1那么翻之前为presuf翻了[1,i]之后总的1的个数为i-(pre1)suf-1
②如果b[i]一开始是0那么翻之前为presuf翻了[1,i]之后总的1的个数为i-presuf
也就是询问的两种结果一种结果一定是t根据另一种结果是什么去判断b[i]初始的值是什么 但是这种情况下需要保证pre和初始局面情况下前缀的1的个数相等
所以如果询问了32次后[1,i]中1的个数pre和后缀个数suf之和(即a[32])与t的个数不等
说明前缀被翻了这个时候应该不断重试两次直至总和为t
也就是保证后缀没翻的情况下前缀再被翻回来
而对于前缀01个数情况相等的情况不会影响上面的两个式子的值不会影响第i位初始的答案
插曲
一开始写的是固定下来询问[i,n]的次数然后只用第偶数次的结果
询问16次wa324次wa930次wa8632次超次数上限
后来改成偶数次数、奇数次数的结果奇数次数的时候[i,n]一定被翻一起考虑
此时询问30次时还是wa86
最后加了一个剪枝也就是对于当前[i,n]偶数次的询问
如果已经问出了两种不同的值就break然后就ac了
最后看了下ac链接里各样例的询问次数
把询问10000次降到了4000次 真·纯纯期望次数
心得
一开始学弟提了一个询问[1,i]32次的方法
也是先询问[1,1][1,2]...,直到[1,n]
但是这个做法有个问题由于后缀是未求出的并且有概率翻转
那么如果询问[1,i]的时候[i1,n]中01的个数相同就无法区别是否翻转
也就是有了后效性所以被否掉了想了一下怎么修
于是把翻前缀改成翻后缀也就是把已经求出来的翻了
这样前缀01个数相等的时候并不会影响没求的数的正确性因为没求的数没有翻过
并且能够根据前缀和后缀的1的个数推出也就有了上面的做法
Another Solution
https://www.cnblogs.com/Kobe303/p/16749590.html
代码
#includebits/stdc.h
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 pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#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 N305,M33;
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[n1]\0;printf(! %s,ans1);fflush(stdout);
}
void sol(){sci(n),sci(t);int pre0,suft;rep(i,1,n-1){int mnn,mx0,lasj0;rep(j,1,32){a[j]ask(i1,n);if(j%20){mnmin(mn,a[j]);mxmax(mx,a[j]);if(mn!mx){lasjj;break;}}}int nowa[lasj];while(now!t)nowask(i1,n),nowask(i1,n);int onei-1-presuf-1;// zeroi-1-presuf1;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]);preb[i];suf-b[i];}b[n]suf;out();
}
int main(){sol();return 0;
}
