模拟题6——CSP202506C 消息解码

一、整体题意

题目给出 (n) 条长度固定为 72 位的二进制消息，要求按照消息的编码规则，将每条消息转换成对应的文字形式。

每条消息包含：

• 接收方代号；

• 发送方代号；

• 可选的发送方位置编号。

根据第一个二进制位，消息分为两种：

• 第一个二进制位是0：简单消息；

• 第一个二进制位是1：复杂消息。

困难之处在于：消息中不一定直接保存完整代号，也可能只保存代号的散列值。此时需要根据之前消息中直接出现过的代号进行推断。

二、两种消息的结构

1. 简单消息

简单消息的 72 位结构如下：

其中，28 位代号字段有两种情况：

• 如果数值小于 (2^{25})，表示代号的 25 位散列值；

• 如果数值不小于 (2^{25})，表示典型代号的短数字表示加上 (2^{25})。

位置编号：

• 等于 0：消息不包含位置；

• 不等于 0：直接输出对应位置编号。

2. 复杂消息

复杂消息的 72 位结构如下：

最后一位表示完整代号属于哪一方：

• 0：完整代号是发送方，散列值代号是接收方；

• 1：完整代号是接收方，散列值代号是发送方。

三、输出规则

每条消息输出格式为：

接收方代号 发送方代号 位置

如果消息中没有位置，则只输出：

接收方代号 发送方代号

代号有三种输出方式：

1. 代号由完整数字表示或者短数字表示直接解析得到：

ABCD200_3

1. 代号通过散列值推断得到，需要添加#：

#ABCD200_3

1. 散列值无法推断：

###

四、思路解析

1. 二进制字段转换成整数

每一条消息都是一个长度为 72 的字符串。我们需要从中提取某一段二进制，并转换成整数。

例如，简单消息中：

• bits[1]开始的 28 位是接收方；

• bits[29]开始的 28 位是发送方；

• bits[57]开始的 15 位是位置。

可以逐位完成二进制转十进制：

ull getBinaryValue(const string& bits, int start, int length) { ull value = 0; for (int i = start; i < start + length; i++) { value = value * 2 + (bits[i] - '0'); } return value; }

假设当前二进制已经解析出101，其十进制值为 5。

如果继续读入一位1，新的结果就是：5 × 2+1=11

对应二进制1011。

由于完整代号只占 58 位，使用unsigned long long就能保存。

2. 完整数字表示还原代号

一个代号会补充到 11 位，然后看作一个 11 位的 38 进制数。

字符与数字的对应关系为：

因此，可以不断对数字表示除以 38，从后往前还原字符。

string decodeNormal(ull value) { string result(11, ' '); for (int i = 10; i >= 0; i--) { int x = value % 38; value /= 38; if (x == 0) { result[i] = ' '; } else if (x <= 10) { result[i] = char('0' + x - 1); } else if (x <= 36) { result[i] = char('A' + x - 11); } else { result[i] = '_'; } } while (!result.empty() && result.back() == ' ') { result.pop_back(); } return result; }

这里的关键是从后往前填写字符。

因为value mod 38得到的是最低位，也就是代号的最后一个字符。

原代号不足 11 位时，会在结尾补空格，因此解析完成后需要删除结尾的空格。

3. 典型代号的短数字表示

典型代号长度为 5 或 6 位，格式为：

第一部分 + 一位数字 + 三位字母

其中第一部分长度为 1 或 2，可以是数字或大写字母。

例如：

A0BCD 12AABC

五位代号会在开头补一个空格，变成六位代号。

六个位置对应的取值数量分别为：

因此，这是一个混合进制数。

从最后一位开始依次：

• 对 26 取模，得到第六位；

• 对 26 取模，得到第五位；

• 对 26 取模，得到第四位；

• 对 10 取模，得到第三位；

• 对 36 取模，得到第二位；

• 剩余部分为第一位。

