124 lines
4.1 KiB
Markdown
124 lines
4.1 KiB
Markdown
Q1
|
||
```
|
||
有n颗珍珠，编号为1至n，爸爸和小明做游戏，让小明把这些珍珠串成若干串项链。初始时n颗珍珠摆放在桌子上，每颗珍珠自成一个项链（即相当于有n个项链，每个项链只含一颗珍珠）。
|
||
|
||
每次爸爸让小明做如下操作“a b”，表示将珍珠a所在的项链串在珍珠b所在的项链后面，形成一串新的项链，即a所在项链的第一个珍珠排在b所在项链的最后一个珍珠后面，如果珍珠a和b已在同一项链里，则忽略该操作。
|
||
|
||
请编写程序，输出小明完成爸爸的所有操作后，每个珍珠所在的项链的链头（该项链第一颗珍珠的编号）。
|
||
|
||
输入格式:
|
||
每个测试点包含多组测试数据，第一行1个整数 T ，表示测试数据组数。对于每组数据，第一行两个整数 n 和 m，分别表示珍珠个数和操作次数。接下来 m 行，每行两个整数a和b，表示爸爸让小明执行的一个操作。T≤5，1≤n, m≤30000，1≤a, b≤n。
|
||
|
||
输出格式:
|
||
输出为T 行，每行为 n个整数a
|
||
1
|
||
|
||
a
|
||
2
|
||
|
||
…a
|
||
n
|
||
|
||
，每个整数后一个空格，a
|
||
i
|
||
|
||
(1≤i≤n)表示珍珠i所在项链的链头珍珠编号。
|
||
|
||
输入样例:
|
||
2
|
||
4 2
|
||
2 1
|
||
4 3
|
||
5 4
|
||
1 2
|
||
2 3
|
||
4 5
|
||
1 3
|
||
|
||
|
||
输出样例:
|
||
1 1 3 3
|
||
3 3 3 5 5
|
||
|
||
数据规模:
|
||
测试点0：1 ≤n, m ≤ 10；
|
||
测试点1：10 < n, m ≤100；
|
||
测试点2：100 < n, m ≤ 1000；
|
||
测试点3：1000 < n, m ≤10000；
|
||
测试点4：10000 < n, m ≤ 30000。
|
||
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
100 ms
|
||
内存限制
|
||
64 MB
|
||
栈限制
|
||
8192 KB
|
||
```
|
||
|
||
Q2
|
||
```
|
||
编写程序统计一棵非空二叉树中每层度为1的结点的数目，二叉树结点个数不超过100。
|
||
|
||
输入格式:
|
||
输入为一个字符串，表示带空指针信息的二叉树先根序列。其中空指针信息用#表示，二叉树结点为a-z, A-Z的字母。
|
||
|
||
输出格式:
|
||
输出为若干行，按层数从小到大次序输出二叉树每层度为1的结点个数，即第1行输出第0层度为1的结点个数，第2行输出第1层度为1的结点个数，以此类推。
|
||
|
||
输入样例:
|
||
ABD###CE###
|
||
输出样例:
|
||
0
|
||
2
|
||
0
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
50 ms
|
||
内存限制
|
||
64 MB
|
||
栈限制
|
||
8192 KB
|
||
```
|
||
|
||
Q3
|
||
```
|
||
编写一个哈夫曼编码译码程序。针对一段文本，根据文本中字符出现频率构造哈夫曼树，给出每个字符的哈夫曼编码，并进行译码，计算编码前后文本大小。
|
||
为确保构建的哈夫曼树唯一，本题做如下限定：
|
||
|
||
选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。
|
||
若多棵二叉树根结点权值相等，则先生成的作为左子树，后生成的作为右子树，具体来说：i) 对于单结点二叉树，优先选择根结点对应字母在文本中最先出现者，如文本为cba，三个字母均出现1次，但c在文本中最先出现，b第二出现，故则选择c作为左子树，b作为右子树。ii) 对于非单结点二叉树，先生成的二叉树作为左子树，后生成的二叉树作为右子树。iii. 若单结点和非单结点二叉树根结点权值相等，优先选择单结点二叉树。
|
||
生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。
|
||
输入格式:
|
||
输入为3行。第1行为一个字符串，包含不超过5000个字符，至少包含两个不同的字符，每个字符为a-z的小写字母。第2、3行为两个由0、1组成的字符串，表示待译码的哈夫曼编码。
|
||
|
||
输出格式:
|
||
输出第一行为用空格间隔的2个整数，分别为压缩前后文本大小，以字节为单位，一个字符占1字节，8个二进制位占1字节，若压缩后文本不足8位，则按1字节算。输出从第二行开始，每行为1个字符的哈夫曼编码，按各字符在文本中出现次数递增顺序输出，若多个字符出现次数相同，则按其在文本出现先后排列。每行格式为“字母:编码”。最后两行为两行字符串，表示译码结果，若译码失败，则输出INVALID。
|
||
|
||
输入样例:
|
||
cbaxyyzz
|
||
0100
|
||
011
|
||
|
||
输出样例:
|
||
8 3
|
||
c:100
|
||
b:101
|
||
a:110
|
||
x:111
|
||
y:00
|
||
z:01
|
||
zy
|
||
INVALID
|
||
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
50 ms
|
||
内存限制
|
||
64 MB
|
||
栈限制
|
||
8192 KB
|
||
``` |