P16382 [IATI 2025] Bits and Tree【通信题尚未配置】

给定一个长度为 $2N$ 的二进制字符串 $S$。你的任务是利用一棵含有 $N$ 个节点的**无标号无向树**，对 $S$ 的**尽可能长的前缀**进行编码。 为此，你需要编写两个函数：一个编码器和一个解码器。你的编码器将接收二进制字符串，并构造一棵节点编号为 $0$ 到 $N-1$ 的树。然而，通信媒介并不可靠，它会**损坏这棵树**：额外添加一个新节点，并将其连接到原 $N$ 个节点中的某一个。解码器只会收到这棵被损坏的树，此时树具有 $N+1$ 个节点和 $N$ 条边。此外，在传递给解码器之前，节点编号、边以及每条边的两个端点都会被随机打乱。这模拟了向解码器传递一棵**无标号**树的情形。解码器只能依赖树的结构，而不能对节点编号做任何假设。 你的解码器必须返回一个字符串，该字符串需要在**无论损坏发生在何处**的情况下，与原字符串 $S$ 共享尽可能长的公共前缀。你的得分将取决于在所有可能的损坏情形中，以及在所有测试点的所有子测试中，公共前缀长度的最小值。 ### 实现细节 你需要实现以下函数： ```cpp std::vector encode(int n, std::vector data) ``` 该函数接收：一个整数 $N$（允许你使用的节点数量）以及一个布尔向量 $\texttt{data}$，表示二进制字符串 $S$。它应当返回一个由 $N-1$ 条边组成的列表，这些边构成一棵包含 $N$ 个节点的树（采用 0 基索引）。 ```cpp std::vector decode(int n, std::vector tree) ``` 该函数接收：一个整数 $N$（即传递给 $\texttt{encode}$ 的原始值）以及一个由 $N$ 条边组成的向量，这些边构成一棵具有 $N+1$ 个节点的树（损坏后的版本）。它应当返回一个二进制位序列，该序列应在尽可能长的前缀上与原始 $\texttt{data}$ 匹配。 对于一个给定的测试点，评测器会运行 $1$ 个编码器实例以及 $N$ 个不同的解码器实例。每个实例对应的函数都会被调用 $T$ 次——即该测试点所含子测试的数量。 你的程序不应实现 $\verb|main|$ 函数，也不应与标准输入输出进行交互。它将与一个系统评测器一同编译，由后者处理这些部分。 ### 本地测试 我们提供了一个本地评测器以帮助你测试自己的解答。它需要与你的程序一起编译，且不使用独立进程。 该评测器会模拟完整的编码/解码流程： - 读入一个整数 $T$ —— 子测试的数量。 - 对于每个测试用例： - 读入一个整数 $N$ —— 可供编码使用的节点数。 - 读入一个整数 $\ell$ —— 二进制数据串的长度（通常为 $2N$）。 - 读入 $\ell$ 个二进制位（每个为 $0$ 或 $1$，之间无空格），表示二进制字符串 $S$。 - 调用你的 $\verb|encode(n, data)|$ 函数。 - 尝试损坏生成的树，具体方式为： - 遍历每个 $x$ —— 新节点所要挂载到的原节点编号（从 $0$ 到 $N-1$）。 - 添加一个新节点，并将其连接到节点 $x$。 - 随机打乱节点编号，打乱边表，并随机交换每条边的两个端点。 - 用每种损坏后的树调用你的 $\verb|decode(n, corrupted_edges)|$ 函数。 - 将每个结果与原始数据进行比较，统计最短匹配前缀中与原字符串一致的二进制位数量。

无

无

### 交互示例 输入 ``` 1 5 10 1101010110 ``` 交互过程 ``` encode(5, {1,1,0,1,0,1,0,1,1,0}) 返回 {{0,1},{1,2},{0,3},{1,4}} decode(5, {{1,0},{0,2},{2,3},{3,4},{5,3}}) 返回 {1,1,0} decode(5, {{1,0},{0,2},{0,3},{4,0},{5,4}}) 返回 {1,1,1,0,1,0,1,0} decode(5, {{2,0},{2,1},{1,3},{4,1},{5,4}}) 返回 {1,1,1,0,0,0,0,0} decode(5, {{0,1},{0,2},{0,3},{4,3},{3,5}}) 返回 {1,1,1,0,1} decode(5, {{1,0},{1,2},{2,3},{4,2},{5,4}}) 返回 {1,1,1,0} ``` ### 数据范围 - $T = 2$ - $N = 200$ - $|\texttt{data}| = 2N$ - 未损坏的树中，节点编号范围为 $0$ 到 $N-1$。 - 损坏后的树中，节点编号范围为 $0$ 到 $N$。 ### 计分 你在本题的最终得分（占满分的比例）取决于你的解答所正确解码的二进制位数。 如果你的解答产生了无效的树，你将会得到 $0$ 分。 否则，你的得分 $S$ 将根据以下分段线性函数计算： :::align{center}  ::: 正确解码的二进制位数取所有测试点、子测试以及损坏情形下的最小值。 翻译由 DeepSeek V4 Pro 完成