string decodeShort(ull value) { int c6 = value % 26; value /= 26; int c5 = value % 26; value /= 26; int c4 = value % 26; value /= 26; int c3 = value % 10; value /= 10; int c2 = value % 36; value /= 36; int c1 = value; string result; if (c1 != 0) { if (c1 <= 10) { result += char('0' + c1 - 1); } else { result += char('A' + c1 - 11); } } if (c2 <= 9) { result += char('0' + c2); } else { result += char('A' + c2 - 10); } result += char('0' + c3); result += char('A' + c4); result += char('A' + c5); result += char('A' + c6); return result; }

第一位有三种情况：

• 0：补充的空格，不输出；

• 1～10：数字0～9；

• 11～36：字母A～Z。

第二位不允许为空格，因此对应方式与第一位略有不同：

• 0～9：数字0～9；

• 10～35：字母A～Z。

4. 将代号重新转换成完整数字表示

简单消息中的典型代号通过短数字表示直接解析得到。

但是后面的消息可能会使用这个代号的 12 位或 25 位散列值，因此我们必须计算它的完整数字表示。

完整数字表示本质上就是 38 进制：

ull encodeNormal(const string& name) { ull value = 0; for (int i = 0; i < 11; i++) { int x = 0; if (i < (int)name.size()) { char c = name[i]; if (c >= '0' && c <= '9') { x = c - '0' + 1; } else if (c >= 'A' && c <= 'Z') { x = c - 'A' + 11; } else { x = 37; } } value = value * 38 + x; } return value; }

如果代号长度不足 11，那么剩余位置对应补充的空格，数字为 0。

每加入一个新字符，都执行：
value=value×38+x

这就是标准的进制转换过程。

72 位短消息解码——混合进制、散列计算与历史信息维护

一、整体题意

题目给出 (n) 条按照接收顺序排列的消息，每条消息都是一个长度为 72 的二进制字符串。

我们需要将每条二进制消息转换成如下文字形式：

接收方代号 发送方代号 发送方位置

如果消息中没有位置，则只输出：

接收方代号 发送方代号

72 位消息分为两种：

• 第一位为0：简单消息；

• 第一位为1：复杂消息。

题目的主要难点有四个：

1. 将代号的普通数字表示还原成字符串；

2. 将典型代号的短数字表示还原成字符串；

3. 按照题目公式正确计算 12 位和 25 位散列值；

4. 根据此前消息中直接出现过的代号推断散列值对应的代号。

二、两种消息的结构

1. 简单消息

简单消息共 72 位，结构如下：

28 位的代号字段有两种可能。

如果字段值小于 (2^{25})，它表示代号的 25 位散列值。

如果字段值不小于 (2^{25})，它表示：典型代号的短数字表示+2²⁵

因此，真正的短数字表示为：字段值-2²⁵

最后 15 位是位置编号：

• 为 0：消息中不包含位置；

• 不为 0：输出对应的位置编号。

2. 复杂消息

复杂消息的结构如下：

最后一位表示完整代号属于哪一方：

• 0：完整代号是发送方，散列值是接收方；

• 1：完整代号是接收方，散列值是发送方。

三、思路解析

1. 提取二进制字段

一条消息是字符串形式的二进制序列。

我们编写一个函数，从指定位置开始读取若干位，并转换成十进制整数：

ull getBinaryValue(const string& s, int start, int length) { ull value = 0; for (int i = start; i < start + length; i++) { value = value * 2 + (s[i] - '0'); } return value; }

例如：

getBinaryValue(bits, 1, 28);

表示从下标 1 开始，读取 28 个二进制位。

每读取一个二进制位，相当于：value=value×2+当前位

这里使用：

using ull = unsigned long long;

因为完整代号的数字表示最多占 58 位，可以存入 64 位无符号整数。

2. 还原普通代号

一个普通代号最多有 11 个字符，不足 11 位时在结尾补空格。

每个字符对应一个 (0\sim37) 的数字：

代号的数字表示为：

因此，它本质上是一个 11 位的 38 进制数。

不断进行：

value % 38

可以从后往前取得每一位。

