题解：P10539 [APIO2024] 魔术表演

· · 题解

根据题意，很显然，我们只需要想办法传递 N 二进制下每一位的值即可。因为点数 5000 远大于 N 在二进制下的位数 60，所以在许多边重复记录要传达的信息的情况下，删去一些边后出错率仍然极低。

为了避免被毒瘤交互库卡掉，我们要让生成的树尽可能均匀，让交互库无法猜测到每个点或边的功能，或者即使可能被交互库卡也要尽可能提高正确率。我们考虑一些非常神奇的做法：

我们将这 5000 个点分成大小相等的两组：一组 2500 个点（编号 1 \sim 2500）用于表示 1 或 0，其中前 1250 个点表示 1，后 1250 个点表示 0；另一组 2500 个（编号 2501 \sim 5000）分别描述 N 的每一个二进制位，第 2501 + i 个点表示 N 从低到高第 (i \mod 60) 个二进制位（从 0 开始）的值。

我们将第 2501 \sim 5000 的点连向前 2500 个点，若对应 N 的二进制位应当为 1 则随机连接 1 \sim 1250 中的一个点，否则随机连接 1251 \sim 2500 中的一个点。如果你愿意，你甚至可以把一部分用于记录二进制位为 0 的点随机连接到其他编号在 2501 \sim 5000 中的点，使得这个树在交互库看来更加随机，反正我们最终以是否连接到表示二进制位为 1 的点来判断 N 每一个二进制位的值是否为 1，所以没有任何问题。

至于前面 2500 个点之间怎么连边，那就随便了，我是将每个点随机连到比它编号小的一个点上。

这样做唯一的弱点就是在交互库删除叶子节点所连接的边是会导致正确率降低，但是大致估测凭感觉发现这样的边数通常大于 3000（由于随机，编号在 1251 \sim 2500 的点很多就是叶子节点），极端情况下正确率仍可接受（实测提交 4 次全部通过）。

如果你怕被卡也可以选定一个随机种子，把点的编号打乱（事实证明这种方法对于毒瘤的交互库来说几乎没用），当然我没有打乱也过了。

#include<bits/stdc++.h>
using namespace std;
long long setN(int n);
#include<bits/stdc++.h>
using namespace std;
long long setN(int n);
vector<pair<int,int> > Alice(){
    long long t=setN(5000);
    mt19937 rnd(time(0));
    vector<pair<int,int> > res;
    bool tag;int x;
    for(int i=0;i<60;i++){
        tag=(t&(1ll<<i))>0;
        for(int j=2501+i;j<=5000;j+=60)
            res.push_back(make_pair(tag?(x=rnd()%1250+1):(x=rnd()%1250+1251),j));
    }
    for(int i=2;i<=2500;i++)
        res.push_back(make_pair(rnd()%(i-1)+1,i));
    return res;
}
long long Bob(vector<pair<int,int> > g){
    long long ans=0;
    for(pair<int,int> e:g){
        if(e.first<=1250&&e.second>2500){
            ans|=(1ll<<((e.second-2501)%60));
        }
    } 
    return ans;
}