题解：P13340 [EGOI 2025] Dark Ride / 黑暗乘车

· · 题解

鲜花

感觉很妙的一道题啊，不过我咋一道青做一天呢？

解法

先思考 n 次交互怎么做。考虑直接对于每个位置询问，如果交互库告诉我答案是一，那显然这个位置是控制两边的开关。否则你不用理它到底是啥。

再考虑正解。我们思考为啥题目让我们求的是两边的开关。可以发现，如果一次询问中不包含两边的开关，那么它返回的答案一定是连通块数的两倍，是个偶数。如果这个询问包含两个两边的开关，那么答案也是偶数。如果恰好包含一个两端的开关，答案就是奇数。这就体现了两边的开关的特殊性。

于是题目就转化为了：现在有个零一序列（代表原题面中的是否为两端的开关），恰好有两个一，每次你可以查询一个子序列中一的个数的奇偶性，让你求出这两个一的位置。

我们发现有个测试组三。在 p_0=0 时，我们已经知道了其中一个一的位置，我们想知道剩下的数中哪个是一。这是好做的，我们考虑一个像线段树一样的递归过程：先查询左儿子区间中有没有一，如果有一就往左儿子走，否则往右儿子走。

通过这个测试组三的提示，我们学会了如何在一个只有一个一的集合中使用 \log n 次询问找到这个一。于是现在我们只要有一种分类方式将两个一分到不同的组中，进行询问，就能找到这两个一的位置。显然你能想到使用质因数等方式区分，但这些都太劣了。于是考虑把每一个位置下标表示为二进制形式，把某个二进制位为一的分为一组，对这些位置统一询问。由于序列中两个一的下标在二进制下总有一些位置不同，因此这样一定能问出来。然后对于那些有恰好一个一的集合 S，我们随便挑一个拉出来做测试组三。要找到剩下的那个一，我们直接对于 S 中的位置取个反就行了（因为只有这些位置里这两个数不同）。

最终交互次数上限是 2\log n 次的，可以通过。

代码

#include<bits/stdc++.h>
using namespace std;
bool is[16];
int xu[30010];
bool xuan[30010];

int main(){
    int n;
    cin>>n;
    int tot=0;
    for(int i=0;i<=14;i++){
        int cnt=0;
        for(int j=1;j<=n;j++){
            if((1<<i)&j)cnt++;
        }
        if(!cnt)continue;
        cout<<"? ";
        for(int j=1;j<=n;j++){
            if((1<<i)&j){
                cout<<"1";
            }
            else cout<<"0";
        }
        cout<<endl;
        int x;
        cin>>x;
        if(x%2){
            is[i]=1;
            if(!tot){
                for(int j=1;j<=n;j++){
                    if((1<<i)&j)xu[++tot]=j;
                }
            }
        }
    }
    int l=1,r=tot;
    while(l<r){
        int mid=(l+r)>>1;
        cout<<"? ";
        for(int i=1;i<=n;i++)xuan[i]=0;
        for(int i=l;i<=mid;i++)xuan[xu[i]]=1;
        for(int i=1;i<=n;i++){
            cout<<xuan[i];
        }
        cout<<endl;
        int x;
        cin>>x;
        if(x%2){
            r=mid;
        }
        else l=mid+1;
    }
    l=xu[l];
    cout<<"! "<<l-1<<" ";
    int sum=l;
    for(int i=0;i<=14;i++){
        if(is[i]){
            sum^=(1<<i);
        }
    }
    cout<<sum-1;
    return 0;
}