工信部2017网站备案,网站建设页面设计,手工木雕网站建设策划书,深圳网站制作的公司深圳app开发题目
n(6n1e4#xff0c;n是3的倍数)个人#xff0c;其中k个人是好人#xff0c;n-k个人是坏人
k是未知的#xff0c;但保证1/3nk2/3n#xff0c;你可以询问若干次#xff0c;
每次你可以选择三个不同的人a,b,c#xff0c;系统告诉你这三个人中好人更…题目
n(6n1e4n是3的倍数)个人其中k个人是好人n-k个人是坏人
k是未知的但保证1/3nk2/3n你可以询问若干次
每次你可以选择三个不同的人a,b,c系统告诉你这三个人中好人更多还是坏人更多
其中好人更多返回1坏人更多返回0
easy可以询问不超过2n次
hard可以询问不超过n6次
要求在给定询问次数内回答出k的值
实际t(t100)组样例保证sumn不超过2e4
思路来源
乱搞ac
题解
其实是两年前做的题了当时没写题解现在补一下
首先n是3的倍数恰分成n/3堆每堆询问一次
其中约束条件1/3nk2/3n是保证这n/3次询问不会出现答案全是0或全是1的情况
记录得到一个0的询问位置(huai,huai1,huai2)和得到一个1的询问位置(hao,hao1,hao2) 得到这六个位置后每个询问中取出四个这里是
令a[1]huai,a[2]huai1a[3]huai2a[4]haoa[5]hao1,a[6]hao2
这里是取出a[2]、a[3]、a[5]、a[6]
然后再询问四次即C(4,3)挑一下
b[1]询问2、3、5b[2]询问2、3、6b[3]询问356b[4]询问2、5、6 注意到a[1]-a[3]的询问结果是0说明a[2]和a[3]要么一好一坏要么两坏
同理a[5]和a[6]要么一好一坏要么两好即a[5]和a[6]至少有一个好 那么对于235(b[1])和236(b[2])这两次询问
即如果把a[1]替换成a[5]/a[6]导致出现了1出现了翻转
而a[2]和a[3]两坏情况是翻转不过来的说明a[2]和a[3]只能是一好一坏那么a[1]一定是坏
如果没出现翻转由于a[5]和a[6]一好一坏其中好的那次都没翻转说明a[2]和a[3]只能是两坏
这样就能获得一定是坏的人的编号了记为huai 类似地对于b[3]和b[4]也这么讨论一下也能获得一定是好的人的编号记为hao
此时用了n/34次询问 easy由于得到了一好一坏对于n个位置每次询问(hao,huai,i)即可得出i是哪一边
总询问次数n/34n不超过2n hard根据之前询问的n/3次结果在原来的结果基础上分类讨论还是考虑这n/3堆
1如果这一堆是hao或huai所在的堆
那么有四个这样的位置未确认答案暴力询问(hao,huai,i)即可
2如果之前这堆是huai取出其中两个询问不妨取出i和i1
询问(hao,i,i1)如果答案是hao说明i2一定是huai而i和i1中一好一坏
再暴力询问(hao,huai,i)得到这一个的值即可得到另一个的值
3如果之前这堆是hao和2对称也能两次询问出这三个位置的值
所以总的询问次数为n/34n/3*2即n4次符合条件
代码
#includebits/stdc.h
using namespace std;
const int N1e410;
int T,n;
int hao,huai,res[N];
vectorintans;
int one,two,a[7],b[5];
int ask(int a,int b,int c){printf(? %d %d %d\n,a,b,c);fflush(stdout);int v;scanf(%d,v);return v;
}
void solve(){if(b[1] || b[2])huaia[1];//被01翻了说明a[2]和a[3]一个0一个1a[1]是0else huaia[2];//01都翻不过来说明a[2]和a[3]都是0if(!b[3] || !b[4])haoa[4];//被01翻了说明a[5]和a[6]一个0一个1a[4]是1else haoa[5];//01都翻不过来说明a[5]和a[6]都是1ans.clear();ans.push_back(huai);for(int i1;in;i3){if(ione || itwo){for(int ji;ji3;j){if(jhuai || jhao)continue;int vask(huai,hao,j);if(v0)ans.push_back(j);}continue;}int x,y;if(res[i]0){xask(i,i1,hao);if(x0){ans.push_back(i);ans.push_back(i1);yask(i2,hao,huai);if(y0)ans.push_back(i2);}else{ans.push_back(i2);yask(i1,huai,hao);if(y1)ans.push_back(i);else ans.push_back(i1);}}else{xask(i,i1,huai);if(x1){yask(i2,hao,huai);if(y0)ans.push_back(i2);}else{yask(i1,huai,hao);if(y1)ans.push_back(i);else ans.push_back(i1);}}}printf(! );printf(%d,(int)ans.size());for(auto v:ans){printf( %d,v);}puts();fflush(stdout);
}
int main(){scanf(%d,T);while(T--){scanf(%d,n);onetwo-1;for(int i1;in;i3){int vask(i,i1,i2);res[i]v;if(v0 one-1)onei;if(v1 two-1)twoi;}a[1]one;a[2]one1;a[3]one2;a[4]two;a[5]two1;a[6]two2;b[1]ask(a[2],a[3],a[5]);b[2]ask(a[2],a[3],a[6]);b[3]ask(a[3],a[5],a[6]);b[4]ask(a[2],a[5],a[6]);solve();}return 0;
}