string decodeNormal(ull value) { string result(11, ' '); for (int i = 10; i >= 0; i--) { int x = value % 38; value /= 38; if (x == 0) { result[i] = ' '; } else if (x <= 10) { result[i] = char('0' + x - 1); } else if (x <= 36) { result[i] = char('A' + x - 11); } else { result[i] = '_'; } } while (!result.empty() && result.back() == ' ') { result.pop_back(); } return result; }

为什么要删除结尾空格？

代号不足 11 位时，是在结尾补空格。

例如：

ABC

会被补成：

ABC________

这里用_表示空格。

解码完成后，需要删除这些结尾补充的空格，才能得到原代号。

3. 还原典型代号的短数字表示

典型代号长度为 5 或 6，其格式为：

第一部分 + 一位数字 + 三位大写字母

其中第一部分长度为 1 或 2，每个字符只能是数字或大写字母。

例如：

A0BCD AB0CDE 12AABC

如果原代号长度为 5，会在开头补一个空格，变成 6 位。

六个位置的取值数量分别为：

这不是普通的统一进制，而是一个混合进制数。

可以按照从后往前的顺序依次取模：

string decodeShort(ull value) { int c6 = value % 26; value /= 26; int c5 = value % 26; value /= 26; int c4 = value % 26; value /= 26; int c3 = value % 10; value /= 10; int c2 = value % 36; value /= 36; int c1 = value; string result; if (c1 != 0) { if (c1 <= 10) { result += char('0' + c1 - 1); } else { result += char('A' + c1 - 11); } } if (c2 <= 9) { result += char('0' + c2); } else { result += char('A' + c2 - 10); } result += char('0' + c3); result += char('A' + c4); result += char('A' + c5); result += char('A' + c6); return result; }

第一位的编码规则和其他位置不同：

• 0表示补充的空格；

• 1～10表示数字0～9；

• 11～36表示字母A～Z。

如果c1 == 0，说明原代号长度为 5，因此不输出第一位。

第二位的编码规则是：

• 0～9表示数字0～9；

• 10～35表示字母A～Z。

所以第二位不能和第一位使用完全相同的转换方法。

4. 将代号字符串转换成普通数字表示

简单消息中的典型代号只能得到短数字表示。

但是如果想计算它的 12 位和 25 位散列值，就必须先得到它的普通数字表示。

因此还需要编写普通代号的编码函数：

ull encodeNormal(const string& name) { ull value = 0; for (int i = 0; i < 11; i++) { int x = 0; if (i < (int)name.size()) { char c = name[i]; if (c >= '0' && c <= '9') { x = c - '0' + 1; } else if (c >= 'A' && c <= 'Z') { x = c - 'A' + 11; } else { x = 37; } } value = value * 38 + x; } return value; }

每次执行：

value = value * 38 + x;

相当于向 38 进制数的末尾添加一位。

如果当前下标超过代号的实际长度，则当前字符是补充的空格，其数字为 0。

5. 计算代号的散列值

代号的 (n) 位散列值计算公式为：

其中 (x) 是代号的普通数字表示。

先乘以常数：

x * 47055833459

然后除以：

对于整数来说，除以 (2^k) 等价于向右移动 (k) 位：

product >> (64 - n)

最后对 (2^n) 取模，等价于只保留最低的 (n) 位。

ull getHash(ull value, int n) { u128 product = (u128)value * HASH_CONSTANT; product >>= (64 - n); ull mask = (1ULL << n) - 1; return (ull)product & mask; }

为什么使用unsigned __int128？

完整代号占用最多 58 位，而常数47055833459大约占用 36 位。

两者相乘最多可能需要约：58+36=94位。

unsigned long long只有 64 位，乘法会发生溢出。因此必须使用 GCC 提供的 128 位无符号整数：

using u128 = unsigned __int128;

6. 如何根据散列值推断代号

如果消息中的某一方使用散列值表示，就需要在之前直接出现过的代号中寻找匹配项。

能够用于推断的代号只有两类：

1. 简单消息中，由短数字表示直接解码出的典型代号；

