题解：P11050 [IOI 2024] 消息篡改者（暂无法评测）

· · 题解

现有公开的做法，好像都本质相同啊——又能有几种做法呢？有将近一半的位置会被修改，我们甚至不知道 Cleopatra 对它们做了什么——

哦不对，其实我们知道 Cleopatra 做了什么。没错，send_packet 函数是有返回值的。

来一个依赖返回值的，极其高手的做法。感谢 lmh 老师和 dx 老师的讨论和指导 /qq

坐稳了！

下面称不会被 Cleopatra 修改的位是好的（记为 1），会被修改的位是坏的（记为 0），将位置 i 的状态记为 C_i。注意这里数字记号和题面是反的，如果你绕不过来就别看了反正也没啥好看的。

将一个数据包的长度记为 N，它等于 31。

由于信息长度不固定，我们先补一个 1，再补一串 0，直到长度 =1025。显然这样可以区分长度，最后把多出来的部分删了就行。而满足 C_i=1 的位总共可以传输 1056 个位，还剩下 31 个。

我们的思路是这样的：

  1. 确定一个好的位；

  2. 利用这个位置找到所有好的位；

  3. 用找到的好位传送信息。

整个通信的过程看似是离线的，但是我们一定要摆脱离线的思维定势。因为我们有获得返回值的能力，所以我们可以得知 Basma 具体收到了什么，进而改变发送的内容，也就是将离线强制转为在线。

在一次发送信息的过程中，可以让一个位 u 记录位置 v 的类型——令 A_u=C_v 即可。如果 u 是好的，那么结果一定真实；否则，结果可能被 Cleopatra 篡改。称其为一次询问。如果 C_u=1 则为有效询问，否则为无效询问。

由于 1 是绝对众数，我们考虑摩尔投票。具体而言，维护一个栈，按顺序扫描每个位 i：

显然最后栈中 1 比 0 更多，而且不可能出现连续的 10。证明是简单的：如果出现 C_u=1 之后紧跟 C_v=0，那么在处理 v 的时候应该将它们一起弹出去。所以最后栈顶一定是一个好位置。

这个过程是可以实现的原因是，我们每次得到了返回值。所以说 A 可以预测到 B 的行为，而 B 只需要顺着既定流程走就行了，并不会改变历史。

现在有一个问题——一次询问就会消耗一个二进制位，而这样做完之后最坏情况下已经进行了 30 次询问，如何用剩下的询问确定所有好的的位置呢？

首先可以观察到，无效询问不会占用信息量，因为这个位本来就传不了信息。

现在忘掉之前的栈，考虑如下问题：我们已经进行了多次询问，它们的结果全部已知；我们还知道一个 C_i=1 的 i；接下来需要用更多的询问确定所有 C_i，但是有效询问至多只能有 31 个，而且总的询问次数 \le 66。

对操作建树，如果 u 查询 v，就从 u 向 v 连一条有向边，连成一条森林，显然这个森林当中所有节点满足 fa_i<i（除非 i 为树根）。

设已经确定的那个好位为 s。我们每次找到编号最小的 p，满足 p 还未确定。通过一次询问 (u=s,v=p) 来判断 p 的实际好坏。若 p 是一个好位置，那么因为 p 说真话，所以 p 的所有儿子都可以根据刚刚的询问直接确定。这样的关系可以递归下去，因此可以一次性填好所有能确定的位置，再重复这个过程，直到所有位置都被确定为止。

考虑每个有效询问，发现它恰好确定了一个点的状态。并且每个节点只会被一个有效询问更新——首先在维护栈的过程中，每个节点最多被询问一次；而如果这个询问有效，那么遍历到它之前它的父亲一定已经被确定了，这样它也会被确定下来，就不会被多次访问了。

这样询问的总数 \le 2N，其中有效询问至多只有 N 次。

因此我们在 66 包内解决了这个问题！！！！！！！！！！

#include"message.h"
#include<bits/stdc++.h>
using namespace std;
void send_message(vector<bool> M,vector<bool> C){
    for (int i=0;i<31;++i) C[i]=!C[i];
    M.emplace_back(1);
    while(M.size()<66*16) M.emplace_back(0);
    int pos_M=0,cnt=0,bad=0;
    vector<bool> A(31);
    vector<int> vis(31),fa(31,-1),stk;
    for (int i=0;i<31;++i){
        if (stk.empty()){stk.push_back(i);continue;}
        else{
            A[stk.back()]=C[i];
            bad+=C[stk.back()];
            fa[i]=stk.back();
            for (int j=0;j<31;++j) if (C[j]&&(j!=stk.back())) A[j]=M[pos_M++];
            auto vec=send_packet(A);
            ++cnt;
            if (vec[stk.back()]==0){
                stk.pop_back();
            }
            else stk.emplace_back(i);
        }
    }
    assert(stk.size());
    int lst=stk.back();vis[lst]=1;
    for (++cnt;cnt<=66;++cnt){
        int p=-1;
        for (int i=0;i<31;++i) if (!vis[i]){p=i;break;}
        if (p!=-1) A[lst]=C[p],++bad;
        for (int i=0;i<31;++i) if (C[i]&&(i!=lst||p==-1)) A[i]=M[pos_M++];
        send_packet(A);
        if (p==-1) continue;
        vis[p]=1;
        for (int i=p+1;i<31;++i) if (fa[i]!=-1&&C[fa[i]]&&vis[fa[i]]) vis[i]=1;
    }
    assert(pos_M>=1025);
}
vector<bool> receive_message(vector<vector<bool> > R){
    vector<bool> ans;
    vector<int> ok[66],vis(31),qry(31),C(31),stk,fa(31,-1);
    for (int i=0;i<66;++i) ok[i].resize(31);
    int L=0,bad=0;
    for (int i=0;i<31;++i){
        if (stk.empty()){stk.push_back(i);continue;}
        else{
            int x=stk.back();fa[i]=x;
            int k=qry[i]=R[L][x];ok[L++][x]=1;++bad;
            if (k) stk.emplace_back(i);
            else{
                stk.pop_back();
            }
        }
    }
    assert(stk.size());
    int lst=stk.back();C[lst]=vis[lst]=1;
    for (;L<66;++L){
        int p=-1;
        for (int i=0;i<31;++i) if (!vis[i]){p=i;break;}
        if (p==-1) break;
        int k=R[L][lst];ok[L][lst]=1;++bad;
        C[p]=k;vis[p]=1;
        if (k) for (int i=p+1;i<31;++i) if (vis[i]==0&&fa[i]!=-1&&C[fa[i]]){
            vis[i]=1;C[i]=qry[i];
        }
    }
    for (int i=0;i<66;++i) for (int j=0;j<31;++j) if (ok[i][j]==0&&C[j]) ans.emplace_back(R[i][j]);
    assert(ans.size()>=1025);
    while(ans.back()==0) ans.pop_back();ans.pop_back();
    return ans;
}