CF835E The penguin's game 题解

Zi_Gao

2024 年 04 月 22 日

299 次浏览

暂无评论

872字数

OI 题解

## 题意

交互题。

有一个长度为 $n$ 的序列，给定 $x,y$，其中有恰好 $2$ 个数是 $y$ ，剩下的 $n-2$ 个数是 $x$ 。

你每次可以询问一个集合的异或和。

你需要用不超过 $19$ 次询问找到两个为 $y$ 的数的下标。

$n\leq 1000,x\not = y$

## 题解

假如现在询问一下 $S$ 这个集合，分类讨论：

- 集合大小是奇数，包含奇数个 $y$，答案为 $y$。
- 集合大小是奇数，包含偶数个 $y$，答案为 $x$。
- 集合大小是偶数，包含奇数个 $y$，答案为 $x\oplus y$。
- 集合大小是偶数，包含偶数个 $y$，答案为 $0$。

那么根据集合大小和答案可以反推出包含 $y$ 的情况。现在考虑一个询问策略，由于是找出两个不同的下标，自然想到在二进制上寻找不同位，那么二进制拆分就是最好的选择，每次询问 $S_i$ 表示在 $i$ 这一位上是 $1$ 的所有数，若询问到有奇数个 $y$ 那么这个集合恰好包含了一个 $y$，直接在集合里面二分出来。这样操作次数是 $\lceil\log_2 n\rceil+2\lceil\log_2 \lfloor \frac{n}{2}\rfloor\rceil$ 不能通过，但是发现第二次二分是不必要的，由于是二进制拆位，若当前集合只包含了一个，说明另一个和这一个二进制在这一位上不同，记录下来最后异或起来即可。

```cpp
#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

int x,y;

int query(std::vector<int> &vec){
    printf("? %d ",vec.size());
    for(auto val:vec) printf("%d ",val);
    putchar('\n');
    fflush(stdout);
    return read();
}

char queryCnt(std::vector<int> &vec){
    int v=query(vec);
    if(vec.size()&1){
        if(v==x) return 0;
        else return 1;
    }else{
        if(v==0) return 0;
        else return 1;
    }
}

std::vector<int> grp[30];

int main(){
	#ifndef ONLINE_JUDGE
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
	#endif

for(i=0;i<=lg;++i){
        for(j=1;j<=n;++j)
            if((j>>i)&1)
                grp[i].push_back(j);
        if(queryCnt(grp[i])){
            xr|=1<<i;
            if(flg){
                l=0,r=grp[i].size();
                while(l<r){
                    mid=(l+r)>>1;
                    std::vector<int> now;
                    now.insert(now.end(),grp[i].begin(),grp[i].begin()+mid+1);
                    if(queryCnt(now)) r=mid;
                    else l=mid+1;
                }
                p1=grp[i][l];
                flg=0;
            }
        }
    }

p2=p1^xr;
    if(p1>p2) std::swap(p1,p2);
    printf("! %d %d",p1,p2);

#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	#endif
    return 0;
}
```

最后修改：2024 年 04 月 22 日