2. 复杂消息中，由完整数字表示直接解码出的代号。

通过散列值间接推断出来的代号，不能再次用于后续推断。

例如：

#ABCD200_3

虽然成功推断出了ABCD200_3，但它不能被加入历史记录。

7. 如何找到最近出现的匹配代号

一种直接思路是：每次遇到散列值，都从前往后扫描所有历史消息。

但是如果消息数量较大，这种方法的最坏时间复杂度为：O(²)

实际上，题目只需要“最近出现”的匹配代号，因此可以使用两个哈希表：

unordered_map<ull, string> latest12; unordered_map<ull, string> latest25;

含义分别是：

• latest12[h]：最近直接出现的、12 位散列值为h的代号；

• latest25[h]：最近直接出现的、25 位散列值为h的代号。

加入一个直接出现的代号时，同时计算它的两种散列值：

void addDirectName( ull normalValue, const string& name, unordered_map<ull, string>& latest12, unordered_map<ull, string>& latest25 ) { latest12[getHash(normalValue, 12)] = name; latest25[getHash(normalValue, 25)] = name; }

如果同一个散列值已经存在，直接覆盖旧值即可，因为新代号出现得更晚。

8. 处理同一条消息中双方同时匹配的情况

题目规定：

如果最后收到的消息中的收发双方代号的散列值都符合，则使用最后收到的消息中发送方的代号。

因此，如果一条简单消息中的双方代号都是短数字表示，两者都可以加入历史记录。

更新顺序必须是：

1. 先更新接收方；

2. 再更新发送方。

if (receiverDirect) { addDirectName(...); } if (senderDirect) { addDirectName(...); }

如果双方散列值相同，后加入的发送方会覆盖接收方，从而满足题目的优先级要求。

9. 推断代号的输出格式

如果在历史记录中找到对应散列值，则在代号前添加#：

#ABCD200_3

如果找不到，则输出：

###

对应函数为：

string inferName( ull hashValue, const unordered_map<ull, string>& history ) { auto it = history.find(hashValue); if (it == history.end()) { return "###"; } return "#" + it->second; }

10. 解析简单消息

简单消息的三个字段分别位于：

ull receiverField = getBinaryValue(bits, 1, 28); ull senderField = getBinaryValue(bits, 29, 28); ull position = getBinaryValue(bits, 57, 15);

注意字符串下标从 0 开始：

• bits[0]：消息类型；

• 下标1～28：接收方；

• 下标29～56：发送方；

• 下标57～71：位置。

对于代号字段：

if (receiverField >= SHORT_FLAG)

说明它是短数字表示。

真正的短数字表示为：

ull shortValue = receiverField - SHORT_FLAG;

否则，它就是 25 位散列值，需要从latest25中查找。

发送方的处理方法完全相同。

完成解析后输出：

cout << receiverName << ' ' << senderName; if (position != 0) { cout << ' ' << position; } cout << '\n';

位置为 0 时，不输出第三部分。

11. 解析复杂消息

复杂消息的三个字段为：

ull normalValue = getBinaryValue(bits, 1, 58); ull hashValue = getBinaryValue(bits, 59, 12); int relation = bits[71] - '0';

完整数字表示可以直接还原：

string directName = decodeNormal(normalValue);

12 位散列值需要从latest12中查找：

string inferredName = inferName(hashValue, latest12);

如果最后一位为0，完整代号是发送方：

cout << inferredName << ' ' << directName << '\n';

如果最后一位为1，完整代号是接收方：

cout << directName << ' ' << inferredName << '\n';

12. 为什么必须先解析，再更新历史？

题目规定，推断代号时，只能使用收到当前消息之前已经出现过的代号。

假设当前复杂消息的完整代号是ABCD200_5，另一方使用散列值表示。

即使ABCD200_5的散列值恰好与另一方的散列值相同，也不能使用当前消息中的ABCD200_5完成推断。

因此处理顺序必须是：

1. 使用旧的历史记录推断当前消息；

2. 输出当前消息；

