CF727C Guess the Array
先问前三个，就可以算出来前三个，后面就更简单了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
int a[N],x,y,z;
signed main(){
cin>>n;
cout<<"? 1 2"<<endl;
cin>>x;
cout<<"? 1 3"<<endl;
cin>>y;
cout<<"? 2 3"<<endl;
cin>>z;
a[1]=(x+y-z)/2,a[2]=(x+z-y)/2,a[3]=(y+z-x)/2;
for(int i=4;i<=n;i++){
cout<<"? 1 "<<i<<endl;
cin>>x;
a[i]=x-a[1];
}
cout<<"! ";
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}UOJ52 元旦激光炮
考虑每次查询每个数组的第 $\frac{k}{3}$ 个数，取最小的，删掉其前缀，因为至多有 $k$ 个数小于它，所以正确性显然。之后重复即可。
代码：
#include"kth.h"
#include<bits/stdc++.h>
using namespace std;
int query_kth(int n_a,int n_b,int n_c,int k){
int id[3]={0,0,0},ans=0;
while(k){
int l=(k+2)/3;
pair<int,int> g[3]={
{get_a(id[0]+l-1),0},
{get_b(id[1]+l-1),1},
{get_c(id[2]+l-1),2}
};
sort(g,g+3);
id[g[0].second]+=l,
ans=max(g[0].first,ans),
k-=l;
}
return ans;
}CF1762D GCD Queries
发现一个性质：
$$
\begin{cases}
gcd(a,b)=gcd(a,c) \rightarrow a \not = 0 \\
gcd(a,b)<gcd(a,c) \rightarrow b \not = 0 \\
gcd(a,b)>gcd(a,c) \rightarrow c \not = 0 \\
\end{cases}
$$
维护一个可能为 $0$ 的二元组即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int T,n;
cin>>T;
while(T--){
int a=1,b=2,c;
cin>>n;
for(c=3;c<=n;c++){
int g1,g2;
cout<<"? "<<a<<" "<<b<<endl;
cin>>g1;
cout<<"? "<<a<<" "<<c<<endl;
cin>>g2;
if(g1==g2) a=b,b=c;
else if(g1<g2) b=c;
}
cout<<"! "<<a<<" "<<b<<endl;
cin>>n;
if(n==-1) break;
}
return 0;
}CF1918E ace5 and Task Order
我们会发现，如果我们一直询问一个位置 $i$，最劣 $n$ 次询问后 $x$ 会变成 $a_i$。
又不难发现，当我们询问一次其他位置，再询问一次 $i$ 时，$x$ 最后还是会变回 $a_i$。
那我们就可以将 $a_i$ 与其他位置比较，进行分治排序。这里我们运用快排的思想，随机去取这个 $i$，期望复杂度为 $O(n\log n)$，每次分治需比较 $3n$ 次，期望询问次数为 $3n\log n$ 次，在规定范围内。
代码：
#include<bits/stdc++.h>
using namespace std;
int T,n;
int ans[2005];
mt19937 rnd(time(0));
int ask(int k){
char c;
cout<<"? "<<k<<endl;
cin>>c;
if(c=='=') return 0;
if(c=='>') return 1;
return -1;
}
void solve(int l,int r,vector<int> v){
if(!v.size()||l>r) return;
if(l==r){
ans[v[0]]=l;
return;
}
vector<int> a,b;
int id=v[rnd()%v.size()];
while(1) if(ask(id)==0) break;
for(int x:v){
if(x==id) continue;
if(ask(x)==-1) a.push_back(x);
else b.push_back(x);
ask(id);
}
ans[id]=l+a.size();
solve(l,l+a.size()-1,a);
solve(l+a.size()+1,r,b);
}
int main(){
cin>>T;
while(T--){
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++) v[i]=i+1;
solve(1,n,v);
cout<<"! ";
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
cout<<endl;
}
return 0;
}CF1406E Deleting Numbers
一个与众不同的写法，询问次数是一样的。
考虑根号分治，对于寻找答案小于 $\sqrt{n}$ 的质因数，我们直接暴力，也就是先问一次 B 把其倍数删掉，再问一次 A 看有没有剩下的，有的话就找到了一个质因数 $p$，之后直接问 A $p,p^2,p^3...$ 来找 $p$ 的指数。
进行这番操作后，我们分析当前的答案。
如果当前答案为 $1$，说明 $x$ 没有小于 $\sqrt{n}$ 的质因数，即 $x$ 要么是 $1$ 要么是一个大质数，且当前集合应该只剩下 $1$ 和大于 $\sqrt{n}$ 的质数。考虑二分，不管集合中的那个 $1$，对前半部分的质数暴力进行 B 操作，再进行 A 操作，查询 $1$，得到集合元素总数，判断 $x$ 是否在前半部分。如果在，就在对前半部分暴力查询一边；如果不在，就递归后半部分。
如果当前答案不为 $1$，说明如果 $x$ 有一个大于 $\sqrt{n}$ 的质因数，那我们对这个质因数进行 A 操作，得到的结果一定是 2，直接暴力扫一遍大于 $\sqrt{n}$ 的质数并查询即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,idx=0,ans=1;
int vis[N],prm[N],num[N];
void euler(){
for(int i=2;i<=n;i++){
if(!vis[i]) prm[++idx]=i;
for(int j=1;i*prm[j]<=n;j++){
vis[i*prm[j]]=1;
if(i%prm[j]==0) break;
}
}
}
int A(int x){
int res;
cout<<"A "<<x<<endl;
cin>>res;
return res;
}
int B(int x){
int res;
cout<<"B "<<x<<endl;
cin>>res;
return res;
}
void solve(int l,int r){
if(l>r) return;
int mid=(l+r)>>1;
for(int i=l;i<=mid;i++) B(prm[i]);
if(A(1)+mid==r+1) solve(mid+1,r);
else{
for(int i=l;i<=mid;i++) if(A(prm[i])){
ans=prm[i];
return;
}
}
}
signed main(){
cin>>n;
euler();
for(int i=1;i<=min(idx,65ll);i++){
int x,y;
x=B(prm[i]);
y=A(prm[i]);
if(y){
ans*=prm[i];
for(int j=prm[i]*prm[i];j<=n;j*=prm[i]){
if(A(j)) ans*=prm[i];
else break;
}
}
}
if(ans!=1){
for(int i=66;i<=idx;i++) if(A(prm[i])==2){
ans*=prm[i];
break;
}
}
else solve(66,idx);
cout<<"C "<<ans;
return 0;
}
Comments NOTHING