CF2022D1 Asesino
题意
交互题，有 \(n\) 个人，其中有一些好人和一些坏人，还有一个内鬼，你每次可以选择问一个人回答另一个人是不是好人，回答如下表：
| 好人 | 坏人 | 内鬼 | |
|---|---|---|---|
| 好人 | Yes | No | Yes |
| 坏人 | No | Yes | No |
| 内鬼 | No | Yes | - |
例如，你问内鬼一个好人是不是好人，他会回答 No。
你需要通过最多 \((n+69)\) 次询问找出内鬼。
思路
很显然，内鬼对另一人和另一人对内鬼的回答是相反的，而好人和坏人之间的回答是相同的，所以可以从头问到尾找出有内鬼嫌疑的两个人，再通过 \(2\) 次额外的询问找出内鬼，询问次数最大为 \((n+2)\) 次，我也不知道 \((n+69)\) 次是怎么给出来的。
代码
#include<bits/stdc++.h>
using namespace std;
int T,n;
signed main(){
cin>>T;
while(T--){
cin>>n;
string res1,res2;
int id=0;
for(int i=1;i<=n-(n%2);i+=2){
cout<<"? "<<i<<" "<<i+1<<endl;
cin>>res1;
cout<<"? "<<i+1<<" "<<i<<endl;
cin>>res2;
if(res1!=res2){
id=i;
break;
}
}
if(!id){
cout<<"! "<<n<<endl;
continue;
}
else{
if(id==1){
cout<<"? "<<id+1<<" "<<id+2<<endl;
cin>>res1;
cout<<"? "<<id+2<<" "<<id+1<<endl;
cin>>res2;
if(res1==res2)
cout<<"! "<<id<<endl;
else
cout<<"! "<<id+1<<endl;
}
else{
cout<<"? "<<id-1<<" "<<id<<endl;
cin>>res1;
cout<<"? "<<id<<" "<<id-1<<endl;
cin>>res2;
if(res1==res2)
cout<<"! "<<id+1<<endl;
else
cout<<"! "<<id<<endl;
}
}
}
return 0;
}