知识点总结（其实没什么知识点，就是一些要注意的地方）
1.交互题
- 每次输出后记得使用
<<endl或者fflush(stdout)刷新缓冲区 - 注意题目类型是IO交互题还是函数交互题，若为函数交互题则需注意是否要引用头文件
- 注意利用好下发文件
2.通信题
- 可以理解为实现两个互相调用的交互库
- 注意传递信息的限制
注意是否有Alice和Bob
3.提交答案题
- 注意细心观察即可
今日题目总结
A – Guess the Array
注意到 ，首先进行三次询问，分别为：
? 1 2? 2 3? 1 3
我们就可以得到询问出来的两数之和以及相加后可以得到前三个数的和的两倍，那么除以二就是这三个数的和
于是就可以求出这三个数。最后用这三个数中的任意一个与其他的数求和即可，询问次数为 。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int ans[5005];
signed main(){
int n,sum,tmp1,tmp2,tmp3;
cin>>n;
cout<<"? 1 2"<<endl;
cin>>tmp1;
sum+=tmp1;
cout<<"? 2 3"<<endl;
cin>>tmp2;
sum+=tmp2;
cout<<"? 1 3"<<endl;
cin>>tmp3;
sum+=tmp3;
sum/=2;
ans[1]=sum-tmp2;
ans[2]=sum-tmp3;
ans[3]=sum-tmp1;
for(int i=4;i<=n;++i)
{
cout<<"? 1 "<<i<<endl;
cin>>tmp1;
ans[i]=tmp1-ans[1];
}
cout<<"! ";
for(int i=1;i<=n;++i)
{
cout<<ans[i]<<" ";
}
return 0;
}
B – 元旦激光炮
直接排除法（只是感觉比二分好写一点）
在三个有序数组中，每次比较各数组第 个位置的元素，最小值所在数组的前 个元素一定可以被安全排除
通过不断将被排除的元素数量从 中减去，循环直至 变为 ，最终记录的 即为第 小的值。
#include <bits/stdc++.h>
#include "kth.h"
using namespace std;
int query_kth(int n_a,int n_b,int n_c,int k)
{
int ans=0,ca=-1,cb=-1,cc=-1;
while(k)
{
int l=(k+2)/3;
int va=get_a(ca+l),vb=get_b(cb+l),vc=get_c(cc+l);
if(va<=vb&&va<=vc)
{
ans=max(ans,va);
ca+=l;
k-=l;
}
else if(vb<=vc)
{
ans=max(ans,vb);
cb+=l;
k-=l;
}
else
{
ans=max(ans,vc);
cc+=l;
k-=l;
}
}
return ans;
}
C – ace5 and Task Order
和快排差不多的思路
随机选择一个数组元素作为基准，通过交互查询将其余元素与基准比较，递归地划分出小于和大于基准的两部分，最终确定每个元素的排名
利用随机化来避免被单调数据卡住，期望时间复杂度为
#include <bits/stdc++.h>
using namespace std;
#define int long long
int ans[2005];
char ch;
vector<int> p;
void quick_sort(int l,vector<int> a)
{
int x=rand()%a.size();
cout<<"? "<<a[x]<<endl;
cin>>ch;
while(ch!='=')
{
cout<<"? "<<a[x]<<endl;
cin>>ch;
}
vector<int> b,c;
for(int i=0;i<a.size();++i)
{
if(i==x)
{
continue;
}
cout<<"? "<<a[i]<<endl;
cin>>ch;
if(ch=='<')
{
b.push_back(a[i]);
}
else
{
c.push_back(a[i]);
}
cout<<"? "<<a[x]<<endl;
cin>>ch;
}
ans[a[x]]=l+b.size();
if(b.size())
{
quick_sort(l,b);
}
if(c.size())
{
quick_sort(l+b.size()+1,c);
}
}
signed main(){
srand(chrono::steady_clock::now().time_since_epoch().count());
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
p.clear();
for(int i=1;i<=n;++i)
{
p.push_back(i);
}
quick_sort(1,p);
cout<<"! ";
for(int i=1;i<=n;++i)
{
cout<<ans[i]<<" ";
}
cout<<endl;
}
return 0;
}
D – GCD Queries
注意到题目定义 ，容易发现以下性质：
- 如果，则；
- 如果，则；
- 如果，则；
将所有编号加入集合中，每次选集合中的三个数进行上面的判断，发现哪个数不为 $0$ 则将其从集合中删去，直到剩下最后两个数
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
set<int> s;
for(int i=1;i<=n;++i)
{
s.insert(i);
}
while(s.size()>2)
{
int cnt=0;
int a1=-1,a2=-1,a3=-1;
for(auto it=s.begin();it!=s.end();++it)
{
++cnt;
if(a1==-1)
{
a1=*it;
}
else if(a2==-1)
{
a2=*it;
}
else
{
a3=*it;
}
if(cnt==3)
{
break;
}
}
cout<<"? "<<a1<<" "<<a2<<endl;
int gcd1;
cin>>gcd1;
cout<<"? "<<a1<<" "<<a3<<endl;
int gcd2;
cin>>gcd2;
if(gcd1==gcd2)
{
s.erase(a1);
}
else if(gcd1<gcd2)
{
s.erase(a2);
}
else
{
s.erase(a3);
}
}
cout<<"! ";
for(auto it=s.begin();it!=s.end();++it)
{
cout<<*it<<" ";
}
cout<<endl;
int res;
cin>>res;
if(res==-1)
{
exit(0);
}
}
return 0;
}
E – Deleting Numbers
先用线性筛找出所有不超过 的质数
将质数分块，对每个质数执行 B 操作删除其倍数并记录删除数量，若返回值与预期不符，则说明 含有该质因子，进而通过 A 操作查询其幂次来确定具体指数
每处理完一个质数块后执行 A 1 查询。若集合剩余数量与预期不符，说明 的最小质因子就在刚处理的这个块中，随后在该块内逐个质数排查以精确定位
对于超过 的大质数，因其指数最多为 ，只需在分块过程中确认其是否存在即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100005;
bool vis[N],iscomp[N];
int prime[N],tot;
int n,x,sum,ans;
bool found;
inline void read(int &n)
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
n=x*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
return;
}
signed main(){
read(n);
if(n==1)
{
printf("C 1\n");
fflush(stdout);
return 0;
}
for(int i=2;i<=n;++i)
{
if(!iscomp[i])
{
prime[++tot]=i;
}
for(int j=1;j<=tot&&i*prime[j]<=n;++j)
{
iscomp[i*prime[j]]=true;
if(i%prime[j]==0)
{
break;
}
}
}
memset(vis,0,sizeof(vis));
sum=n;
ans=1;
found=false;
int k=(int)sqrt(tot)+1;
for(int i=1;i<=tot;++i)
{
if(i>=k&&ans*prime[i-k+1]>n)
{
break;
}
printf("B %lld\n",prime[i]);
fflush(stdout);
int cnt=0;
for(int j=prime[i];j<=n;j+=prime[i])
{
if(!vis[j])
{
++cnt;
--sum;
vis[j]=true;
}
}
read(x);
if(x!=cnt)
{
for(int pwr=prime[i];pwr<=n;pwr*=prime[i])
{
printf("A %lld\n",pwr);
fflush(stdout);
read(x);
if(x)
{
ans*=prime[i];
}
else
{
break;
}
}
}
if((i==tot||i%k==0)&&!found)
{
printf("A 1\n");
fflush(stdout);
read(x);
if(x!=sum)
{
int start=i-k+1;
if(start<1)
{
start=1;
}
for(int j=start;j<=i;++j)
{
for(int pwr=prime[j];pwr<=n;pwr*=prime[j])
{
printf("A %lld\n",pwr);
fflush(stdout);
read(x);
if(x)
{
ans*=prime[j];
found=true;
}
else
{
break;
}
}
if(found)
{
break;
}
}
}
}
}
printf("C %lld\n",ans);
fflush(stdout);
return 0;
}
F – Rin and The Unknown Flower
其实我调了一中午提交十多遍都是错的我也很sad
分类讨论一下
对于 的情况，询问CC、CH、CO得到除最后一个位置的C；询问HH、OH得到除第一个位置的H。则除第一个位置和最后一个位置外还没确定的全为O，最后枚举剩下至多四种情况
对于 的情况，依次查 CC, CH, CO；若有出现则枚举所有候选，必要时用候选串查询区分；若无则查 HO；若无则查 OO；若无则查 HHH，每次筛选候选（最后一步唯一），输出最终字符串
然后是蒟蒻因为不想写函数搞出来的整整540行代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
char p[55];
signed main(){
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;++i)
{
p[i]=0;
}
if(n>4)
{
cout<<"? CH"<<endl;
int k;
cin>>k;
if(k==-1)
{
exit(0);
}
for(int i=1;i<=k;++i)
{
int a;
cin>>a;
p[a]='C';
p[a+1]='H';
}
cout<<"? CO"<<endl;
cin>>k;
if(k==-1)
{
exit(0);
}
for(int i=1;i<=k;++i)
{
int a;
cin>>a;
p[a]='C';
p[a+1]='O';
}
cout<<"? CC"<<endl;
cin>>k;
if(k==-1)
{
exit(0);
}
for(int i=1;i<=k;++i)
{
int a;
cin>>a;
p[a]=p[a+1]='C';
}
cout<<"? OH"<<endl;
cin>>k;
if(k==-1)
{
exit(0);
}
for(int i=1;i<=k;++i)
{
int a;
cin>>a;
p[a]='O';
p[a+1]='H';
}
cout<<"? HH"<<endl;
cin>>k;
if(k==-1)
{
exit(0);
}
for(int i=1;i<=k;++i)
{
int a;
cin>>a;
p[a]=p[a+1]='H';
}
for(int i=2;i<n;++i)
{
if(!p[i])
{
p[i]='O';
}
}
int cnt1=2,cnt2=2;
char mj1[2]={'H','O'};
char mj2[2]={'C','O'};
if(p[1]!=0)
{
mj1[0]=p[1];
cnt1=1;
}
if(p[n]!=0)
{
mj2[0]=p[n];
cnt2=1;
}
int is_completed=0;
for(int i=0;i<cnt1;++i)
{
if(is_completed)
{
break;
}
for(int j=0;j<cnt2;++j)
{
if(is_completed)
{
break;
}
p[1]=mj1[i];
p[n]=mj2[j];
if(i==cnt1-1&&j==cnt2-1)
{
is_completed=1;
int tmp;
cout<<"! ";
for(int l=1;l<=n;++l)
{
cout<<p[l];
}
cout<<endl;
cin>>tmp;
if(!tmp)
{
exit(0);
}
break;
}
cout<<"? ";
for(int l=1;l<=n;++l)
{
cout<<p[l];
}
cout<<endl;
cin>>k;
if(k==1)
{
is_completed=1;
int tmp;
cin>>tmp;
cout<<"! ";
for(int l=1;l<=n;++l)
{
cout<<p[l];
}
cout<<endl;
cin>>tmp;
if(!tmp)
{
exit(0);
}
}
if(is_completed)
{
break;
}
}
}
}
else
{
string q2[3]={"CC","CH","CO"};
vector<int> r2[3];
bool any=false;
for(int i=0;i<3;++i)
{
cout<<"? "<<q2[i]<<endl;
int k;
cin>>k;
if(k==-1)
{
exit(0);
}
for(int j=0;j<k;++j)
{
int pos;
cin>>pos;
r2[i].push_back(pos);
}
if(k>0)
{
any=true;
}
}
if(any)
{
vector<pair<string,vector<int>>> qs;
for(int i=0;i<3;++i)
{
qs.push_back({q2[i],r2[i]});
}
vector<string> cands;
string chars="CHO";
for(int mask=0;mask<81;++mask)
{
string cand;
int tmp=mask;
for(int i=0;i<4;++i)
{
cand+=chars[tmp%3];
tmp/=3;
}
bool ok=true;
for(auto &q:qs)
{
string s=q.first;
vector<int> exp=q.second;
vector<int> got;
int len=s.size();
for(int st=0;st+len<=4;++st)
{
if(cand.substr(st,len)==s)
{
got.push_back(st+1);
}
}
if(got!=exp)
{
ok=false;
break;
}
}
if(ok)
{
cands.push_back(cand);
}
}
string ans;
if(cands.size()==1)
{
ans=cands[0];
}
else
{
for(int idx=0;idx<(int)cands.size()-1;++idx)
{
cout<<"? "<<cands[idx]<<endl;
int k;
cin>>k;
if(k==-1)
{
exit(0);
}
if(k==1)
{
int pos;
cin>>pos;
if(pos==1)
{
ans=cands[idx];
break;
}
}
}
if(ans.empty())
{
ans=cands.back();
}
}
cout<<"! "<<ans<<endl;
int tmp;
cin>>tmp;
if(tmp==0)
{
exit(0);
}
continue;
}
cout<<"? HO"<<endl;
int k;
cin>>k;
if(k==-1)
{
exit(0);
}
vector<int> rHO;
for(int i=0;i<k;++i)
{
int pos;
cin>>pos;
rHO.push_back(pos);
}
if(k>0)
{
vector<pair<string,vector<int>>> qs;
for(int i=0;i<3;++i)
{
qs.push_back({q2[i],r2[i]});
}
qs.push_back({"HO",rHO});
vector<string> cands;
string chars="CHO";
for(int mask=0;mask<81;++mask)
{
string cand;
int tmp=mask;
for(int i=0;i<4;++i)
{
cand+=chars[tmp%3];
tmp/=3;
}
bool ok=true;
for(auto &q:qs)
{
string s=q.first;
vector<int> exp=q.second;
vector<int> got;
int len=s.size();
for(int st=0;st+len<=4;++st)
{
if(cand.substr(st,len)==s)
{
got.push_back(st+1);
}
}
if(got!=exp)
{
ok=false;
break;
}
}
if(ok)
{
cands.push_back(cand);
}
}
string ans;
if(cands.size()==1)
{
ans=cands[0];
}
else
{
for(int idx=0;idx<(int)cands.size()-1;++idx)
{
cout<<"? "<<cands[idx]<<endl;
int k2;
cin>>k2;
if(k2==-1)
{
exit(0);
}
if(k2==1)
{
int pos;
cin>>pos;
if(pos==1)
{
ans=cands[idx];
break;
}
}
}
if(ans.empty())
{
ans=cands.back();
}
}
cout<<"! "<<ans<<endl;
int tmp;
cin>>tmp;
if(tmp==0)
{
exit(0);
}
continue;
}
cout<<"? OO"<<endl;
cin>>k;
if(k==-1)
{
exit(0);
}
vector<int> rOO;
for(int i=0;i<k;++i)
{
int pos;
cin>>pos;
rOO.push_back(pos);
}
if(k>0)
{
vector<pair<string,vector<int>>> qs;
for(int i=0;i<3;++i)
{
qs.push_back({q2[i],r2[i]});
}
qs.push_back({"HO",rHO});
qs.push_back({"OO",rOO});
vector<string> cands;
string chars="CHO";
for(int mask=0;mask<81;++mask)
{
string cand;
int tmp=mask;
for(int i=0;i<4;++i)
{
cand+=chars[tmp%3];
tmp/=3;
}
bool ok=true;
for(auto &q:qs)
{
string s=q.first;
vector<int> exp=q.second;
vector<int> got;
int len=s.size();
for(int st=0;st+len<=4;++st)
{
if(cand.substr(st,len)==s)
{
got.push_back(st+1);
}
}
if(got!=exp)
{
ok=false;
break;
}
}
if(ok)
{
cands.push_back(cand);
}
}
string ans;
if(cands.size()==1)
{
ans=cands[0];
}
else
{
cout<<"? "<<cands[0]<<endl;
int k2;
cin>>k2;
if(k2==-1)
{
exit(0);
}
if(k2==1)
{
int pos;
cin>>pos;
if(pos==1)
{
ans=cands[0];
}
else
{
ans=cands[1];
}
}
else
{
ans=cands[1];
}
}
cout<<"! "<<ans<<endl;
int tmp;
cin>>tmp;
if(tmp==0)
{
exit(0);
}
continue;
}
cout<<"? HHH"<<endl;
cin>>k;
if(k==-1)
{
exit(0);
}
vector<int> rHHH;
for(int i=0;i<k;++i)
{
int pos;
cin>>pos;
rHHH.push_back(pos);
}
vector<pair<string,vector<int>>> qs;
for(int i=0;i<3;++i)
{
qs.push_back({q2[i],r2[i]});
}
qs.push_back({"HO",rHO});
qs.push_back({"OO",rOO});
qs.push_back({"HHH",rHHH});
vector<string> cands;
string chars="CHO";
for(int mask=0;mask<81;++mask)
{
string cand;
int tmp=mask;
for(int i=0;i<4;++i)
{
cand+=chars[tmp%3];
tmp/=3;
}
bool ok=true;
for(auto &q:qs)
{
string s=q.first;
vector<int> exp=q.second;
vector<int> got;
int len=s.size();
for(int st=0;st+len<=4;++st)
{
if(cand.substr(st,len)==s)
{
got.push_back(st+1);
}
}
if(got!=exp)
{
ok=false;
break;
}
}
if(ok)
{
cands.push_back(cand);
}
}
string ans=cands[0];
cout<<"! "<<ans<<endl;
int tmp;
cin>>tmp;
if(tmp==0)
{
exit(0);
}
}
}
return 0;
}