消息解码

GitHub跳转原题关系图 Canvas 关系图返回列表

按协议切分 72 位消息，用 128 位乘法计算哈希，并按历史显式代号处理碰撞与发送方优先级。

OJ: shumeng

题目 ID: CSP202506C

难度:普及+/提高-

标签:模拟位运算哈希

日期: 2026-07-31 16:21

形式化题目

每条消息是一个 72 位的二进制串，首比特决定类型：

简单消息（首比特 0）：三个字段依次为接收方 28 位、发送方 28 位、位置 15 位。每方字段若 $\ge 2^{25}$ 表示典型代号短码，否则表示 25 位散列值；位置为 0 表示无位置信息。
复杂消息（首比特 1）：一方为 58 位完整编码，另一方为 12 位散列值，最后 1 位表示谁在前（0 表示完整编码一方是发送方）。

按收到的先后顺序，用此前消息中显式出现的代号推断散列值对应的代号，输出每条消息的文字表示。

思路

解码过程分四个独立环节。

按位切分字段

用一个函数从消息串第 start 位开始连续读取 length 位，逐位左移或上当前位的 0/1 即可。

两种代号的还原

完整编码：11 位、每位基数 38，从低位到高位取模还原成字符，再去掉末尾补的空格。
典型短码：按题目给定的混合进制（ $36\times10\times26^3,\ 10\times26^3,\ 26^3,\ 26^2,\ 26,\ 1$ ）反解，得到 5/6 位短代号后再转成完整编码数字。

散列值计算

$n$ 位散列值为 number * 47055833459 >> (64-n) 的低 n 位。乘积会超过 64 位，必须用 unsigned __int128 计算。

历史表与碰撞

用两个哈希表分别保存"12/25 位散列值 $\to$ 最近一次显式出现的完整编码"。更新规则：

消息中显式给出的代号（完整编码或短码）才写入历史表；
通过散列值推断出的代号不写入历史表；
查表时取的是最近一次出现的记录，天然满足"最后收到的消息优先"；
同一消息中接收方、发送方都符合时，先记接收方再记发送方，使发送方优先。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:55
 */
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const ull HASH_MULTIPLIER = 47055833459ULL;

struct DecodedCode {
    string name;         // 还原出的代号文本，无法还原时为 "###"，推断时为 "#"+代号
    ull number;          // 该代号完整编码对应的数字
    bool explicit_code;  // 是否为消息中显式给出的完整代号
};

unordered_map<ull, ull> latest_hash_12; // 12 位散列值 -> 最近一次显式出现的完整编码
unordered_map<ull, ull> latest_hash_25; // 25 位散列值 -> 最近一次显式出现的完整编码

// 从 72 位消息串中读取第 start 位起 length 个二进制位（高位在前）
ull read_bits(const string &message, int start, int length) {
    ull value = 0;
    for (int i = start; i < start + length; i++) {
        value = (value << 1) | (ull)(message[i] - '0');
    }
    return value;
}

char full_digit_to_char(int digit) {
    if (digit == 0) return ' ';
    if (digit <= 10) return (char)('0' + digit - 1);
    if (digit <= 36) return (char)('A' + digit - 11);
    return '_';
}

int full_char_to_digit(char value) {
    if (value == ' ') return 0;
    if (value >= '0' && value <= '9') return value - '0' + 1;
    if (value >= 'A' && value <= 'Z') return value - 'A' + 11;
    return 37;
}

// 由完整编码数字还原 11 位代号（不足 11 位用空格补齐，去掉末尾空格）
string decode_full_name(ull number) {
    string result(11, ' ');
    for (int i = 10; i >= 0; i--) {
        result[i] = full_digit_to_char((int)(number % 38));
        number /= 38;
    }
    while (!result.empty() && result.back() == ' ') result.pop_back();
    return result;
}

// 把 11 位代号编码为完整数字（不足 11 位在结尾补空格）
ull encode_full_name(const string &name) {
    ull number = 0;
    for (int i = 0; i < 11; i++) {
        int digit = 0;
        if (i < (int)name.size()) digit = full_char_to_digit(name[i]);
        number = number * 38 + digit;
    }
    return number;
}

char first_short_digit_to_char(int digit) {
    if (digit == 0) return ' ';
    if (digit <= 10) return (char)('0' + digit - 1);
    return (char)('A' + digit - 11);
}

char second_short_digit_to_char(int digit) {
    if (digit < 10) return (char)('0' + digit);
    return (char)('A' + digit - 10);
}

