题目

题目链接：TUOJhttps://sim.csp.thusaac.com/contest/38/problem/2参考：CCF-CSP第38次认证第三题——消息解码（满分题解）_csp消息解码-CSDN博客https://blog.csdn.net/2501_92845263/article/details/150998468#comments_38557269

 大佬的代码很优雅，经过测试也是满分。但是简单消息的s1和s2那里，现在的代码感觉还是有可能出现第二个代号的散列值来自第一个代号的情况。所以我觉得应该在s1和s2都解析完之后再存表。其他的逻辑大差不差

思路

拿到大模拟的题目，需要把握好输入和输出，然后结合给出的样例理解题意，理清思路

一、核心思路

处理两种类型的消息，将二进制串转换为人类可读的代号格式，并维护哈希表来建立散列值与原始代号之间的映射关系。

二、两种消息类型处理

1. 类型0消息（72位：1标志位 + 28位×2 + 15位位置信息）

• 标志位：'0'

• 接收方代号：28位 → solve28() 处理

• 发送方代号：28位 → solve28() 处理

• 位置信息：15位 → 十进制整数

2. 类型1消息（72位：1标志位 + 58位 + 12位 + 1位顺序标志）

• 标志位：'1'

• 代号本体：58位 → solve58() 处理（直接转38进制）

• 散列值：12位 → solve12() 处理（查哈希表）

• 顺序标志：第72位决定输出顺序

三、关键技术点

1. 28位代号处理（solve28()）

• 如果值 ≥ 2^25：使用短数字表示（3字母+数字组合）

• 如果值 < 2^25：查询25位哈希表获取真实代号

2. 哈希机制

• 使用乘数 47055833459ULL 和右移操作计算散列值

• 维护两个哈希表：mp12（12位哈希）和 mp25（25位哈希）

• save_sanlie() 将真实代号存入两个哈希表

3. 进制转换

• 二进制 ↔ 十进制：change() 函数

• 十进制 ↔ 38进制：_10to38() 和 _38to10()（支持数字、字母、下划线）

• 短数字表示：decode_short() 生成3-5位紧凑格式

四、数据处理流程

1. 读取二进制消息串

2. 根据首位判断消息类型

3. 解析各部分内容

4. 更新哈希表（记录见过的真实代号）

5. 输出格式化结果

五、特殊标记

• "###"：表示哈希表中找不到对应项

• "#" 开头：表示从哈希表查找到的结果

• 无 "#"：表示直接生成的代号

代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n' 
#define int long long

int n; 
int mi25=1ULL<<25; //2^25
unordered_map<int,string>mp12,mp25; //12位散列值，25位散列值 

/* [可选]快速幂：base^m，用来算 38^k */
int fastpow(int base,int n){
    int res = 1;
    while(n){
    	if(n&1) res=res*base;
    	base=base*base;
    	n>>=1; //warn: >>= not >>
	}
    return res;
}

//2进制字符串-> 10进制整数
int change(string s){
	int res=0,base=1;
	for(int i=s.size()-1;i>=0;i--){ //WARN:死循环：如果define int为ULL；无符号数永远大于等于 0：条件 i >= 0 永远成立。
		if(s[i]=='1') res+=base;
		base=base<<1; //*2
	}
	return res;
} 
/* 短数字表示->典型代号, 1/2 位数字或大写字母、1 位数字和 3 位字母组成, 倒序再reverse */
string decode_short(int num){
	string res;
	int op=0; //操作数
	//3 位字母
	for(int i=0;i<3;i++){
		op=num%26;
		res+=char('A'+op);
		num/=26;
	}
	//1位数字
	op=num%10;
	res+=char('0'+op);
	num/=10; 
	//第2位 数字/大写字母
	op=num%36;
	if(op<=9) res+=char('0'+op);
	else res+=char('A'+op-10); 
	num/=36;
	//第1位 数字/大写字母
	if(num!=0){
		op=num;
		if(op<=10) res+=char('0'+op-1);
		else res+=char('A'+op-11); 	
	}
	reverse(res.begin(),res.end());
	return res;
}

