P5473 [NOI2019] I 君的探险 题解

· · 题解

诶嘿嘿第一篇黑题题解！写的不好还请各位多多包涵喵 qwq。

这是一个非常有意思的题喵。

交互题格式

首先需要弄清楚这种远古交互题的格式。

我们都知道现在的交互题都是直接向标准输出输出请求然后清空缓冲区后读取题目给的回复对吧。但是这里的交互题是直接使用一个函数来与题目进行交互的，我觉得这种方式其实非常好理解，只不过不好测样例罢了。

如果不太懂的话可以看下面的代码，就是这道交互题的格式。如果有需要的话可以直接复制过来在其基础上编代码。

::::success[code]

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define pb push_back
using namespace std;

void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);

void explore(int N,int M){
    //真正的实现部分
}

::::

考虑到现在正赛上不会出现这种交互题了就不给正赛上的这种交互题的格式代码了，上面的代码是适用于在洛谷提交的。

第一档分数：测试点 1 \sim 5

query 次数（即 L_q）给的十分充足，达到了 n^2 的量级。

于是可以考虑直接暴力枚举当前节点 0 \le x < n-1，对 x 先进行一次 modify 改变状态，然后枚举所有 x < y \le n-1，只要当前 query 得到的 y 状态与原先不符，说明在对 x 执行 modify 的时候也牵连到 y 使其状态改变了，等价于说 x 和 y 之间有一条边，此时就可以直接 report 记录了。

注意：由于 modify 次数（即 L_m）只给到了 n-1，不支持每次对 x 执行 modify 后再执行一次还原状态，因此要实时维护每个点当前的状态。不过处理完了的点显然就不需要维护了，比如当前考虑到 x，则只需维护点 x \sim n-1 的状态。

::::success[code]

//第一档分数：测试点 1~5
namespace sub1{
    int a[N];
    void main(int n){//主函数
        for(int x=0;x<n-1;x++){
            modify(x);//改变状态
            for(int y=x+1;y<n;y++)
                if(query(y)!=a[y])
                    report(x,y),a[y]^=1;
            //判断是否有边，有边则记录
        }return;//搞定
    }
}

::::

此时你可以搞到 20 分。

第二档分数：测试点 6 \sim 9

特殊性质 A 保证了每个点度数为 1，m = \frac{n}{2}，得到结论：图一定是两两点形成配对组（二元匹配）。

为了确保唯一性，定义 x 到 y 的边的边编号为 \min(x,y)，同时这也被称为 x 的边编号以及 y 的边编号。

整体二分，solve(l,r,L,R) 表示询问 [L,R] 的答案（边编号）所处范围为 [l,r]。取 [l,r] 的中点 mid，先对 l \sim mid 的点进行修改，然后枚举每个询问 L \le x \le R。对于这个 x，如果 l \le x \le mid 和 x 受到前面改变导致状态（query 值）改变这两个条件中满足且仅满足一个，那么 x 的边编号一定在 [l,mid] 中，分到左边，否则分到右边。

::::success[code]

//第二档分数：测试点 6~9
namespace sub2{
    int sta[N],q[N],q1[N],q2[N];
    bool vis[N];
    void solve(int l,int r,int L,int R){//整体二分
        if(l>r||L>R)return;//越界
        if(l==r){
            for(int i=L;i<=R;i++)
                if(!vis[min(q[i],l)]){//这条边还没被记录
                    vis[min(q[i],l)]=1;//标记
                    report(q[i]-1,l-1);//转化为 0-base
                    break;//连边成功
                }
            return;
        }
        int mid=(l+r)>>1,p1=0,p2=0;
        for(int i=l;i<=mid;i++)
            modify(i-1);//前提，方便后续二分判断
        for(int i=L;i<=R;i++){
            bool flag=0;
            if(sta[q[i]]!=query(q[i]-1))//状态变了
                sta[q[i]]^=1,flag=1;//记录
            if(flag!=(l<=q[i]&&q[i]<=mid))q1[++p1]=q[i];
            else q2[++p2]=q[i];
            //二分，分到左右两边
        }
        for(int i=1;i<=p1;i++)q[L+i-1]=q1[i];
        for(int i=1;i<=p2;i++)q[R-p2+i]=q2[i];
        //放回原数组
        solve(l,mid,L,L+p1-1);
        solve(mid+1,r,R-p2+1,R);return;
        //继续往下分治做二分
    }
    void main(int n){//主函数
        for(int i=1;i<=n;i++)q[i]=i;//初值
        solve(1,n,1,n);//整体二分
        return;//搞完了
    }
}

