题解 | #"注意标点符号"#

I."注意标点符号"

Arcturus1350:很抱歉，彩蛋是在这道题

标准做法：

首先这道题是一道正经的算法题，题目中说了你要输出的是一颗huffman树的WPL，并且题目中加粗字体也已经告诉你了字符集是大小写不敏感的26个英文字母，现在就是要找到每个字符所对应的频数(为什么是频数而不是频率参考题目中“the frequency of occurrence”)。

再看题目名称"注意标点符号"，经过粗略的观察我们发现题目描述是被一对引号引起来的文段，而题目中也说了一对神秘字符给出了每个字符的出点频数，

因此我们只需要将题面描述中的26个英文字母出现的次数做统计(大小写不敏感)，用这个来构建huffman树，求出WPL即可。

而WPL可以不构建huffman树，直接用优先队列来求。最后求出来的答案是3551.

//统计字符数
#include<bits/stdc++.h>
using namespace std;
char qwq;
struct data{
	char qwq;
	int num;
	friend bool operator <(const data &a,const data &b) {
//		return a.num==b.num?a.qwq<b.qwq:a.num<b.num;
		return a.qwq<b.qwq;
	}
}a[1001];
int main() {
	freopen("1.txt","r",stdin);//题目描述中的所有的文本
//	freopen("2.txt","w",stdout);
	while(scanf("%c",&qwq)!=EOF) {
		if(qwq>='a'&&qwq<='z') a[qwq-'a'].num++;
		if(qwq>='A'&&qwq<='Z') a[qwq-'A'].num++;
	}
	for(int i=0;i<26;i++) a[i].qwq=i+'a';
	sort(a,a+26);
//	for(int i=0;i<26;i++) printf("%c %d\n",a[i].qwq,a[i].num);
	for(int i=0;i<26;i++) printf("%d\n",a[i].num);
	return 0;
}

a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

63 | 7 | 55 | 30 | 95 | 36 | 15 | 42 | 46 | 1 | 5 | 20 | 29 | 64 | 62 | 23 | 4 | 53 | 54 | 66 | 32 | 6 | 11 | 3 | 13 | 2

然后直接跑优先队列我就不放代码了。

彩蛋做法：

这道题让输出一个WPL，但是奇怪的是这道题有spj,并且在输出格式中还有行意义不明的文字。其实这个文字是Hymmnos语，翻译过来就是or some lowercast English letters。那么到底是什么呢？

观察到样例输入是一个意义不明的整数，而输出在说明中给出了是通过AES加密的结果，不难猜出key 就是题目描述中Maplef_Snow给出的字符串:skvqpzcgxjkszcrq，可是第二遍AES加密中的密钥是pass，反正我是不会解了。并且在样例说明中已经提示了，"但真正需要解码的是样例输出吗？"很显然，不是。

然后备注中说了我最近写了篇blog，所以在nowcoder和cnblogs中都可以找到这篇文章https://blog.nowcoder.net/n/4ad83b19ac4d4e2eac524e634ee77d66 或者 https://www.cnblogs.com/arcturus/p/17272163.html

众所周知，于对于一组字符集和频数对应的huffman编码会有好多种，我这里给出了一个我自己习惯的写法。看到这段代码应该就能猜到彩蛋是可以用huffman编码解码的吧。

那怎么找到编码后的01串呢？应该对样例输入下手了，因为全文只剩样例输入没有用到了。其实需要将样例输入的整数转化为2进制表示，得到一个01串:1110110010011100011010000001101100110011111101100011011010

再根据我给出的代码(在开始比赛50分钟之后为了减少难度我公布了主函数除了输入的其他所有代码，1h20min之后公布了所有代码)，补全代码之后跑这个代码，输入用到的26个英文字母频数就是在正常做法中求出来的频数。最后能跑出每个字符的编码:

WPL=3551
f 0000
b 000100
q 0001010
k 0001011
l 00011
h 0010
w 001100
x 00110100
j 001101010
z 001101011
v 0011011
p 00111
e 010
i 0110
r 0111
d 10000
u 10001
a 1001
n 1010
t 1011
s 1100
c 1101
y 111000
g 111001
m 11101
o 1111

利用这个编码去解码1110110010011100011010000001101100110011111101100011011010，得到的最终结果就是:

maplefissocute

把这个字符串输出可以成功的触发彩蛋并且通过此题

ps:因此这道题输出3551和maplefissocute都可以通过，这就是spj存在的意义之一