一、整体题意题目给出 (n) 条长度固定为 72 位的二进制消息要求按照消息的编码规则将每条消息转换成对应的文字形式。每条消息包含接收方代号发送方代号可选的发送方位置编号。根据第一个二进制位消息分为两种第一个二进制位是0简单消息第一个二进制位是1复杂消息。困难之处在于消息中不一定直接保存完整代号也可能只保存代号的散列值。此时需要根据之前消息中直接出现过的代号进行推断。二、两种消息的结构1. 简单消息简单消息的 72 位结构如下位数含义第 1 位固定为0接下来 28 位接收方代号接下来 28 位发送方代号最后 15 位发送方位置其中28 位代号字段有两种情况如果数值小于 (2^{25})表示代号的 25 位散列值如果数值不小于 (2^{25})表示典型代号的短数字表示加上 (2^{25})。位置编号等于 0消息不包含位置不等于 0直接输出对应位置编号。2. 复杂消息复杂消息的 72 位结构如下位数含义第 1 位固定为1接下来 58 位一方代号的完整数字表示接下来 12 位另一方代号的 12 位散列值最后 1 位双方关系最后一位表示完整代号属于哪一方0完整代号是发送方散列值代号是接收方1完整代号是接收方散列值代号是发送方。三、输出规则每条消息输出格式为接收方代号 发送方代号 位置如果消息中没有位置则只输出接收方代号 发送方代号代号有三种输出方式代号由完整数字表示或者短数字表示直接解析得到ABCD200_3代号通过散列值推断得到需要添加##ABCD200_3散列值无法推断###四、思路解析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 × 2111对应二进制1011。由于完整代号只占 58 位使用unsigned long long就能保存。2. 完整数字表示还原代号一个代号会补充到 11 位然后看作一个 11 位的 38 进制数。字符与数字的对应关系为数字字符0空格110091136AZ37_因此可以不断对数字表示除以 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五位代号会在开头补一个空格变成六位代号。六个位置对应的取值数量分别为位置可能字符数量第 1 位空格、数字、大写字母37第 2 位数字、大写字母36第 3 位数字10第 4 位大写字母26第 5 位大写字母26第 6 位大写字母26因此这是一个混合进制数。从最后一位开始依次对 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补充的空格不输出110数字091136字母AZ。第二位不允许为空格因此对应方式与第一位略有不同09数字091035字母AZ。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。每加入一个新字符都执行valuevalue×38x这就是标准的进制转换过程。72 位短消息解码——混合进制、散列计算与历史信息维护一、整体题意题目给出 (n) 条按照接收顺序排列的消息每条消息都是一个长度为 72 的二进制字符串。我们需要将每条二进制消息转换成如下文字形式接收方代号 发送方代号 发送方位置如果消息中没有位置则只输出接收方代号 发送方代号72 位消息分为两种第一位为0简单消息第一位为1复杂消息。题目的主要难点有四个将代号的普通数字表示还原成字符串将典型代号的短数字表示还原成字符串按照题目公式正确计算 12 位和 25 位散列值根据此前消息中直接出现过的代号推断散列值对应的代号。二、两种消息的结构1. 简单消息简单消息共 72 位结构如下位数含义1 位固定为028 位接收方代号28 位发送方代号15 位发送方位置28 位的代号字段有两种可能。如果字段值小于 (2^{25})它表示代号的 25 位散列值。如果字段值不小于 (2^{25})它表示典型代号的短数字表示2²⁵因此真正的短数字表示为字段值-2²⁵最后 15 位是位置编号为 0消息中不包含位置不为 0输出对应的位置编号。2. 复杂消息复杂消息的结构如下位数含义1 位固定为158 位一方代号的完整数字表示12 位另一方代号的 12 位散列值1 位双方关系最后一位表示完整代号属于哪一方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 个二进制位。每读取一个二进制位相当于valuevalue×2当前位这里使用using ull unsigned long long;因为完整代号的数字表示最多占 58 位可以存入 64 位无符号整数。2. 还原普通代号一个普通代号最多有 11 个字符不足 11 位时在结尾补空格。每个字符对应一个 (0\sim37) 的数字数字字符0空格110091136AZ37_代号的数字表示为因此它本质上是一个 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 位。六个位置的取值数量分别为位置可能字符数量第 1 位空格、数字、大写字母37第 2 位数字、大写字母36第 3 位数字10第 4 位大写字母26第 5 位大写字母26第 6 位大写字母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; 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表示补充的空格110表示数字091136表示字母AZ。如果c1 0说明原代号长度为 5因此不输出第一位。第二位的编码规则是09表示数字091035表示字母AZ。所以第二位不能和第一位使用完全相同的转换方法。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 位。两者相乘最多可能需要约583694位。unsigned long long只有 64 位乘法会发生溢出。因此必须使用 GCC 提供的 128 位无符号整数using u128 unsigned __int128;6. 如何根据散列值推断代号如果消息中的某一方使用散列值表示就需要在之前直接出现过的代号中寻找匹配项。能够用于推断的代号只有两类简单消息中由短数字表示直接解码出的典型代号复杂消息中由完整数字表示直接解码出的代号。通过散列值间接推断出来的代号不能再次用于后续推断。例如#ABCD200_3虽然成功推断出了ABCD200_3但它不能被加入历史记录。7. 如何找到最近出现的匹配代号一种直接思路是每次遇到散列值都从前往后扫描所有历史消息。但是如果消息数量较大这种方法的最坏时间复杂度为O(²)实际上题目只需要“最近出现”的匹配代号因此可以使用两个哈希表unordered_mapull, string latest12; unordered_mapull, string latest25;含义分别是latest12[h]最近直接出现的、12 位散列值为h的代号latest25[h]最近直接出现的、25 位散列值为h的代号。加入一个直接出现的代号时同时计算它的两种散列值void addDirectName( ull normalValue, const string name, unordered_mapull, string latest12, unordered_mapull, string latest25 ) { latest12[getHash(normalValue, 12)] name; latest25[getHash(normalValue, 25)] name; }如果同一个散列值已经存在直接覆盖旧值即可因为新代号出现得更晚。8. 处理同一条消息中双方同时匹配的情况题目规定如果最后收到的消息中的收发双方代号的散列值都符合则使用最后收到的消息中发送方的代号。因此如果一条简单消息中的双方代号都是短数字表示两者都可以加入历史记录。更新顺序必须是先更新接收方再更新发送方。if (receiverDirect) { addDirectName(...); } if (senderDirect) { addDirectName(...); }如果双方散列值相同后加入的发送方会覆盖接收方从而满足题目的优先级要求。9. 推断代号的输出格式如果在历史记录中找到对应散列值则在代号前添加##ABCD200_3如果找不到则输出###对应函数为string inferName( ull hashValue, const unordered_mapull, 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]消息类型下标128接收方下标2956发送方下标5771位置。对于代号字段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完成推断。因此处理顺序必须是使用旧的历史记录推断当前消息输出当前消息把当前消息中直接出现的代号加入历史。也就是string inferredName inferName(hashValue, latest12); cout ...; addDirectName(normalValue, directName, latest12, latest25);不能把addDirectName放到推断之前。四、总结这道题表面上是一道较长的模拟题实际可以分解成四个相对独立的部分二进制字段提取普通 38 进制代号解码典型代号的混合进制解码使用哈希表维护散列值最近对应的直接代号。其中最容易出错的地方有短数字表示需要先减去 (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表示补充的空格 * 110表示数字09 * 1136表示字母AZ。 */ if (c1 ! 0) { if (c1 10) { result char(0 c1 - 1); } else { result char(A c1 - 11); } } /* * 第二位 * 09表示数字09 * 1035表示字母AZ。 */ 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_mapull, string latest12, unordered_mapull, string latest25 ) { ull hash12 getHash(normalValue, 12); ull hash25 getHash(normalValue, 25); latest12[hash12] name; latest25[hash25] name; } /* * 根据散列值从历史记录中推断代号。 */ string inferName( ull hashValue, const unordered_mapull, 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_mapull, string latest12; unordered_mapull, 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^2525位散列值。 */ 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; }转载请注明出处
一、整体题意题目给出 (n) 条长度固定为 72 位的二进制消息要求按照消息的编码规则将每条消息转换成对应的文字形式。每条消息包含接收方代号发送方代号可选的发送方位置编号。根据第一个二进制位消息分为两种第一个二进制位是0简单消息第一个二进制位是1复杂消息。困难之处在于消息中不一定直接保存完整代号也可能只保存代号的散列值。此时需要根据之前消息中直接出现过的代号进行推断。二、两种消息的结构1. 简单消息简单消息的 72 位结构如下位数含义第 1 位固定为0接下来 28 位接收方代号接下来 28 位发送方代号最后 15 位发送方位置其中28 位代号字段有两种情况如果数值小于 (2^{25})表示代号的 25 位散列值如果数值不小于 (2^{25})表示典型代号的短数字表示加上 (2^{25})。位置编号等于 0消息不包含位置不等于 0直接输出对应位置编号。2. 复杂消息复杂消息的 72 位结构如下位数含义第 1 位固定为1接下来 58 位一方代号的完整数字表示接下来 12 位另一方代号的 12 位散列值最后 1 位双方关系最后一位表示完整代号属于哪一方0完整代号是发送方散列值代号是接收方1完整代号是接收方散列值代号是发送方。三、输出规则每条消息输出格式为接收方代号 发送方代号 位置如果消息中没有位置则只输出接收方代号 发送方代号代号有三种输出方式代号由完整数字表示或者短数字表示直接解析得到ABCD200_3代号通过散列值推断得到需要添加##ABCD200_3散列值无法推断###四、思路解析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 × 2111对应二进制1011。由于完整代号只占 58 位使用unsigned long long就能保存。2. 完整数字表示还原代号一个代号会补充到 11 位然后看作一个 11 位的 38 进制数。字符与数字的对应关系为数字字符0空格110091136AZ37_因此可以不断对数字表示除以 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五位代号会在开头补一个空格变成六位代号。六个位置对应的取值数量分别为位置可能字符数量第 1 位空格、数字、大写字母37第 2 位数字、大写字母36第 3 位数字10第 4 位大写字母26第 5 位大写字母26第 6 位大写字母26因此这是一个混合进制数。从最后一位开始依次对 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补充的空格不输出110数字091136字母AZ。第二位不允许为空格因此对应方式与第一位略有不同09数字091035字母AZ。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。每加入一个新字符都执行valuevalue×38x这就是标准的进制转换过程。72 位短消息解码——混合进制、散列计算与历史信息维护一、整体题意题目给出 (n) 条按照接收顺序排列的消息每条消息都是一个长度为 72 的二进制字符串。我们需要将每条二进制消息转换成如下文字形式接收方代号 发送方代号 发送方位置如果消息中没有位置则只输出接收方代号 发送方代号72 位消息分为两种第一位为0简单消息第一位为1复杂消息。题目的主要难点有四个将代号的普通数字表示还原成字符串将典型代号的短数字表示还原成字符串按照题目公式正确计算 12 位和 25 位散列值根据此前消息中直接出现过的代号推断散列值对应的代号。二、两种消息的结构1. 简单消息简单消息共 72 位结构如下位数含义1 位固定为028 位接收方代号28 位发送方代号15 位发送方位置28 位的代号字段有两种可能。如果字段值小于 (2^{25})它表示代号的 25 位散列值。如果字段值不小于 (2^{25})它表示典型代号的短数字表示2²⁵因此真正的短数字表示为字段值-2²⁵最后 15 位是位置编号为 0消息中不包含位置不为 0输出对应的位置编号。2. 复杂消息复杂消息的结构如下位数含义1 位固定为158 位一方代号的完整数字表示12 位另一方代号的 12 位散列值1 位双方关系最后一位表示完整代号属于哪一方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 个二进制位。每读取一个二进制位相当于valuevalue×2当前位这里使用using ull unsigned long long;因为完整代号的数字表示最多占 58 位可以存入 64 位无符号整数。2. 还原普通代号一个普通代号最多有 11 个字符不足 11 位时在结尾补空格。每个字符对应一个 (0\sim37) 的数字数字字符0空格110091136AZ37_代号的数字表示为因此它本质上是一个 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 位。六个位置的取值数量分别为位置可能字符数量第 1 位空格、数字、大写字母37第 2 位数字、大写字母36第 3 位数字10第 4 位大写字母26第 5 位大写字母26第 6 位大写字母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; 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表示补充的空格110表示数字091136表示字母AZ。如果c1 0说明原代号长度为 5因此不输出第一位。第二位的编码规则是09表示数字091035表示字母AZ。所以第二位不能和第一位使用完全相同的转换方法。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 位。两者相乘最多可能需要约583694位。unsigned long long只有 64 位乘法会发生溢出。因此必须使用 GCC 提供的 128 位无符号整数using u128 unsigned __int128;6. 如何根据散列值推断代号如果消息中的某一方使用散列值表示就需要在之前直接出现过的代号中寻找匹配项。能够用于推断的代号只有两类简单消息中由短数字表示直接解码出的典型代号复杂消息中由完整数字表示直接解码出的代号。通过散列值间接推断出来的代号不能再次用于后续推断。例如#ABCD200_3虽然成功推断出了ABCD200_3但它不能被加入历史记录。7. 如何找到最近出现的匹配代号一种直接思路是每次遇到散列值都从前往后扫描所有历史消息。但是如果消息数量较大这种方法的最坏时间复杂度为O(²)实际上题目只需要“最近出现”的匹配代号因此可以使用两个哈希表unordered_mapull, string latest12; unordered_mapull, string latest25;含义分别是latest12[h]最近直接出现的、12 位散列值为h的代号latest25[h]最近直接出现的、25 位散列值为h的代号。加入一个直接出现的代号时同时计算它的两种散列值void addDirectName( ull normalValue, const string name, unordered_mapull, string latest12, unordered_mapull, string latest25 ) { latest12[getHash(normalValue, 12)] name; latest25[getHash(normalValue, 25)] name; }如果同一个散列值已经存在直接覆盖旧值即可因为新代号出现得更晚。8. 处理同一条消息中双方同时匹配的情况题目规定如果最后收到的消息中的收发双方代号的散列值都符合则使用最后收到的消息中发送方的代号。因此如果一条简单消息中的双方代号都是短数字表示两者都可以加入历史记录。更新顺序必须是先更新接收方再更新发送方。if (receiverDirect) { addDirectName(...); } if (senderDirect) { addDirectName(...); }如果双方散列值相同后加入的发送方会覆盖接收方从而满足题目的优先级要求。9. 推断代号的输出格式如果在历史记录中找到对应散列值则在代号前添加##ABCD200_3如果找不到则输出###对应函数为string inferName( ull hashValue, const unordered_mapull, 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]消息类型下标128接收方下标2956发送方下标5771位置。对于代号字段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完成推断。因此处理顺序必须是使用旧的历史记录推断当前消息输出当前消息把当前消息中直接出现的代号加入历史。也就是string inferredName inferName(hashValue, latest12); cout ...; addDirectName(normalValue, directName, latest12, latest25);不能把addDirectName放到推断之前。四、总结这道题表面上是一道较长的模拟题实际可以分解成四个相对独立的部分二进制字段提取普通 38 进制代号解码典型代号的混合进制解码使用哈希表维护散列值最近对应的直接代号。其中最容易出错的地方有短数字表示需要先减去 (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表示补充的空格 * 110表示数字09 * 1136表示字母AZ。 */ if (c1 ! 0) { if (c1 10) { result char(0 c1 - 1); } else { result char(A c1 - 11); } } /* * 第二位 * 09表示数字09 * 1035表示字母AZ。 */ 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_mapull, string latest12, unordered_mapull, string latest25 ) { ull hash12 getHash(normalValue, 12); ull hash25 getHash(normalValue, 25); latest12[hash12] name; latest25[hash25] name; } /* * 根据散列值从历史记录中推断代号。 */ string inferName( ull hashValue, const unordered_mapull, 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_mapull, string latest12; unordered_mapull, 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^2525位散列值。 */ 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; }转载请注明出处
