qoj9237. Message(通信,adhoc,基环树)
首先这题字符串长度不固定，考虑在字符串后面加一个 \(100\ldots0\)，补成一个长度为 \(1025\) 的串，把这个串传递过去后再把得到的串最后一个 \(1\) 后面的删掉即可。
设传递的信息是 \(R_1,R_2,\ldots,R_{66}\)。注意到这题只有 \(66\times 16=1056\) 个真实信息，所以第一个人必须用至多 \(31\) 次真实信息来让第二个人识别出 \(16\) 个真实位，剩余真实信息用于传递字符串。
一个很有创造性的想法是对于一个真实位 \(x\)，设 \(x\) 在真实位中的后继是 \(y\)（末尾的后继就是开头），令 \(d=(y-x)\bmod 31\)，让 \(R_{1,x}=R_{2,x}=\ldots=R_{d-1,x}=0,R_{d,x}=1\)，\(R_{d+1,x}\sim R_{66,x}\) 传递字符串。由于 \(\sum d=31\)，所以传递字符串的信息数量刚好够。
第二个人识别时，对每位 \(x\) 找到最小的 \(i\) 满足 \(R_{i,x}=1\)，连一条 \(x\to (x+i)\bmod 31\) 的有向边，容易发现会连出来一个基环树。最终的真实位会在这个基环树上构成一个大小为 \(16\) 的环。注意到一个 \(31\) 个点的基环树至多只有一个大小为 \(16\) 的环，所以真实位构成的环是唯一的！求出这个环之后再依次枚举其余真实信息即可得到传递的字符串。
代码
#include "message.h"
#include <bits/stdc++.h>#ifdef ORZXKR
#include "grader.cpp"
#endifvoid send_message(std::vector<bool> M, std::vector<bool> C) {M.emplace_back(1);for (; M.size() < 1025; M.emplace_back(0)) {}std::vector<std::vector<bool>> R(66, std::vector<bool>(31));std::vector<int> pos;for (int i = 0; i < 31; ++i)if (!C[i])pos.emplace_back(i);int now = 0;for (int i = 0; i < pos.size(); ++i) {int d = (pos[(i + 1) % pos.size()] - pos[i] + 31) % 31;assert(d);R[d - 1][pos[i]] = 1;for (int j = d; j < R.size(); ++j) R[j][pos[i]] = M[now++];}for (auto &x : R) send_packet(x);
}std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {static int nxt[31];for (int i = 0; i < 31; ++i) {nxt[i] = -1;for (int j = 0; j < R.size(); ++j) {if (R[j][i]) {nxt[i] = (i + j + 1) % 31;break;}}// std::cerr << i << " : " << nxt[i] << '\n';}std::vector<int> pos;for (int i = 0; i < 31; ++i) {static bool vis[31];if (nxt[i] == -1) continue;memset(vis, 0, sizeof(vis));std::vector<int> vec;for (int j = i; !vis[j]; j = nxt[j]) {vec.emplace_back(j);vis[j] = 1;}if (vec.size() == 16 && nxt[vec.back()] == vec[0]) {pos = vec;break;}}assert(pos.size() == 16);std::vector<bool> M;for (int i = 0; i < pos.size(); ++i) {int d = (pos[(i + 1) % pos.size()] - pos[i] + 31) % 31;for (int j = d; j < R.size(); ++j) M.emplace_back(R[j][pos[i]]);}for (; M.back() == 0; M.pop_back()) {}M.pop_back();return M;
}