题意
\(1000\) 个硬币中有 \(10\) 个假币,你每次可以询问两个位置的硬币类型是否相同,你需要用不超过 \(950\) 次询问找出所有假币的位置。
思路
将前 \(990\) 个硬币每 \(11\) 个分一组,共 \(90\) 组,余 \(10\) 个单独分一组。
询问每组第 \(1\) 个硬币和这组后面硬币的关系。因为只有 \(10\) 个假币,所以如果含有 \(11\) 个硬币的一组全部相同,那么这一组就全是真币,挑出一个真币跟含有假币的组(即含有不同硬币的一组)的第 \(1\) 个硬币比较,即可判断出这一组硬币的真假情况,最多 \(90\times 10+9+10=919\) 次询问,可以通过。
注意因为最后一组只有 \(10\) 个,所以当每组的硬币都相同时,\(10\) 个假币就都在最后一组。
代码
#include <bits/stdc++.h>
using namespace std;
int n,m,q,nst;
bool ys[1005][1005],ist[1005];
vector<int> fk;
bool cp;
signed main() {
cin>>n>>m>>q;
for(int i=1;i<=1000;i+=11){
for(int x,j=i+1;j<=min(1000,i+10);j++){
cout<<"? "<<i<<" "<<j<<endl;
cin>>x;
if(x==1)
ys[i][j]=true,ist[i]=true,cp=true;
}
if(!ist[i])
nst=i;
}
if(!cp){
cout<<"! ";
for(int i=991;i<=1000;i++)
cout<<i<<" ";
cout<<endl;
return 0;
}
for(int x,i=1;i<=1000;i+=11){
if(!ist[i]) continue;
cout<<"? "<<nst<<" "<<i<<endl;
cin>>x;
if(x) fk.push_back(i);
for(int j=i+1;j<=min(1000,i+10);j++){
if(ys[i][j]^x)
fk.push_back(j);
}
}
cout<<"! ";
for(int v:fk)
cout<<v<<" ";
cout<<endl;
return 0;
}
标签:10,arc184,一组,硬币,int,题解,假币,cp,Appraiser
From: https://www.cnblogs.com/WuMin4/p/18427162