3. 把当前消息中直接出现的代号加入历史。

也就是：

string inferredName = inferName(hashValue, latest12); cout << ...; addDirectName(normalValue, directName, latest12, latest25);

不能把addDirectName放到推断之前。

四、总结

这道题表面上是一道较长的模拟题，实际可以分解成四个相对独立的部分：

1. 二进制字段提取；

2. 普通 38 进制代号解码；

3. 典型代号的混合进制解码；

4. 使用哈希表维护散列值最近对应的直接代号。

其中最容易出错的地方有：

• 短数字表示需要先减去 (2^{25})；

• 散列值乘法必须使用unsigned __int128；

• 散列值推断只能使用以前直接出现过的代号；

• 当前消息中的代号不能用于推断当前消息；

• 同一条消息双方都匹配时，发送方的优先级更高；

• 推断出来的代号前需要添加#；

• 无法推断时输出###；

• 更新历史时应当先更新接收方，再更新发送方。

使用两个哈希表分别维护 12 位和 25 位散列值对应的最近代号，就能避免向前扫描所有消息。

时间复杂度为：O(n)

空间复杂度为：O(n)

五、完整代码

#include <iostream> #include <string> #include <unordered_map> using namespace std; using ull = unsigned long long; using u128 = unsigned __int128; const ull HASH_CONSTANT = 47055833459ULL; const ull SHORT_FLAG = 1ULL << 25; /* * 从二进制字符串中提取一段，并转换为十进制整数。 * * start：起始下标 * length：读取的二进制位数 */ ull getBinaryValue(const string& s, int start, int length) { ull value = 0; for (int i = start; i < start + length; i++) { value = value * 2 + (s[i] - '0'); } return value; } /* * 将普通代号的数字表示还原为字符串。 * * 普通代号相当于一个11位的38进制数。 */ string decodeNormal(ull value) { string result(11, ' '); for (int i = 10; i >= 0; i--) { int x = value % 38; value /= 38; if (x == 0) { result[i] = ' '; } else if (x <= 10) { result[i] = char('0' + x - 1); } else if (x <= 36) { result[i] = char('A' + x - 11); } else { result[i] = '_'; } } // 删除编码时在代号结尾补充的空格 while (!result.empty() && result.back() == ' ') { result.pop_back(); } return result; } /* * 将典型代号的短数字表示还原为字符串。 * * 六个位置分别使用： * 37、36、10、26、26、26种取值。 */ string decodeShort(ull value) { int c6 = value % 26; value /= 26; int c5 = value % 26; value /= 26; int c4 = value % 26; value /= 26; int c3 = value % 10; value /= 10; int c2 = value % 36; value /= 36; int c1 = value; string result; /* * 第一位： * 0表示补充的空格； * 1～10表示数字0～9； * 11～36表示字母A～Z。 */ if (c1 != 0) { if (c1 <= 10) { result += char('0' + c1 - 1); } else { result += char('A' + c1 - 11); } } /* * 第二位： * 0～9表示数字0～9； * 10～35表示字母A～Z。 */ if (c2 <= 9) { result += char('0' + c2); } else { result += char('A' + c2 - 10); } // 第三位一定是数字 result += char('0' + c3); // 最后三位一定是大写字母 result += char('A' + c4); result += char('A' + c5); result += char('A' + c6); return result; } /* * 将代号字符串转换成普通数字表示。 * * 主要用于把简单消息中的短代号转换成普通数字表示， * 从而计算它的12位和25位散列值。 */ ull encodeNormal(const string& name) { ull value = 0; for (int i = 0; i < 11; i++) { int x = 0; if (i < (int)name.size()) { char c = name[i]; if (c >= '0' && c <= '9') { x = c - '0' + 1; } else if (c >= 'A' && c <= 'Z') { x = c - 'A' + 11; } else if (c == '_') { x = 37; } } value = value * 38 + x; } return value; } /* * 计算代号的n位散列值。 * * 由于乘法结果可能超过64位，因此使用unsigned __int128。 */ ull getHash(ull value, int n) { u128 product = (u128)value * HASH_CONSTANT; // 除以2^(64-n) product >>= (64 - n); // 对2^n取模，即保留最低n位 ull mask = (1ULL << n) - 1; return (ull)product & mask; } /* * 将直接出现的代号加入历史记录。 * * 一个代号同时需要记录它的12位和25位散列值。 */ void addDirectName( ull normalValue, const string& name, unordered_map<ull, string>& latest12, unordered_map<ull, string>& latest25 ) { ull hash12 = getHash(normalValue, 12); ull hash25 = getHash(normalValue, 25); latest12[hash12] = name; latest25[hash25] = name; } /* * 根据散列值从历史记录中推断代号。 */ string inferName( ull hashValue, const unordered_map<ull, string>& history ) { auto it = history.find(hashValue); if (it == history.end()) { return "###"; } return "#" + it->second; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; /* * latest12[h]： * 最近直接出现的、12位散列值为h的代号。 * * latest25[h]： * 最近直接出现的、25位散列值为h的代号。 */ unordered_map<ull, string> latest12; unordered_map<ull, string> latest25; while (n--) { string bits; cin >> bits; if (bits[0] == '0') { /* * 简单消息： * * 1位消息类型 * 28位接收方 * 28位发送方 * 15位位置 */ ull receiverField = getBinaryValue(bits, 1, 28); ull senderField = getBinaryValue(bits, 29, 28); ull position = getBinaryValue(bits, 57, 15); string receiverName; string senderName; // 记录双方是不是直接出现的短代号 bool receiverDirect = false; bool senderDirect = false; // 直接代号对应的普通数字表示 ull receiverNormalValue = 0; ull senderNormalValue = 0; /* * 解析接收方。 * * 不小于2^25：短数字表示； * 小于2^25：25位散列值。 */ if (receiverField >= SHORT_FLAG) { ull shortValue = receiverField - SHORT_FLAG; receiverName = decodeShort(shortValue); receiverNormalValue = encodeNormal(receiverName); receiverDirect = true; } else { receiverName = inferName(receiverField, latest25); } /* * 解析发送方。 */ if (senderField >= SHORT_FLAG) { ull shortValue = senderField - SHORT_FLAG; senderName = decodeShort(shortValue); senderNormalValue = encodeNormal(senderName); senderDirect = true; } else { senderName = inferName(senderField, latest25); } /* * 输出当前消息。 */ cout << receiverName << ' ' << senderName; if (position != 0) { cout << ' ' << position; } cout << '\n'; /* * 当前消息不能参与当前消息的散列值推断， * 因此必须在解析和输出完成之后更新历史。 * * 先加入接收方，再加入发送方。 * 如果双方散列值相同，发送方会覆盖接收方， * 满足题目规定的发送方优先规则。 */ if (receiverDirect) { addDirectName( receiverNormalValue, receiverName, latest12, latest25 ); } if (senderDirect) { addDirectName( senderNormalValue, senderName, latest12, latest25 ); } } else { /* * 复杂消息： * * 1位消息类型 * 58位完整数字表示 * 12位散列值 * 1位双方关系 */ ull normalValue = getBinaryValue(bits, 1, 58); ull hashValue = getBinaryValue(bits, 59, 12); int relation = bits[71] - '0'; // 完整数字表示可以直接解码 string directName = decodeNormal(normalValue); // 12位散列值只能使用此前的历史记录推断 string inferredName = inferName(hashValue, latest12); if (relation == 0) { /* * 完整代号是发送方， * 散列值表示接收方。 */ cout << inferredName << ' ' << directName << '\n'; } else { /* * 完整代号是接收方， * 散列值表示发送方。 */ cout << directName << ' ' << inferredName << '\n'; } /* * 完成当前消息的推断和输出后， * 再把完整代号加入历史记录。 * * 散列值推断出的代号不能加入历史。 */ addDirectName( normalValue, directName, latest12, latest25 ); } } return 0; }

转载请注明出处