[cf1491F]Magnets

首先，只需要找到一个有磁性的位置，就可以通过$n-1$次判断其余磁铁是否有磁性，因此也就是要在$\lfloor\log_{2}n\rfloor+1$次中找到一个有磁性的位置

有一个$n-1$次的做法，即暴力枚举第$i$个磁铁（$i\ge 2$），将1到$i-1$的磁铁放在左侧，那么一定能找到第2个有磁性的磁铁，由于总存在两个，即可以找到

事实上，找磁铁已经无法优化了，但找磁铁的过程却可以带来额外的信息：假设第一个磁铁位于$i$，$i$之前恰好存在一个磁铁，对$i$之前的部分二分即可

更精确的来说，首先用了$i-1$次找到了$i$这个位置，再用$n-i$次可以确定$i$之后的部分，对于$i$之前的部分仅用$\lceil\log_{2}i-1\rceil$次，共计即$n-1+\lceil\log_{2}n\rceil\le n+\lfloor\log_{2}n\rfloor$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 2005

 4 vector<int>v;

 5 int t,n,ans,vis[N];

 6 int main(){

 7     scanf("%d",&t);

 8     while (t--){

 9         scanf("%d",&n);

10         for(int i=1;i<=n;i++)vis[i]=0;

11         v.clear();

12         for(int i=2;i<=n;i++){

13             printf("? %d 1\n",i-1);

14             for(int j=1;j<i;j++)printf("%d ",j);

15             printf("\n%d\n",i);

16             fflush(stdout);

17             scanf("%d",&ans);

18             if (ans){

19                 vis[i]=1;

20                 for(int j=i+1;j<=n;j++){

21                     printf("? 1 1\n%d\n%d\n",i,j);

22                     fflush(stdout);

23                     scanf("%d",&ans);

24                     if (ans)vis[j]=1;

25                 }

26                 int l=1,r=i-1;

27                 while (l<r){

28                     int mid=(l+r>>1);

29                     printf("? %d 1\n",mid-l+1);

30                     for(int j=l;j<=mid;j++)printf("%d ",j);

31                     printf("\n%d\n",i);

32                     fflush(stdout);

33                     scanf("%d",&ans);

34                     if (ans)r=mid;

35                     else l=mid+1;

36                 }

37                 vis[l]=1;

38                 break;

39             }

40         }

41         for(int i=1;i<=n;i++)

42             if (!vis[i])v.push_back(i);

43         printf("! %d ",v.size());

44         for(int i=0;i<v.size();i++)printf("%d ",v[i]);

45         printf("\n");

46         fflush(stdout);

47     }

48 }

巴特西

[cf1491F]Magnets

最新文章

热门文章