// 按混合进制反解典型代号的短数字表示，得到 5/6 位短代号
string decode_short_name(ull number) {
    ull base26_3 = 26ULL * 26 * 26;
    int first = (int)(number / (36ULL * 10 * base26_3));
    number %= 36ULL * 10 * base26_3;
    int second = (int)(number / (10ULL * base26_3));
    number %= 10ULL * base26_3;
    int third = (int)(number / base26_3);
    number %= base26_3;
    int fourth = (int)(number / (26ULL * 26));
    number %= 26ULL * 26;
    int fifth = (int)(number / 26);
    int sixth = (int)(number % 26);

    string result;
    if (first != 0) result.push_back(first_short_digit_to_char(first));
    result.push_back(second_short_digit_to_char(second));
    result.push_back((char)('0' + third));
    result.push_back((char)('A' + fourth));
    result.push_back((char)('A' + fifth));
    result.push_back((char)('A' + sixth));
    return result;
}

// 计算 n 位散列值：number * 47055833459 右移 64-n 位后取低 n 位。
// 乘积可能超过 64 位，必须用 128 位乘法
ull calculate_hash(ull number, int bits) {
    __uint128_t product = (__uint128_t)number * HASH_MULTIPLIER;
    ull mask = (1ULL << bits) - 1;
    return (ull)((product >> (64 - bits)) & mask);
}

// 根据散列值查表找最近出现的完整编码，找不到返回 false
bool find_by_hash(ull target, int bits, ull &number) {
    unordered_map<ull, ull> *table;
    if (bits == 12) table = &latest_hash_12;
    else table = &latest_hash_25;
    unordered_map<ull, ull>::iterator it = table->find(target);
    if (it == table->end()) return false;
    number = it->second;
    return true;
}

void remember_code(ull number) {
    latest_hash_12[calculate_hash(number, 12)] = number;
    latest_hash_25[calculate_hash(number, 25)] = number;
}

DecodedCode decode_simple_code(ull value) {
    DecodedCode result;
    if (value >= (1ULL << 25)) {
        result.name = decode_short_name(value - (1ULL << 25));
        result.number = encode_full_name(result.name);
        result.explicit_code = true;
        return result;
    }

    ull number = 0;
    result.explicit_code = false;
    if (find_by_hash(value, 25, number)) {
        result.name = "#" + decode_full_name(number);
        result.number = number;
    } else {
        result.name = "###";
        result.number = 0;
    }
    return result;
}