::::

此时你可以搞到 36 分。

第三档分数：测试点 10 \sim 11

题目保证了一个 B 性质，其实就等价于说：全图是一棵树，且每个节点的父节点都比自己的编号要小。并且 modify 次数和 query 次数都是 n \log n 级别的。

还是考虑整体二分，solve(l,r,L,R) 表示询问 [L,R] 的答案（父节点编号）所处范围为 [l,r]。先把 l \sim mid 都 modify 一次，然后对于每个询问 L \le x \le R，若 x \le mid 或对 x 进行 query 得到 1 的话，就将 x 分到左边，否则把 x 分到右边。最后记得把 l \sim mid 给 modify 回来，还原状态。

::::success[code]

//第三档分数：测试点 10~11
namespace sub3{
    int sta[N],q[N],q1[N],q2[N];
    void solve(int l,int r,int L,int R){//整体二分
        if(l>r||L>R)return;//越界
        if(l==r){
            for(int i=L;i<=R;i++)
                report(q[i]-1,l-1);//记录边，注意转化为 0-base
            return;
        }
        int mid=(l+r)>>1,p1=0,p2=0;
        for(int i=l;i<=mid;i++)
            modify(i-1);//前提，方便后续二分判断
        for(int i=L;i<=R;i++)
            if(q[i]<=mid||query(q[i]-1))q1[++p1]=q[i];
            else q2[++p2]=q[i];
            //二分，分到左右两边
        for(int i=l;i<=mid;i++)
            modify(i-1);//重置回原状态
        for(int i=1;i<=p1;i++)q[L+i-1]=q1[i];
        for(int i=1;i<=p2;i++)q[R-p2+i]=q2[i];
        //放回原数组
        solve(l,mid,L,L+p1-1);
        solve(mid+1,r,R-p2+1,R);return;
        //继续往下分治做二分
    }
    void main(int n){//主函数
        report(0,1);//肯定有这条边，先记录上
        for(int i=3;i<=n;i++)q[i]=i;//初值
        solve(1,n,3,n);//整体二分
        return;//搞完了
    }
}

::::

此时你可以搞到 44 分。

第四档分数：测试点 12 \sim 14

这个 C 性质等价于保证了图是一条链，而 modify 和 query 次数（L_m 和 L_q）都给的非常大，有 10^7，等价于你不用考虑它的限制，只要你不超时就行。

拆二进制位考虑（\log 随便做），对于二进制下第 k 位，枚举所有节点 x，如果 x 的第 k 位是 1 就对 x 执行 modify。再枚举每个节点 x，如果 x 的第 k 位的值与对 x 执行 query 得到的状态不符，说明 x 的相邻节点的异或和包含二进制位 k，算进去即可。别忘了刚才 modify 的内容在处理完这一位的相邻节点异或和后还需要 modify 回来，不然影响后面判断。

得到了这些异或和就好办了。我们随便指定一个节点（比如 0），先用 modify 和 query 找出它的相邻两个节点（也有可能只有一个）的具体编号，然后从两边进去不断往链的两个端点搜即可找出所有边啦！

::::success[code]

