题解：P11050 [IOI 2024] 消息篡改者

· · 题解

更好的阅读体验

这题，牛大了！

省略一些和正解无关的部分分做法。

由于 B 不知道串 M 的长度，我们考虑给这个字符串加一个结束标记。具体地，我们让 A 在 M 后面拼上 0111 \cdots 1，当 B 还原出这个串后，他可以找到最后一个 0，然后把这个 0 直到字符串结尾的这一段删掉。不难发现添加标记后串长至少应该是 1025。

我们参照 [JOIST 2023] 最后之战 / The Last Battle，如果 B 知道了哪几个格子被 ban 掉了，那么剩下的格子都能用来传输信息。

容易计算我们可以操控的字符数量是 66 \times 16 = 1056，恰好就是 1025 + 31。这意味着，我们要用 31 个字符，传输 31 列是否被 ban 掉。

接下来是非人类部分。我们巧妙地想到，可以对于每个能被 A 利用的列，计算出它的后继 nxt_i，也就是下一个能被 A 利用的列。我们将序列连成一个环，因此最后一个能被 A 利用的列的后继是第一个能被 A 利用的列。直接标记后继浪费太多，我们在第 i 列上标记差分数组 d_i = (nxt_i - i) \bmod 31。不难发现所有 d 之和等于 31，也就是我们能用于标记的格子数量！

至于如何标记 d_i，可以在第 i 列从上往下标记 d_i - 1 个 1 和一个 0。B 解码的时候只要从上往下看看最靠上的 0 在第几行，就知道 d_i 是多少了！

然而由于交互库会篡改一些东西，B 在解码的时候可能会得到一些错误的 nxt。我们让 i \to nxt_i 连边，那么正确的 nxt 一定会构成一个大小为 16 的环，然后还可能多出来 15 条边。但是容易发现，由于一个点只有一条出边，所以这个长度为 16 的环是唯一的！环上的点就代表我们可以使用的列。

如果不想写一些很复杂的找环，就直接找一个起点，跳 16 次 nxt，如果能跳回起点且没有重复经过的点，就说明找到了。

最后 B 按照 A 填写 M 的顺序把 M 取出来，再去掉结束标记即可。

那么这道题就做完了。次数卡的非常满。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
vector<bool> send_packet(vector<bool>);
void send_message(vector<bool>,vector<bool>);
vector<bool> receive_message(vector<vector<bool>>);
void send_message(vector<bool> M,vector<bool> C)
{
    M.push_back(0);
    while(M.size()<1025)M.push_back(1);
    int now=0;
    vector<vector<bool> > vec(66);
    for(int i=0;i<66;i++)vec[i].resize(31);
    for(int i=0;i<31;i++)if(!C[i])
    {
        int j=(i+1)%31,step=1;
        for(;C[j];j=(j+1)%31,step++);
        for(int k=0;k<step-1;k++)vec[k][i]=1;
        vec[step-1][i]=0;
        for(int k=step;k<66;k++)vec[k][i]=M[now++];
    }
    for(int i=0;i<66;i++)send_packet(vec[i]);
}
vector<bool> receive_message(vector<vector<bool> > R)
{
    vector<bool> ans,C(31);
    for(int i=0;i<31;i++)C[i]=1;
    vector<int> nxt(31);
    for(int i=0;i<31;i++)
    {
        int j=0; for(;j<66&&R[j][i];j++);
        nxt[i]=(i+j+1)%31;
    }
    for(int i=0;i<31;i++)
    {
        set<int> s; int now=i;
        for(int j=0;j<16;j++)
            s.insert(now),now=nxt[now];
        if(now==i&&s.size()==16) {for(int j:s)C[j]=0; break;}
    }
    for(int i=0;i<31;i++)if(!C[i])
    {
        int j=(i+1)%31,step=1;
        for(;C[j];j=(j+1)%31,step++);
        for(int k=step;k<66;k++)ans.push_back(R[k][i]);
    }
    while(*ans.rbegin())ans.pop_back();
    ans.pop_back();
    return ans;
}

How zak's mind works?