DecodedCode decode_hash_code(ull value) {
    DecodedCode result;
    result.explicit_code = false;
    ull number = 0;
    if (find_by_hash(value, 12, number)) {
        result.name = "#" + decode_full_name(number);
        result.number = number;
    } else {
        result.name = "###";
        result.number = 0;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    latest_hash_12.reserve(200005);
    latest_hash_25.reserve(200005);

    int n;
    cin >> n;
    while (n--) {
        string message;
        cin >> message;
        string receiver;
        string sender;

        if (message[0] == '0') {
            ull receiver_value = read_bits(message, 1, 28);
            ull sender_value = read_bits(message, 29, 28);
            ull location = read_bits(message, 57, 15);
            DecodedCode decoded_receiver = decode_simple_code(receiver_value);
            DecodedCode decoded_sender = decode_simple_code(sender_value);
            receiver = decoded_receiver.name;
            sender = decoded_sender.name;

            if (decoded_receiver.explicit_code) {
                remember_code(decoded_receiver.number);
            }
            if (decoded_sender.explicit_code) {
                remember_code(decoded_sender.number);
            }

            cout << receiver << ' ' << sender;
            if (location != 0) cout << ' ' << location;
            cout << '\n';
        } else {
            ull first_number = read_bits(message, 1, 58);
            ull second_hash = read_bits(message, 59, 12);
            int relation = (int)read_bits(message, 71, 1);
            DecodedCode decoded_second = decode_hash_code(second_hash);
            string first_name = decode_full_name(first_number);

            if (relation == 0) {
                receiver = decoded_second.name;
                sender = first_name;
            } else {
                receiver = first_name;
                sender = decoded_second.name;
            }

            remember_code(first_number);
            cout << receiver << ' ' << sender << '\n';
        }
    }

    return 0;
}

复杂度

每条消息解析字段和查表都是常数次操作，总时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ （保存历史代号）。

总结

本题的难点在于字段位数、两种代号编码和碰撞规则，而不是算法。把"切位、还原代号、算哈希、查历史"分别封装成函数后，主流程就只是逐条消息按协议拼装输出。

题目来自第 38 次 CSP 认证 T3，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 2.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛上的居民经常使用一种短消息服务来互相通信。这种短消息的特点是，每条消息仅需 72 个比特，可以用来发送些简短的信息。发送的信息包含收发双方的代号和发送方的位置。每位居民都有一个代号，代号包含 1 到 11 个字符，且只能包含大写字母、数字和下划线。特别地，多数居民的代号长 5 到 6 位，并且依次由 1 到 2 位数字或大写字母、1 位数字和 3 位字母组成。符合这样特征的代号被称为典型代号。西西艾弗岛上的位置，可以用数字编号 1 至 32400 表示。

代号的数字表示

一个代号可以唯一地用一个数字表示，具体办法是：

将不足 11 位的代号从结尾处用空格补充到 11 位；
将每个字符用一个数字表示，数字的计算方法如下：

空格用 0 表示；
数字 0 至 9 用 1 到 10 表示；
大写字母 A 至 Z 用 11 到 36 表示；
下划线 _ 用 37 表示。

将第一个字符的数字乘以 $38^{10}$ ，第二个字符的数字乘以 $38^9$ ，第三个字符的数字乘以 $38^8$ ，……，第十一个字符的数字乘以 $38^0$ ，然后将这些数相加。

例如，代号 ABCD200_3 的数字表示可以计算为： $\underline{11}×38^{10}+\underline{12}×38^9+\underline{13}×38^8+\underline{14}×38^7+\underline{3}×38^6+\underline{1}×38^5+\underline{1}×38^4+\underline{37}×38^3+\underline{4}×38^2+\underline{0}×38^1+\underline{0}×38^0=71101055775146872$

典型代号的短数字表示

典型代号除了常规的数字表示，还有一种更简洁的短数字表示：

将 5 位的代号从开头处用空格补充到 6 位；
将第一个字符转换为数字：

空格用 0 表示；
数字 0 至 9 用 1 到 10 表示；
大写字母 A 至 Z 用 11 到 36 表示；

将第二个字符转换为数字：

数字 0 至 9 用 0 到 9 表示；
大写字母 A 至 Z 用 10 到 35 表示；

将第三个字符转换为数字：

数字 0 至 9 用 0 到 9 表示；

将第四、五、六个字符转换为数字：

大写字母 A 至 Z 用 0 到 25 表示；

将第一个字符的数字乘以 $36×10×26^3$ ，将第二个字符的数字乘以 $10×26^3$ ，将第三个字符的数字乘以 $26^3$ ，将第四个字符的数字乘以 $26^2$ ，将第五个字符的数字乘以 $26^1$ ，将第六个字符的数字乘以 $26^0$ ，然后将这些数相加。

例如，典型代号 A0BCD 的短数字表示可以计算为： $\underline{0}×36×10×26^3+\underline{10}×10×26^3+\underline{0}×26^3+\underline{1}×26^2+\underline{2}×26^1+\underline{3}×26^0=1758331$

代号的散列值

为了能在 72 个比特的消息中表达 11 位的代号，并容纳前述信息，居民们采用的方法是：

在第一次通信中使用代号的数字表示，此后可以使用代号的散列值作为代替，因为散列值的长度较短；
如果是典型代号，也可以直接使用其短数字表示来节省空间。

由代号的数字表示可以唯一地计算出代号的散列值，但由代号的散列值不能唯一地计算出代号的数字表示。对于接收消息的一方而言，如果收到的消息中含有代号的散列值，则可以通过此前收到的代号来推算该散列值所对应的代号。代号的 $n$ 位散列值的计算方法如下：

计算代号的数字表示；
将代号的数字表示乘以 47055833459；
将结果除以 $2^{64-n}$ ，取整数部分；
将结果对 $2^n$ 取模。

例如，代号 ABCD200_3 的 25 位散列值可以计算为：

$71101055775146872×47055833459=3345719439314381360096790248$

$3345719439314381360096790248÷2^{64-25} \mod 2^{25}=7770595$

（典型）代号 A0BCD 的 12 位散列值可以计算为：

数字表示 $\underline{11}×38^{10}+\underline{1}×38^9+\underline{12}×38^8+\underline{13}×38^7+\underline{14}×38^6=69279249490478336$

$69279249490478336×47055833459÷2^{64-12} \mod 2^{12}=909$

题目描述

消息可以被分为两种：简单消息和复杂消息。其中复杂消息包含完整的代号的数字表示；而简单消息仅包含典型代号的短数字表示或代号的散列值，同时可以包含发送方所在位置。

简单消息的第一个二进制位是 0，随后的 28 位（位序为高位在前，下同）表示接收方的代号，随后的 28 位表示发送方的代号，接下来的 15 位是发送方的位置编号。表示一方代号的数字有两种情况：如果是代号的散列值，则为代号的 25 位散列值；如果是典型代号的短数字表示，则为该值加上 $2^{25}$ 。位置编号如果为 0 表示该消息不包括位置编号，否则表示发送方的位置编号。

复杂消息的第一个二进制位是 1，随后的 58 位是一方的代号的数字表示；接下来的 12 位是另一方的代号的 12 位散列值；最后的 1 位表示二者的关系：0 表示首先的一方（即用代号的数字表示的那一方）是发送方，1 表示首先的一方是接收方。

一条消息的文字表示包含用空格分隔的三部分，分别是接收方的代号、发送方的代号和发送方的位置编号。如果消息不包括位置编号，则无第三部分。其中，如果一方的代号是用散列值推断的，则在该方的代号前加上井号（#）；如果通过散列值无法推断出该方的代号（可能因为此前的消息没有收到），则用 ### 表示。用散列值推断代号时，使用收到该消息前接收到的消息中出现过的代号推断。用于推断的代号包括出现在简单消息中的用短数字表示的典型代号，和出现在复杂消息中的用数字表示的代号；而不包括此前通过散列值间接推断出的。如果有多个代号的散列值都符合，则使用最后收到消息中出现的代号；如果最后收到的消息中的收发双方代号的散列值都符合，则使用最后收到的消息中发送方的代号。

试编写程序，将给出的消息的比特序列转换为对应的文字表示。

输入格式

从标准输入读入数据。

输入的第一行是一个整数 $n$ ，表示消息的数量。接下来的 $n$ 行中，每行包含一个由 72 个 0 或 1 组成的字符串，表示先后收到的 $n$ 条 72 比特长的消息。

输出格式

输出到标准输出。

输出 $n$ 行，表示这些消息对应的文字表示。

input1

1
2
3
4
5
6
7
87
100111111001001101000001000100101001010001000000011011110000011100011010
000000111011010010001111000110010000110101101010001111011000000001111011
100111111001001101000001000100101001010001000001001000111000011101101000
110010110001000111010011000010110001101000100110000001111000011110010101
100111111001001101000001000100101001010001000001001000111000011101101000
100111111001001101000001000100101001010001000001110110000000011101101000
100111111001001101000001000100101001010001000001110110000000011101101000

output1

1
2
3
4
5
6
7### ABCD200_3
#ABCD200_3 A0BCD 123
#ABCD200_3 ABCD200_4
PY4XMCHJZTN ###
#PY4XMCHJZTN ABCD200_4
#ABCD200_4 ABCD200_5
#ABCD200_5 ABCD200_5

样例 1 解释

前两个输入为题目描述中的例子。需要注意的是，在解析第一个输入时，收到的代号散列值尚不能推断出代号，因此用 ### 表示。

第三个输入是复杂消息。根据代号的数字表示值解析第一个代号为 ABCD200_4，第二个代号的 12 位散列值为 001110110100，即 948。此时向前搜索发现曾经出现的 ABCD200_3 的 12 位散列值也是 948，因此可以推断出第二个代号为 ABCD200_3，并加 # 表示这个代号是推断而来的。输入的最后一位是 0，表示第一个代号是发送方，第二个代号是接收方，因此要将 #ABCD200_3 放在前面。

第四个输入也是复杂消息，解析得第一个代号为 PY4XMCHJZTN、第二个代号的 12 位散列值为 970。此时在前面出现过的代号中找不到 12 位散列值为 970 的代号，因此无法推断出第二个代号，用 ### 表示。输入的最后一位是 1，表示第一个代号是接收方，第二个代号是发送方，因此要将 PY4XMCHJZTN 放在前面。

第五个输入也是复杂消息，解析得第一个代号为 ABCD200_4、第二个代号的 12 位散列值为 948。需要注意的是，曾经出现的代号 ABCD200_3、ABCD200_4、PY4XMCHJZTN 的 12 位散列值都是 948，我们选取最近在第四个输入中收到的 PY4XMCHJZTN 作为推断的代号，因此得到本条消息的结果。注意虽然第五个输入和第三个输入完全相同，但是由于代号的 12 位散列值发生了碰撞，因此推断出的代号可能不同。

第六个输入也是复杂消息，解析得第一个代号为 ABCD200_5、第二个代号的 12 位散列值为 948。这时，选取第五个输入中收到的 ABCD200_4 作为推断的代号，因为它是最近收到的 12 位散列值是 948 的代号。需要注意的是，虽然本条消息中出现的代号 ABCD200_5 的 12 位散列值也是 948，但是在根据散列值推断代号时，仅考虑此前收到的消息中出现的代号，而不考虑本条消息中出现的代号。

第七个输入和第六个输入相同，此次选取的是第六个输入中收到的 ABCD200_5 作为推断的代号。

子任务

对于所有的数据，保证输入的消息数据一定是按上述编码规则得到的，但可能存在由散列值无法推断出代号的情况。

测试点编号	$n\le$	特殊性质
$1\sim 3$	$100$	仅含有复杂消息，且散列值与所有出现的代号均不匹配
$4\sim 6$	$100$	仅含有简单消息，且表示双方代号的数字均不小于 $2^{25}$
$7\sim 8$	$100$	无
$9\sim 10$	$10^5$	无