//第四档分数：测试点 12~14
namespace sub4{
    int xr[N];
    void sol(int now,int lst){
        if(lst==xr[now])return;//到链端了
        report(now,lst^xr[now]);//记录
        sol(lst^xr[now],now);//继续搜索
        return;//使命完成
    }
    void main(int n){
        for(int x=0;(1<<x)<n;x++){//枚举二进制位
            for(int i=0;i<n;i++)
                if((i>>x)&1)modify(i);//这位为 1 则变化
            for(int i=0;i<n;i++)
                if(((i>>x)&1)!=query(i))xr[i]|=(1<<x);
                //与原状态不匹配，说明两边异或包含该二进制位
            for(int i=0;i<n;i++)
                if((i>>x)&1)modify(i);//变回来防止影响后面的处理
        }
        modify(0);//变化 0 并针对性找出与 0 相连的边
        int x=0,y=0;//用于记录 0 的连边
        for(int i=1;i<n;i++)
            if(query(i)){if(x)y=i;else x=i;}
        report(0,x);sol(x,0);//继续深入找边
        if(y){//0 不是链的末端，另一个方向也有值
            report(0,y);sol(y,0);//同样深入找边
        }
        return;//边都找完了，结束
    }
}

::::

此时你可以搞到 56 分。

第五档分数：测试点 15 \sim 17

D 性质保证了图连通，再加上 m=n-1，就是告诉我们图是一棵树。modify 和 query 次数（L_m 和 L_q）依旧多的吓人，于是我们可以随便用。

使用刚才那档分数的方式也求出每个节点的相邻节点异或和。为了以下描述方便，将节点 x 的相邻节点异或和记为 xr_x。

搞一个普通队列，最开始先把 1 \sim n 所有节点编号都塞进去。

我们每次取出队头 u，用 modify 再 query 最后 modify 回来的方式判断 u 与 xr_u 之间是否有边（有边说明 u 的其他相邻节点都处理完毕了），没边就先跳过这一回合。有边直接 report，然后让 xr_{xr_u} 异或上 u，让 xr_u 加入队列并设置 xr_u = 0，等价于在这棵树上删掉 u 这个节点。

这个方法看起来好玄乎，但其实是没问题的，因为每次 u 与 xr_u 有边的情况当且仅当 u 的度数为 1 即 u 是叶子结点，那么每次删叶子总会导致出现新的叶子，肯定是能把所有边都找完全的。

::::success[code]

//第五档分数：测试点 15~17
namespace sub5{
    int xr[N];
    map<pii,bool> mp;//标记边是否被处理
    bool Isrep(int x,int y){
        pii p={min(x,y),max(x,y)};
        //排序后记录确保唯一性
        if(mp[p])return 0;//记录过了
        mp[p]=1;return 1;//做好标记
    }
    void main(int n){
        for(int x=0;(1<<x)<=n;x++){//枚举二进制位
            for(int i=1;i<=n;i++)
                if((i>>x)&1)modify(i-1);//这位为 1 则变化
            for(int i=1;i<=n;i++)
                if(((i>>x)&1)!=query(i-1))xr[i]|=(1<<x);
                //与原状态不匹配，说明两边异或包含该二进制位
            for(int i=1;i<=n;i++)
                if((i>>x)&1)modify(i-1);//变回来防止影响后面的处理
        }
        queue<int> q;
        while(!q.empty())q.pop();//清空
        for(int i=1;i<=n;i++)q.push(i);//把所有点都塞进去
        while(!q.empty()){//只要队列非空，就意味着还没处理完全
            int u=q.front();q.pop();//取出队头
            if(xr[u]<1||xr[u]>n||xr[u]==u)continue;//剩余垃圾值
            modify(xr[u]-1);//变化
            int sta=query(u-1);//看看情况
            modify(xr[u]-1);//变回去
            if(sta&&Isrep(xr[u],u)){//有边且没被记录过
                report(xr[u]-1,u-1);//记录
                xr[xr[u]]^=u;//更新异或值，去掉 u 点
                q.push(xr[u]);//进队列
                xr[u]=0;//废弃值
            }
        }return;//搞完了
    }
}

::::

此时你可以搞到 68 分。

第六档分数：测试点 18 \sim 25

正解终于来了！但是正解好像和前面的东西关系不大……

