题目

交互题

有\(2n\)个物品，编号为\(1-2n\)，存在唯一的两两配对关系，即有\(n\)种物品

有一个盒子，初始为空，盒子上会显示里面存在的物品种类数\(C\)

你每次操作可以将一个物品从盒子里拿出或者放入盒子

$n \le 43000 $，次数限制\(10^6\)

题解

• 首先依次加入所有物品，考虑C变和不变可以将物品分成两个对应的集合AB

• 在盒子里保留A的一半，依次改变B的状态，考虑C变和不变可以将B继续分成对应的两个集合

• 交换AB，一直分治下去，复杂度大约是\(O(3.5N+2NlogN)\)

• 然而这题最优秀的一点在于后面(图片来自官解)：

  我们假设分治部分的次数复杂度为\(f(N) = tN \ logN\) ，设每次分治的两部分之比为p : 1 - p

  

  (求导)求极值点：

  

• 那 p 就一反套路地取0.382好了

  #include "minerals.h"#include
        
         #define K 0.38using namespace std;const int maxN=43010;int n,P[maxN],Q[maxN],vis[maxN<<1];int pl[maxN],pr[maxN],ql[maxN],qr[maxN];bool query(int x){  static int now,lst,re;  vis[x]^=1;now=Query(x);  re=(now!=lst);lst=now;  return re;}void Swap(int l1,int r1){  static int tmp[maxN];  for(int i=1;i<=l1;++i)tmp[i]=pl[i];  for(int i=1;i<=r1;++i)pl[i]=pr[i];  for(int i=1;i<=l1;++i)pr[i]=tmp[i];}//直接swap两个指针的话似乎会把指向的数组全部交换void solve(int*p,int*q,int len){  if(len==1){      Answer(p[1],q[1]);      return;  }  int l1,r1,l2,r2;  l1=r1=l2=r2=0;  for(int i=1;i<=len;++i){      if(vis[p[i]])pl[++l1]=p[i];      else pr[++r1]=p[i];  }  if(l1>r1)Swap(l1,r1),swap(l1,r1);  int base=max(1,(int)(K*len));  while(l1
         
          base)query(pl[l1]),pr[++r1]=pl[l1--];  if(vis[pl[1]])Swap(l1,r1),swap(l1,r1);  for(int i=1;i<=len;++i)if(query(q[i])){      ql[++l2]=q[i];      if(l2==l1){for(++i;i<=len;++i)qr[++r2]=q[i];}  } else{      qr[++r2]=q[i];      if(r2==r1){for(++i;i<=len;++i)ql[++l2]=q[i];}  }  for(int i=1;i<=l1;++i)p[i]=pl[i];  for(int i=1;i<=l2;++i)q[i]=ql[i];  for(int i=1;i<=r1;++i)p[i+l1]=pr[i];  for(int i=1;i<=r2;++i)q[i+l2]=qr[i];      solve(q,p,l1);  solve(q+l1,p+l1,r1);}void Solve(int N) {  n=N;  int cnt1=0,cnt2=0;  for(int i=1;i<=2*n;++i){      if(query(i))P[++cnt1]=i;      else Q[++cnt2]=i;  }     solve(P,Q,n);}//一道非常有意思的交互题//20190622