[EGOI2025] Dark Ride 题解

· · 题解

提供一种从另一个角度的理解。

考虑一个询问可以包含怎样的信息：对于一次游乐实验，若一个开灯连续段既没有包含第一个位置，也没有包含最后一个位置，那么它的贡献必然是偶数（开始和离开都会有恰好一次尖叫）；若包含两个端点中的恰好一个，贡献为奇数；若两个都包含，贡献为偶数。

从部分分“N 为偶数，且一个端点房间的开关在前半部分，另一个在后半部分”出发，发现这个部分分可以对于两个开关的位置分别进行二分（因为它们初始时已知可能存在于的集合是不交的，也就是说二分时不会出现两个都包含的情况，直接根据询问返回值的奇偶性来判断当前选择的集合是否包含某个开关）。

这启发我们把两个目标开关划分到两个不同的集合中。基于事实“两个数不同，那么这两个数必然存在某个二进制位不同”：考虑对于每个位拿出编号满足当前位为 1 的开关进行询问，若返回值为奇数则两个开关编号该位不同，否则相同。这样只要找到一个不相同的位，就可以把两个开关划分进两个不交的集合（该位为 0/1）。进一步地，我们惊喜地发现上面拆位询问的过程其实是询问两个开关编号的异或值，故只需要二分出其中一个开关编号，即可直接求出另一个开关编号。

拆位询问和二分各需要 \lceil\log_2N\rceil\le 15 次询问，故总共需要不多于 15\times 2=30 次询问，可以通过。

代码非常好写。放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  int k=__lg(n)+(__builtin_popcount(n)>1),c=0;
  for(int i=0;i<k;i++){
    cout<<"? ";
    for(int j=0;j<n;j++)
      cout<<(j>>i&1);
    cout<<endl;
    int x; cin>>x,c|=(x&1)<<i;
  } // 拆位询问，求异或和
  int b=__builtin_ctz(c);
  vector<int> v;
  for(int i=0;i<n;i++)
    if(i>>b&1)v.emplace_back(i);
  int l=0,r=v.size()-1;
  while(l<r){
    int m=l+r>>1;
    vector<int> b(n);
    for(int i=l;i<=m;i++)
      b[v[i]]=1;
    cout<<"? ";
    for(int i:b)cout<<i;
    cout<<endl;
    int x; cin>>x;
    x&1?(r=m):(l=m+1);
  } // 二分过程
  cout<<"! "<<v[r]<<' '<<(v[r]^c)<<endl;
  return 0;
}