类似第二档分数（测试点 6 \sim 9）去做整体二分。先用 random_shuffle 打乱节点编号，然后每个点仿照运来第三档分数（测试点 10 \sim 11）的方式“找父节点”，但是这里的图并不是树对吧……所以并没有一个特指的“父节点”，不过找到的这个所谓“父节点”一定是边之一，连上就行。注意判断状态的时候需要消掉已经 report 的点所带来的影响。

只要边还没找完全，我们就把所有还没找全边的点（即 check 返回值为 0 的点）加入询问序列，打乱后做上述整体二分。

什么随机化，不会证，感性理解一下吧。

::::success[code]

//第六档分数：测试点 18~25
namespace sub6{
    int id[N],q[N],q1[N],q2[N],cnt;//id 存储编号
    bool ok[N],sta[N];//这个点是否处理完全，以及每个点的状态
    vector<int> g[N];//存边
    bool edges_sta(int u){
        bool state=query(u-1);//读取当前状态
        for(int v:g[u])state^=sta[v];//算上邻点状态
        return state;//返回
    }
    void solve(int l,int r,int L,int R){//整体二分
        if(l>r||L>R)return;//越界
        if(l==r){
            for(int i=L;i<=R;i++)if(q[i]!=l){//自己不能和自己连边
                report(id[l]-1,id[q[i]]-1);//记录边
                g[id[l]].pb(id[q[i]]);
                g[id[q[i]]].pb(id[l]);//连边
                cnt--;//边数减少
            }return;
        }
        int mid=(l+r)>>1,p1=0,p2=0;
        for(int i=l;i<=mid;i++)if(!ok[id[i]])
            //处理完了的就不用浪费次数了
            modify(id[i]-1),sta[id[i]]=1;
        for(int i=L;i<=R;i++)
            if(q[i]<=mid||edges_sta(id[q[i]]))q1[++p1]=q[i];
            else q2[++p2]=q[i];
            //二分，分到左右两边
        for(int i=l;i<=mid;i++)if(!ok[id[i]])
            modify(id[i]-1),sta[id[i]]=0;//还原
        for(int i=1;i<=p1;i++)q[L+i-1]=q1[i];
        for(int i=1;i<=p2;i++)q[R-p2+i]=q2[i];
        //放回原数组
        solve(l,mid,L,L+p1-1);
        solve(mid+1,r,R-p2+1,R);return;
        //继续往下分治做二分
    }
    void main(int n,int m){
        cnt=m;//记录当前剩余边数
        for(int i=1;i<=n;i++)id[i]=i;
        while(cnt){//还没处理完
            random_shuffle(id+1,id+n+1);//打乱
            int qcnt=0;//询问长度
            for(int i=1;i<=n;i++)
                if(!ok[id[i]])q[++qcnt]=i;//没处理完的就塞进去当询问
            solve(1,n,1,qcnt);//整体二分
            if(cnt)//没处理完
                for(int i=1;i<=n;i++)
                    if(!ok[i]&&check(i-1))ok[i]=1;
                    //更新是否处理完全的状态
        }
    }
}

::::

此时你可以搞到 100 分和一个绿色的 Accepted。

最终代码

把上面六档分数的代码结合在一起就能过了。

::::success[code]

void explore(int N,int M){
    if(N<=500)sub1::main(N);//测试点 1~5
    else if(N%10==8)sub2::main(N);//测试点 6~9
    else if(N%10==7)sub3::main(N);//测试点 10~11
    else if(N%10==6)sub4::main(N);//测试点 12~14
    else if(N%10==5)sub5::main(N);//测试点 15~17
    else sub6::main(N,M);//测试点 18~25
}

::::

完整代码就不放了，就是上面给出的所有代码结合在一块。

后记

这题确实是一个好题。神仙题！个人认为挺考验思维哒 qwq。

这是嘎嘎喵的第一篇黑题题解 /kel，还请各位留个赞好嘛 awa ，谢谢你们喵！/xin