AB6 （消息）

时间限制： 2s
空间限制： 256MB

题目类型说明

这是一道提交函数题，并且需要提交一个源文件：

你需要实现两个函数：

std::vector<bool> transmit(const std::vector<bool>& data, int d);
std::vector<bool> receive(const std::vector<bool>& message, int n, int d);

题目描述

火星车 Opportunity 想向地球发送一条消息。但它的设备已经损坏，因此消息中的一部分无法成功传输。

更准确地说，它真正想让地球接收到的是一个长度为 N 的比特串。火星车可以发送一个自己选择长度为 M 的比特串。在发送之前就已知：发送出的消息中恰好有 D 个比特会丢失。

火星车希望构造一个发送消息，使得地球端能够尽可能准确地恢复原始的 N 个比特。

你的任务是设计并实现一套通信协议。

• 函数 transmit 由火星车端使用。它接收原始数据和 D，返回要发送的比特串。
• 函数 receive 由地球端使用。它接收删去若干比特后的消息，以及 N 和 D，并尽可能准确地恢复原始数据。

目标是让这两个函数共同最大化“成功恢复的有效信息量”与“成功发送的信息总量”之间的比值。评分公式如下，其中 correct 表示猜对的比特数：

(2 * correct - N) / max(M - D, N)

实现细节

1. transmit

函数原型：

std::vector<bool> transmit(const std::vector<bool>& data, int d);

它会被恰好调用一次，参数分别为待发送的数据以及将要被删除的比特数。函数应返回将被发送的消息。

2. receive

函数原型：

std::vector<bool> receive(const std::vector<bool>& message, int n, int d);

它也会被恰好调用一次，参数分别为地球端实际收到的消息，以及 N 与 D。函数必须返回一个长度恰好为 N 的比特串，表示恢复结果。

3. 提交要求

• 两个函数必须分别写在 transmit.cpp 与 receive.cpp 中；
• 可以自行编写辅助函数、结构体、变量等；
• 强烈建议除 transmit 与 receive 本身外，其余内容都声明为 static，以防两个文件之间发生命名冲突；
• 两个文件中都不能包含 main 函数；
• 两个文件都必须在开头通过预处理指令包含头文件：

#include "transmission.h"

重要： 这两个函数会在系统中的不同进程里执行，因此它们不能直接交换信息。

限制

• 所有测试中均有 N = 10 000
• 1 <= D <= N / 10
• M <= 100 000

评分说明

本题按测试点单独计分。

对某个测试，若满足以下条件，则你的程序会获得非零分：

• 两个函数都正常结束；
• transmit 返回的向量长度不超过 100000；
• receive 返回的向量长度正确；
• receive 至少猜对一半以上的比特。

该测试所得分数为：

该测试满分 * min(yourScore / authorScore, 1)

其中：

• yourScore 是你按题目给定公式得到的结果；
• authorScore 是作者程序在同一公式下得到的结果。

部分测试带有额外限制。

测试数据说明

发送的数据串在所有测试中都是随机生成的：每一位独立随机，0 与 1 出现概率相同。

被删除的是哪些比特，不会以有意义的方式依赖于你发送消息的内容，而只与消息长度有关；但不同消息对应的删除位置可能不同。删除位置是按若干段相邻比特块随机生成的，每一块长度为 K。

• 15% 的测试：D = 1 且 K = 1，作者最小结果：0.971
• 25% 的测试：D <= 1.1 * sqrt(N) 且 K = 1，作者最小结果：0.771
• 25% 的测试：K = 1，作者最小结果：0.473
• 35% 的测试：无额外限制，作者最小结果：0.432

对于每一组，题面给出了作者程序在该组测试中取得的最小结果，精确到小数点后三位。

本地测试

题目提供了 transmission.h 与 Lgrader.cpp，可与自己的程序一起编译进行本地测试，同时也提供了两个很朴素的示例实现。

在终端中可使用如下命令编译（需在这些文件所在目录下执行）：

g++ -O2 -std=c++11 -o transmission.exe receive.cpp transmit.cpp Lgrader.cpp

运行后，程序会询问 N、D 和 K，随后其余数据会随机生成。你也可以自行修改提供的本地文件来改变测试方式。

示例通信

编号	评测器调用	返回值
1	transmit({0,0,1,0,1,0}, 2)	{0,0,1,0,1,0}
2	receive({0,1,1,0}, 6, 2)	{0,0,0,0,0,0}

示例解释

这次示例通信使用的是题目提供的两份朴素实现。

原始数据是 001010，其中会有两个比特被删除。transmit 没有对消息做任何修改，而是直接发送原串。最终第 2 个和第 4 个比特丢失，因此 receive 收到的是 0110。

而这个朴素版本的 receive 根本没有尝试恢复原始数据，而是直接返回了全零串。

于是这对函数在该测试上的得分为：

(2 * 4 - 6) / 6 = 1 / 3

最终该测试获得多少分，还要与作者程序在该测试上的结果进行比较。