ZR 集训 Day23 - 通信、交互、题答非传统题

CF727C Guess the Array 先问前三个，就可以算出来前三个，后面就更简单了。 代码： C++ #include using namespace std; const int N=1e5+5; int n; int a[N],x,y,z; signed main(){ cin>>n; cout>x; cout>y; cout>z; a[1]=(x+y-z)/2,a[2]=(x+z-y)/2,a[3]=(y+z-x)/2; for(int i=4;i>x; a[i]=x-a[1]; } cout `#include 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;in;i++){ cout"? 1 "iendl; cin>>x; a[i]=x-a[1]; } cout"! "; for(int i=1;in;i++) couta[i]" "; return 0; }` UOJ52 元旦激光炮 考虑每次查询每个数组的第 \frac{k}{3} 个数，取最小的，删掉其前缀，因为至多有 k 个数小于它，所以正确性显然。之后重复即可。 代码： C++ #include"kth.h" #include 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 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; } `#include"kth.h" #include 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; pairint,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 c \not = 0 \\ \end{cases} 维护一个可能为 0 的二元组即可。 代码： C++ #include using namespace std; int main(){ int T,n; cin>>T; while(T--){ int a=1,b=2,c; cin>>n; for(c=3;c>g1; cout>g2; if(g1==g2) a=b,b=c; else if(g1>n; if(n==-1) break; } return 0; } `#include using namespace std; int main(){ int T,n; cin>>T; while(T--){ int a=1,b=2,c; cin>>n; for(c=3;cn;c++){ int g1,g2; cout"? "a" "bendl; cin>>g1; cout"? "a" "cendl; cin>>g2; if(g1==g2) a=b,b=c; else if(g1g2) b=c; } cout"! "a" "bendl; 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 次，在规定范围内。 代码： C++ #include using namespace std; int T,n; int ans[2005]; mt19937 rnd(time(0)); int ask(int k){ char c; cout>c; if(c=='=') return 0; if(c=='>') return 1; return -1; } void solve(int l,int r,vector v){ if(!v.size()||l>r) return; if(l==r){ ans[v[0]]=l; return; } vector 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 v(n); for(int i=0;i `#include using namespace std; int T,n; int ans[2005]; mt19937 rnd(time(0)); int ask(int k){ char c; cout"? "kendl; cin>>c; if(c=='=') return 0; if(c=='>') return 1; return -1; } void solve(int l,int r,vectorint> v){ if(!v.size()||l>r) return; if(l==r){ ans[v[0]]=l; return; } vectorint> 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; vectorint> v(n); for(int i=0;in;i++) v[i]=i+1; solve(1,n,v); cout"! "; for(int i=1;in;i++) coutans[i]" "; coutendl; } 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} 的质数并查询即可。 代码： C++ #include 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>res; return res; } int B(int x){ int res; cout>res; return res; } void solve(int l,int r){ if(l>r) return; int mid=(l+r)>>1; for(int i=l;i>n; euler(); for(int i=1;i `#include 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;in;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 "xendl; cin>>res; return res; } int B(int x){ int res; cout"B "xendl; cin>>res; return res; } void solve(int l,int r){ if(l>r) return; int mid=(l+r)>>1; for(int i=l;imid;i++) B(prm[i]); if(A(1)+mid==r+1) solve(mid+1,r); else{ for(int i=l;imid;i++) if(A(prm[i])){ ans=prm[i]; return; } } } signed main(){ cin>>n; euler(); for(int i=1;imin(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];jn;j*=prm[i]){ if(A(j)) ans*=prm[i]; else break; } } } if(ans!=1){ for(int i=66;iidx;i++) if(A(prm[i])==2){ ans*=prm[i]; break; } } else solve(66,idx); cout"C "ans; return 0; }`