题解：P14134 【MX-X22-T5】「TPOI-4E」Get MiN? Get MeX!

StеlІаwіnD · 2025-10-02 18:57:47 · 题解

先把序列分成前后两半，那么显然它们问出来的答案是一样的，不妨记为 K。

那么显然一边存在 0\sim K-1 的所有数，而另一边有 K。不妨设左边是前者，右边是后者。

可以发现，在左边的集合里任取一个子集，问出来的答案都不超过 K。在右边的集合里任取一个子集，问出来的答案都不小于 K。且如果把某一边的集合拆成两个，都最多只有其中一个满足问出来恰好等于 K。

于是我们把左边的集合拆成两半，问其中一个。把右边的集合拆成两半，问其中一个。

如果问出来存在一个值不等于 K，那么我们就可以确定包含 0\sim K-1 的集合是左边还是右边。往这个方向递归下去即可。

如果问出来两个都是 K，那么答案只会在这两个询问的集合中。以这两个集合往下递归即可。

最后会剩下两个大小为 1 的集合，问一下第二种询问即可确定。

询问次数显然是 2\log n+1，多的一次是开始要确定最初的 K。

赛时好像没观察全，但是也通过了。

int solve(std::vector<int>A){
  if(A.size()==1)return A[0];
  int sz=A.size();
  std::vector<int>l,r;
  rep(i,0,sz/2-1)l.pb(A[i]);
  rep(i,sz/2,sz-1)r.pb(A[i]);
  int X=ask1(r);
  if(X==1)return solve(r);
  else return solve(l);
}
int solve(int k,std::vector<int>l,std::vector<int>r){
  if(l.size()==1||r.size()==1){
    if(l.size()==1){
      int X=ask2(l[0]);
      if(X==-1)return l[0];
      return solve(r);
    }
    else{
      int X=ask2(r[0]);
      if(X==-1)return r[0];
      return solve(l);
    }
  }
  std::vector<int>lL,lr,rl,rr;
  int szl=l.size(),szr=r.size();
  rep(i,0,(szl+1)/2-1)lL.pb(l[i]);
  rep(i,(szl+1)/2,szl-1)lr.pb(l[i]);
  rep(i,0,(szr+1)/2-1)rl.pb(r[i]);
  rep(i,(szr+1)/2,szr-1)rr.pb(r[i]);
  int X=ask1(lL),Y=ask1(rl);
  if(X<k)return solve(X,lL,lr);
  if(Y<k)return solve(Y,rl,rr);
  std::vector<int>A,B;
  if(X==k)A=lL;else A=lr;
  if(Y==k)B=rl;else B=rr;
  return solve(k,A,B);
}
void solve(){
  int n;read(n);
  if(n==1){std::cout<<"! 1"<<std::endl;return;}
  std::vector<int>l,r;
  rep(i,1,n/2)l.pb(i);
  rep(i,n/2+1,n)r.pb(i);
  int ans=solve(ask1(l),l,r);
  std::cout<<"! "<<ans<<std::endl;
}