/* 10进制整数 -> 11 位 38 进制字符串（带 _） */
string _10to38(int num)
{
	string res;
	int op=0; 
	for(int i=0;i<11;i++){
		op=num%38;
		if(op!=0){
			if(op<=10) res+=char('0'+op-1);
			else if(op<=36) res+=char('A'+op-11);
			else res+='_';
		}
		num/=38; 
	}
	reverse(res.begin(),res.end());
	return res;
}
/* 11 位 38 进制字符串（带 _） -> 10进制整数 */
int _38to10(string s)
{
	int res=0,op=0;
	int base=6278211847988224ULL; //38^10
//	int base=fastpow(38,10); //[可选]快速幂
	for(int i=0;i<s.size();i++){
		if(isdigit(s[i])) op=s[i]-'0'+1;
		else if(isupper(s[i])) op=s[i]-'A'+11; //大写字母
		else op=37;
		res+=op*base;
		base/=38;
	}
	return res;
}

int ha(int num,int digit){ //n位散列值的计算方法
	return num*47055833459ULL>>(64-digit);//右移 (64 - base) 位后，结果最多只有 base 位有效，无需再取模
}

//查找散列值对应的38进制串 
string find_sanlie(int hash,int digit){ //数位 
	if(digit==25){
		if(mp25.count(hash)) return "#"+mp25[hash];
		else return "###";
	}else {
		if(mp12.count(hash)) return "#"+mp12[hash];
		else return "###";
	}
}

//存下散列值的对应38进制串 
void save_sanlie(string s){
	if(s[0]=='#') return; //warn:本就由散列值推断而来
	int num=_38to10(s);
	mp12[ha(num,12)]=s;
	mp25[ha(num,25)]=s;
}

string solve28(string s) {
	int num=change(s);
	if(num>=mi25) {
		num-=mi25;
		string res=decode_short(num); //短数字表示->典型代号 
		return res;
	}else{
		return find_sanlie(num,25); //查找hash表 
	}
}

string solve58(string s) {
	int num=change(s); //01串转整数 
	return _10to38(num);//10进制->38进制
}

string solve12(string s){
	int hash=change(s);
	return find_sanlie(hash,12);	
}

void solve()
{
	cin>>n;
	string s,s1,s2;
	while(n--){
		cin>>s;
		if(s[0]=='0') {
			s1=solve28(s.substr(1,28)); //接收方 
			s2=solve28(s.substr(29,28)); //发送方 
			int pos=change(s.substr(57)); //57~71 后15位，01串转整数 
			// 填hash表
			save_sanlie(s1);
			save_sanlie(s2); //如果最后收到的消息中的收发双方代号的散列值都符合，则使用最后收到的消息中发送方的代号。
			if(pos!=0) cout<<s1<<" "<<s2<<" "<<pos<<endl;
			else cout<<s1<<" "<<s2<<endl;
		}
		else {
			s1=solve58(s.substr(1,58)); //58位代号的数字表示 //warn:(1,58),not(2,58)
			s2=solve12(s.substr(59,12)); //12位散列值 
			save_sanlie(s1); 
			if(s[71]=='0') cout<<s2<<" "<<s1<<endl;
			else cout<<s1<<" "<<s2<<endl;
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0; 
}

样例

input:
7
100111111001001101000001000100101001010001000000011011110000011100011010
000000111011010010001111000110010000110101101010001111011000000001111011
100111111001001101000001000100101001010001000001001000111000011101101000
110010110001000111010011000010110001101000100110000001111000011110010101
100111111001001101000001000100101001010001000001001000111000011101101000
100111111001001101000001000100101001010001000001110110000000011101101000
100111111001001101000001000100101001010001000001110110000000011101101000

output:
### ABCD200_3
#ABCD200_3 A0BCD 123
#ABCD200_3 ABCD200_4
PY4XMCHJZTN ###
#PY4XMCHJZTN ABCD200_4
#ABCD200_4 ABCD200_5
#ABCD200_5 ABCD200_5

易错点

这里long long已经够用了，如果#define int unsigned long long，这会导致循环变量 i 的类型也是 unsigned long long（无符号 64 位整数）。

1. 无符号数永远大于等于 0：对于无符号类型的 i，条件 i >= 0 永远成立。
2. 溢出回绕：当 i 等于 0 时，执行 i-- 会导致 i 溢出变回无符号整数的最大值（2^(64−1)），而不是变成 -1。
3. 循环因此无法停止，导致死循环。