# hit-cs32132-assignments-2021-wiki **Repository Path**: vonbrank/hit-cs32132-assignments-2021-wiki ## Basic Information - **Project Name**: hit-cs32132-assignments-2021-wiki - **Description**: No description available - **Primary Language**: C++ - **License**: CC-BY-SA-4.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 3 - **Forks**: 0 - **Created**: 2021-10-05 - **Last Updated**: 2024-07-29 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # CS32132 Data Structures and Algorithms - Autumn 2021 这个文档列出了**哈尔滨工业大学**计算学部2021年秋数据结构与算法课程历次**作业**的要求，以及根据个人理解所构造的输入输出格式**样例**。本项目同时包含了这些数据的生成器，**仅供参考**。 项目持续更新中，如有缺漏、建议，欢迎私信、 PR 、提 issue ！ Github [项目源址](https://github.com/vonbrank/hit-cs32132-assignments-2021) `private` ## 索引 ### 普通作业 + 绪论 + [字符串排序](#字符串排序) + [求最大元素位置](#最大元素位置) + [比赛图](#比赛图) + 线性表 + [链表块转置](#链表块转置) + [求链表对称差](#链表对称差) + [共享栈](共享栈) + [链表字符串](链表字符串) + [广义表](#广义表) + 树和二叉树 + [完全二叉树](#完全二叉树) + [最近公共祖先](#最近公共祖先) + [二叉堆](#二叉堆) + [多路平衡归并排序（胜者树与败者树）](#多路平衡归并排序胜者树与败者树) + [森林的后序遍历](#森林的后序遍历) + 图及算法 + [农夫过河](#农夫过河) + 查找 + [二分查找](#二分查找) + [二叉搜索树](#二叉搜索树) ### 大作业 + [【线性表】家电仓库](#大作业家电仓库) ### 实验 + [实验一【线性表】](#实验一) + [分时系统模拟](#分时系统模拟) + [模拟飞机起降系统的设计](#模拟飞机起降系统的设计) + [多项式乘除法](#多项式乘除法) + [算术表达式求值](#算术表达式求值) + [食堂售饭问题](#食堂售饭问题) + [实验二](#实验二) + [遍历二叉树](#遍历二叉树) + [哈夫曼树](#哈夫曼树) + [实验三](#实验三) + [图的遍历](#图的遍历) + [工程安排](#工程安排) ### 加分作业 + [【加分作业】字符串匹配算法报告](#加分作业字符串匹配算法报告) ## 详细内容 ### 绪论 #### 字符串排序 定义字符集是大写字符和数字的集合，设其**顺序**为： `A`，`B`，`C`，... ，`Z`，`0`，`1`，`2`，... ，`9` ，现给出若干字符串，给出其字典序排列。 定义字典序： + 对于 `a` 和 `b` 两个字符串，若前 `i-1` 位相同，第 `i` 位不同，则第 `i` 位按**顺序**靠前者字典序更小。 + 若 `a` 是 `b` 的前缀，且长度比 `b` 小，则 `a` 的字典序比 `b` 小。 + **输入格式** 第一行两个整数 `n` 和 `len` 。 接下来 `n` 行，每行一个长度不超过 `len` 的字符串，包含 `[A-Z0-9]` ，即大写字母和数字 。 + **输出格式** `n` 行排好序的字符串。 + **样例输入** ```bash 8 5 PAB 5C PABC CXY CRSI 7 B899 B9 ``` + **样例输出** ```bash B899 B9 CRSI CXY PAB PABC 5C 7 ``` #### 最大元素位置 有一个包括 `100` 个元素的数组，每个元素的值都是 **实数**，写出一种算法求其最大元素的位置。 + **输入格式** 一行， `100` 个实数，以空格分隔，下标范围 `1-100`。 + **输出格式** 一个整数，表示最大元素的位置 + **样例输入** ```bash 3.14 2.718 1428.57 114.514 1926.0817 1.00 2.00 3.00 4.00 5.00 6.00 7.00 8.00 9.00 10.00 11.00 12.00 13.00 14.00 15.00 16.00 17.00 18.00 19.00 20.00 21.00 22.00 23.00 24.00 25.00 26.00 27.00 28.00 29.00 30.00 31.00 32.00 33.00 34.00 35.00 36.00 37.00 38.00 39.00 40.00 41.00 42.00 43.00 44.00 45.00 46.00 47.00 48.00 49.00 50.00 51.00 52.00 53.00 54.00 55.00 56.00 57.00 58.00 59.00 60.00 61.00 62.00 63.00 64.00 65.00 66.00 67.00 68.00 69.00 70.00 71.00 72.00 73.00 74.00 75.00 76.00 77.00 78.00 79.00 80.00 81.00 82.00 83.00 84.00 85.00 86.00 87.00 88.00 89.00 90.00 91.00 92.00 93.00 94.00 95.00 ``` + **样例输出** ```bash 5 ``` #### 比赛图 在有 `n` 个选手 `P1` , `P2` , `P3` , … , `Pn` 参加的单循环赛中，每对 选手之间非胜即负。现要求求出一个选手序列： `P1'` , `P2'` , `P3'`, … , `Pn'` , 其满足 `Pi'` 胜 `Pi+1'` （ `i = 1, … , n-1` ）。 提示：本题即给出一个**比赛图**（完全有向图），求其任一**哈密顿路**。 + **输入格式** 第一行一个整数 `n` ，表示队伍数目 接下来 `n*(n-1)/2` 行，每行两个数 `a_i`, `b_i` ，表示 `a_i` 队打败了 `b_i` 队 + **输出格式** 一个序列 `p_1`, `p_2`, ... `p_n` ，满足 `p_i` 胜过 `p_{i+1}` + **样例输入** ```bash 4 1 2 1 3 4 1 3 2 4 2 3 4 ``` + **样例输出** ```bash 1 3 4 2 ``` ### 线性表 #### 链表块转置 给出长度为 `n` 的链表，给出一个整数 `k` ， 将链表每个长度为 `k` 的连续区间进行翻转，末尾不足 `k` 个元素的区间不翻转。 **注**：作为练习，你需要使用**单向链表**。 + **输入格式** 第一行两个整数 `n` ， `k` ，意义如题。 第二行 `n` 个整数，依次表示链表每个节点的值。 + **输出格式** 依次输出翻转后链表的节点值。 + **样例输入** ```bash 10 3 1 2 3 4 5 6 7 8 9 10 ``` + **样例输出** ```bash 3 2 1 6 5 4 9 8 7 10 ``` #### 链表对称差 给出两个链表 `A` ，`B` ，求其元素对称差，即生成一个新链表，里面每个元素恰好只属于 `A`，`B` 其中一者。 **注**：作为练习，你需要使用**链表**进行存储。 + **输入格式** 第一行两个整数 `n`，`m`，表示 `A`，`B 两个链表的长度。 第二行 `n` 个整数，依次表示链表 `A` 的每个节点元素值。 第三行 `m` 个整数，依次表示链表 `B` 的每个节点元素值。 + **输出格式** 一行，若干整数，依次表示 `A` 与 `B` 的对称差所生成链表中的元素值。 + **样例输入** ```bash 20 20 47 24 20 41 34 44 7 7 30 26 25 8 28 35 28 1 15 25 6 37 38 35 1 10 4 29 38 26 12 40 20 7 48 8 19 36 38 11 1 27 ``` + **样例输出** ```bash 47 24 41 34 44 30 25 28 15 6 37 38 10 4 29 12 40 48 19 36 11 27 ``` #### 【大作业】家电仓库 你需要编写一个程序，用来维护商场家电的库存。具体来说： 1. 每种家电的信息都需要存储在**链表**节点里； 2. 当出现进货、出货等操作时，意味着维护链表的**增、删、改、查**操作； 3. 每日营业结束时链表信息需存入**文件**，次日开始营业时从文件里读取数据，程序继续运行。 更详细的要求如下： + 每个链表的节点字段包括：家电名称、品牌、单价和数量； + 这是一个有序链表，以商品单价作为排序依据； + 一种商品的进货与出货意味着商品的数量字段增加或减少； + 支持通过商品名称查询该商品的品牌、单价和数量信息； + 链表数据文件的结构需要通过精心设计，以期实现每日开始营业时链表结构与前一日结束营业前等价。 为了规范地模拟上述需求，可选择模拟命令行操作，此处提供的输入样例仅模拟程序运行时增、删、改、查的命令，以及前一日的营业数据文件，输入 `exit` 表示营业结束，程序将保存文件后退出；输出样例则提供了一种可能的命令行UI设计，仅供参考。 **注**：作为练习，你需要使用**链表**进行存储。 + **输入格式** + 对于输入文件： 第一行一个整数 `n` ，表示商品数目。 接下来每行有 ` ` 总共 `4` 个数据，分别表示商品的名称、品牌、数量、单价，`name`、`brand`为字符串，`price` 为正实数，`amount` 为非负整数。 + 对于输入命令： 若干行，当出现 `admin@system ~`时可以输入，以 `exit` 结束。 每行为以下几种命令中的一种： + `put ` ：表示名为 `name` 的商品增加 `amount` 个库存，如果 `name` 商品不存在，则为这种商品新建一个节点，并提示其输入商品的品牌、单价信息，格式为 ` `。 + `get ` ：表示名为 `name` 的商品减少 `amount` 个库存，若商品不存在或库存不足，则报错，错误信息示例见样例。 + `query ` ：表示需要调出名为 `name` 的商品的所有信息，若商品不存在则报错。 + `query --all` ：表示需要调出所有商品信息。 `name`，`brand` 等字段均为不带空格、缩进、换行、回车等字符的字符串。 + **输出格式** 对于每条命令： + 若操作成功，则给出形如 `操作成功` 的回应，或干错不回应，毕竟在Linux中 `没有回应就是最好的回应`； + 若失败则输出错误信息，形如 `库存不足`； + 查询指令将输出商品信息，格式形如： ```bash name: Cleaner-V8-Fluffy-Extra brand: Dyson price: 2399.00 amount: 996 ``` + 程序启动时表示开始营业，可输出 `文件加载成功` 等信息。 + 输入 `exit` 表示营业结束，文件写入完成后可出输出 `文件已保存` 等信息。 + 对于无效命令应报错。 + **样例输入** + 前一日营业的数据文件： ```txt 3 Cleaner-V8-Fluffy-Extra Dyson 2399.00 996 Fridge-BCD-481WGHTDD9D9U1 Haier 4399.00 758 Television-XR-55X91J Sony 5499.00 576 ``` + 输入命令： ```bash query --all put Television-XR-55X91J 100 get Fridge-BCD-481WGHTDD9D9U1 50 get Television-XR-55X91J 30 get Television-XR-55X91J 2000 put Cooker-Hood-JCD7+HT8BE.S 200 Fotile 3899.00 got Television-XR-55X91J 2000 get Television-XR-55X91J 2000 get Table-Lamp-1S 50 exit ``` + **样例输出** + 控制台输出记录： ```bash 程序启动... 正在读取数据... 数据读取完成！ 开始营业。 root@system ~ query --all 库存列表： name: Cleaner-V8-Fluffy-Extra brand: Dyson price: 2399.00 amount: 996 name: Television-XR-55X91J brand: Sony price: 5499.00 amount: 576 name: Fridge-BCD-481WGHTDD9D9U1 brand: Haier price: 4399.00 amount: 758 admin@system ~ put Television-XR-55X91J 100 【库存更新】Television-XR-55X91J 的库存修改为 676 admin@system ~ get Fridge-BCD-481WGHTDD9D9U1 50 【库存更新】Fridge-BCD-481WGHTDD9D9U1 的库存修改为 708 admin@system ~ get Television-XR-55X91J 30 【库存更新】Television-XR-55X91J 的库存修改为 646 admin@system ~ got Television-XR-55X91J 2000 【错误】未知命令：got admin@system ~ get Television-XR-55X91J 2000 【错误】库存不足！ admin@system ~ put Cooker-Hood-JCD7+HT8BE.S 200 【添加商品】请输入 Cooker-Hood-JCD7+HT8BE.S 的品牌名称和单价： Fotile 3899.00 商品添加完成！ admin@system ~ get Table-Lamp-1S 50 【错误】商品 Table-Lamp-1S 不存在！ admin@system ~ exit 正在保存数据... 数据保存完成！ 结束营业。 ``` + 保存的库存数据： ```txt 4 Cleaner-V8-Fluffy-Extra Dyson 2399.00 996 Cooker-Hood-JCD7+HT8BE.S Fotile 3899.00 200 Fridge-BCD-481WGHTDD9D9U1 Haier 4399.00 758 Television-XR-55X91J Sony 5499.00 576 ``` #### 共享栈 实现一种数据结构，要求能同时维护多个栈，包括 `push`，`pop`操作，所有栈共用同一片存储池。 作为练习，请使用**静态链表**实现。 + **输入格式** 第一行三个数，`n`, `m`, `k`，表示共享栈的个数，存储池大小，以及指令条数。 接下来 `k` 每行一条命令，有三种命令： `1 x y` 表示向 `x` 号栈压入元素 `y` ，的范围为 `[0, n - 1]` `2 x` 表示输出 `x` 号栈的栈顶元素。 `3 x` 表示弹出 `x` 号栈的栈顶元素，空栈不做任何操作。 + **输出格式** 对于每个 `2` 操作，输出结果，空栈栈顶返回0。 全部操作结束后输出 `n` 行，表示 `[0, n - 1]` 号栈每个栈从栈顶到栈底的所有元素。 + **样例输入** ```bash 8 39 39 3 5 3 0 3 0 1 7 105 1 2 40 2 2 3 5 3 5 1 2 98 1 1 91 1 3 47 1 6 106 3 0 3 6 2 1 2 5 1 4 113 3 3 2 0 1 5 20 1 3 120 2 1 1 0 114 1 6 42 1 7 54 2 3 2 5 1 7 5 1 3 101 1 2 100 2 6 1 4 7 1 5 122 1 0 48 2 6 1 2 77 1 5 122 1 7 121 1 0 112 ``` + **样例输出** ```bash 40 91 0 0 91 120 20 42 42 112 48 114 91 77 100 98 40 101 120 7 113 122 122 20 42 121 5 54 105 ``` #### 链表字符串 用链表实现字符串的存储、查找和切片。具体来说你可以实现如下接口： ```cpp class String { public: //若s为对象本身的子串，则返回子串的起始下标；否则返回-1。 virtual int getIndex(const String &s); //返回处于区间 [a, b] 内的子串 virtual String subString(int a, int b); }; ``` + **输入格式** 第一行一个字符串 `s` ，表示要操作的字符串 第二行一个整数，表示操作个数 接下来 `n` 行，每行有以下操作的一种： `1 t` 如果 `t` 是 `s` 的子串，则输出开始位置在 `s` 中的索引，若 `s` 的长度为 `length`，则索引范围为 `[0, length - 1]`；否则输出 `-1` `2 a b` 输出 `s` 中处于 `[a, b]` 区间的子串，越界部分不输出 + **输出格式** `n` 行，对于每种操作，输出其结果。 + **样例输入** ```bash YmBYpuUnvhaNrNluLeJzqxvwHrQJyBliGPSCCUTcFqSXlmdBAN 26 2 3 31 1 iGPSCCU 2 3 4 2 29 45 1 vhaNrNluLeJzqxvwHrQJyBliGPSCCUTcFqSXlmdBAN 1 liGPSCCUTcFqSXlm 1 qSXlmdB 2 5 44 1 GPSCC 1 nvhaNrNluLeJzqxvwHrQJyBliGPSCCUTcFqSXlmdBANabc 1 uUnvhaNrNluLeJzqxvwHrQJyBliGP 2 2 8 1 BYpuUnvhaNrNluLeJzqxvwHrQJyBliGPSC 1 haNrNluLeJzqxv 1 TcFqSXlm 1 vhaNrNluLeJzqx 2 31 32 2 20 23 2 45 47 1 rQJyBliGPS 2 12 46 1 liGPSCCUTcFq 1 UnvhaNrNluLe 2 34 34 2 37 49 1 abcPSCCUTcFqSXl ``` + **样例输出** ```bash YpuUnvhaNrNluLeJzqxvwHrQJyBli 31 Yp BliGPSCCUTcFqSXlm 8 30 41 uUnvhaNrNluLeJzqxvwHrQJyBliGPSCCUTcFqSXl 32 -1 5 BYpuUnv 2 9 38 8 iG qxvw mdB 25 rNluLeJzqxvwHrQJyBliGPSCCUTcFqSXlmd 30 6 S UTcFqSXlmdBAN -1 ``` #### 【加分作业】字符串匹配算法报告 写一篇**论文**，描述下列各类算法的思想，并实现其中 `2-3` 个算法。 + 朴素算法 + KMP 算法 + 有限自动机算法 + Boyer-Moore 算法 + Simon 算法 + Colussi 算法 + Galil-Giancarlo 算法 + Apostolico-Crochemore 算法 + Horspool 算法 + Shift-Or 算法 + Sunday 算法 #### 广义表 实现广义表数据结构，要求支持从字符串中**解析**并构造广义表，以及广义表的**深度拷贝**。 具体来说，你需要通过输入的数据构造出一个广义表变量 `a`，再创建另一个广义表变量 `b`，把 `a` 的存储结构复制给 `b`，最后输出能够描述 `b` 的字符串。 **注**：要实现满足如下输入**输出格式**的程序很容易，事实上把输入的字符串直接输出就可以，但作为练习，请根据要求实现一个广义表。 + **输入格式** 一个字符串，描述了一个**非递归**，**无共享**节点的广义表。 + **输出格式** 一个字符串，表示 `b`。 + **样例输入** ```bash (1, 2, 3, 4, 5, 6, 7, (9, (11, 12, 13, 14, 15, (17, (20, ), 19),), ) ) ``` + **样例输出** ```bash (1, 2, 3, 4, 5, 6, 7, (9, (11, 12, 13, 14, 15, (17, (20), 19)))) ``` #### 实验一 这是线性表部分的实验，从以下五个题目中**选择一个**完成即可。 ##### 分时系统模拟 把CPU同时分给多个用户使用的方法，称为分时方法。设有三个用户 `Wang`，`Li`和 `Yao`，同时开始与计算机对话，具体情况如表下所示。 | 起动对话相对时间 | 用户名 | 请求CPU的时间周期 | |------------------|--------|-------------------| | 0 | Wang | 4,　8,　3 | | 1 | Li | 2,　1,　2,　2 | | 2 | Yao | 4,　6,　1 | 用户 `Wang` 在时间 `0` 进入系统经后，CPU 分配给它四个时间周期，运行得出结果后，又输入新内容，此时 CPU 又分配给它 `8` 个时间周期。最后 CPU 又分配给它3个时间周期，运行得出结果后，用户 Wang 的任务全部完成。 `Li` 和 `Yao` 的执行情况类似，只是根据用户起动的相对时间排成一个队列。 ![分时系统模拟-图2](img/分时系统模拟-图2.png) 当Wang完成了所请求的第一次的CPU时间周期后，到输入新内容再一次请求CPU时间这一时间的间隔，称为用户延迟周期（假设这里为5个时间周期）。一个适当的调度原则将CPU分配给Li，当Li完成后，同样再把CPU分配给Yao，这种原则叫"先进先出"。 这种调度原则可归纳为以下三点： 1. 当一用户请求CPU时间，它就进入请求使用CPU的队列。 2. 在此队列首部的用户是当前CPU的使用者，并在整个CPU时间周期内继续在队首。 3. 当一用户完成了它的现行请求CPU是间周期后，出队，并在下一个请求之前不再入队。 编写算法，实现该调度策略。 ##### 模拟飞机起降系统的设计 对于繁忙的机场来说，合理安排飞机的起降非常重要。你需要编写一个程序，维护飞机的起飞或降落动作、机场内外飞机的的数量及等待时间，和跑道的空闲时间。 具体来说，这座机场有以下特征： + 飞机场只有一条跑道。 + 为了保证安全，我们规定时间间隔 `t` 内只能起降一架飞机，即时间被划分为 `[0, t, 2t, 3t, ...]` 的， `t` 为整数且 `>=1`，每个 `[k*t, (k+1)*t]` 被称为一个**单位时间**。 模拟开始时： + 每一个时刻都可能有至多一架飞机请求起飞或降落，或没有飞机请求。 + 当某一时刻飞机请求起降，而下一个单位时间跑道空闲，则飞机可在下一个单位时间起飞；若不空闲，则飞机进入等待队列。 + 等待队列是有序的，降落的飞机总是排在起飞的飞机前面；对于同是起飞或降落的飞机，请求时间早的飞机总是排在请求时间晚的飞机前面。 + 机场地面和附近空域的容量都有限，所以等待队列的总容量是有限的。若某时刻等待队列已满，则这一时刻任何起降请求都会被拒绝。 ##### 多项式乘除法 给任意两个合法的一元多项式，分别输出其相乘和相除的结果。 下图所列的就是一元多项式的一般形式： ![一元多项式](img/一元多项式.png) ##### 算术表达式求值 给出任何一个合法的算术表达式，输出其后缀表达式，并求值。 例如 `1 + 2 * (3 + 4) / 5` 就是一个算术表达式，其后缀表达式为，`1 2 3 4 + * 5 / +`，值为 `3.8` ##### 食堂售饭问题 假设某食堂有四个窗口对外售饭，从上午 `11:00` 开始到下午 `13:00` 结束。 由于某窗口在某个时间只能接待一个同学，因此在学生多的时候需要在窗口前排队，刚来的同学如果发现有空闲窗口即可上前买饭，反之若均有同学则要排到人数最少的窗口的后面。 现要设计一个算法模拟这种业务并计算一天中午饭同学在食堂的平均时间。 ### 树与二叉树 #### 完全二叉树 给定一棵二叉树，判断其是否为完全二叉树。 + 输入格式 第一行一个整数 `n`，表示二叉树的节点个数。 接下来 `n` 行，每行两个整数 `i`，`p_i`，表示第 `i` 号节点的父节点编号为 `p_i`。 若 `p_i = -1`，则 `i` 是根节点。 输入保证是一棵二叉树。 + 输出格式 如果是完全二叉树，则输出`YES`，否则输出`NO`。 + 样例输入 `1` ```bash 10 1 -1 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 ``` + 样例输出 `1` ```bash YES ``` + 样例解释： 如图，是一个完全二叉树。 ![二叉树-1](img/二叉树-1.png) + 样例输入 `2` ```bash 10 1 -1 2 1 3 1 4 2 5 2 6 3 7 5 8 4 9 4 10 5 ``` + 样例输出 `2` ```bash NO ``` + 样例解释： 如图，不是一个完全二叉树。 ![二叉树-1](img/二叉树-2.png) #### 最近公共祖先 给定一棵二叉树，查询其任意两个节点的最近共祖先。 + 输入格式 第一行两个整数 `n`，`m`，表示二叉树的节点个数、询问次数。 接下来 `n` 行，每行两个整数 `i`，`p_i`，表示第 `i` 号节点的父节点编号为 `p_i`。 若 `p_i = -1`，则 `i` 是根节点。 最后 `m` 行，每行两个整数 `x`，`y`，表示查询编号为 `x`，`y` 节点的最近公共祖先（LCA）。 + 输出格式 对于每个查询，输出其 LCA 的编号。 + 样例输入 ```bash 10 5 1 -1 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 4 3 8 10 3 6 9 9 10 7 ``` + 样例输出 ```bash 1 2 3 9 1 ``` + 样例解释： 如图，是一个二叉树。 ![二叉树-1](img/二叉树-1.png) + `4` `3` 的LCA是 `1` + `8` `10` 的LCA是 `2` + `3` `6` 的LCA是 `3` + `9` `9` 的LCA是 `9` + `10` `7` 的LCA是 `1` #### 二叉堆 设计一个程序模仿操作系统的进程管理问题，进程服务按优先级高的先服务，同优先级的先到先服务的管理原则。 **注**：尽管你可以直接用快速排序完成本题，但作为练习，请使用**堆**排序。 + 输入格式 本题要求从文件输入，设文件 `task.dat` 中存放了仿真进程服务请求。 输入若干行，每行两个整数，分别表示进程号和优先级。 + 输出格式 一行，优先级从高到低依次输出进程编号，对于优先级相同的，编号小的排在前面。 + 样例输入 ```bash 1 30 2 20 3 40 4 20 5 0 ``` + 样例输出 ```bash 3 1 2 4 5 ``` #### 多路平衡归并排序（胜者树与败者树） 给出若干已经排好序的数组（或称**顺串**），分别使用胜者树和败者树对其进行排序。 + 输入格式 第一行一个整数 `n`，表示排好序的数组数。 接下来 `n` 行，每行若干整数，是一个有序序列。 + 输出格式 两行，分别表示使用胜者树和败者树进行归并排序的结果。 这两个序列应当是一致的。 **注**：尽管你可以使用快速排序、将序列输出两次、直接完成本题，但作为练习，请使用胜者树和败者树。 + 样例输入 ```bash 8 10 15 16 9 20 38 20 20 30 6 15 25 8 15 20 9 11 16 90 100 110 17 18 20 ``` + 样例输出 ```bash 6 8 9 9 10 11 15 15 15 16 16 17 18 20 20 20 20 20 25 30 38 90 100 110 6 8 9 9 10 11 15 15 15 16 16 17 18 20 20 20 20 20 25 30 38 90 100 110 ``` #### 森林的后序遍历 森林可以使用带度数的后序遍历进行存储。 给出一个森林的后续遍历，以及每个节点的节点个数，通过此来构造森林，并输出其先序遍历。 + 输入格式 第一行一个整数 `n`，表示森林的节点个数。 第二行 `n` 个整数，每个整数都代表森林的一个节点编号，这是森林的后序遍历。 第三行 `n` 个整数，其 `i` 个整数表示**第二行**的后序遍历中第 `i` 个整数对应节点的子节点数。 + 输出格式 两行，第一行 `n` 个整数表示森林的先序遍历，第二行 `n` 个整数表示森林的中序遍历。 森林子树的出现顺序在先序遍历、后序遍历中保持一致。 + 样例输入 ```bash 10 2 5 6 3 4 1 10 8 9 7 0 0 0 2 0 3 0 1 0 2 ``` + 样例输出 ```bash 1 2 3 5 6 4 7 8 10 9 ``` + 样例解释 如图，即为所求森林。 ![forest-1](img/forest-1.png) 其先序遍历为 `1 2 3 5 6 4 7 8 10 9` #### 实验二 ##### 遍历二叉树 已知一个二叉树的先序遍历、中序遍历，建立二叉树，并分别用输出该二叉树的先序遍历、中序遍历、后序遍历。 **注**：作为练习，本题的遍历算法不允许使用**递归**。 + 输入格式 第一行一个整数 `n`，表示二叉树的节点个数。 第二行是 `n` 个整数的序列，表示二叉树的先序遍历。 第三行是 `n` 个整数的序列，表示二叉树的中序遍历。 `n >= 8` + 输出格式 三行序列，分别表示二叉树的先序遍历、中序遍历、后序遍历。 + 样例输入 ```bash 10 1 2 4 8 9 5 10 3 6 7 8 4 9 2 5 10 1 6 3 7 ``` + 样例输出 ```bash 1 2 4 8 9 5 10 3 6 7 8 4 9 2 5 10 1 6 3 7 8 9 4 10 5 2 6 7 3 1 ``` + 样例解释 如图，即为所求二叉树。 ![二叉树-1](img/二叉树-1.png) ##### 哈夫曼树 给出一篇英文文章，构造哈夫曼树，并对其进行编码、译码。 以下输入输出格式**仅供参考**。 + 输入格式 从 `article.txt` 中输入一篇英文文章，可能包含 `ascii` 码表的所有字符。 + 输出格式 输出至以下 `3` 个文件。 + `huffman-encode-list.txt`：包含文章字符出现频率，以及编码结果。 + `binary.txt`：整篇文章的编码结果。 + `decode-result.txt`：由编码重新解析回文章的结果。 + 样例输入 `article.txt` ```txt What is Lorem Ipsum? Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book. It has survived not only five centuries, but also the leap into electronic typesetting, remaining essentially unchanged. It was popularised in the 1960s with the release of Letraset sheets containing Lorem Ipsum passages, and more recently with desktop publishing software like Aldus PageMaker including versions of Lorem Ipsum. Where does it come from? Contrary to popular belief, Lorem Ipsum is not simply random text. It has roots in a piece of classical Latin literature from 45 BC, making it over 2000 years old. Richard McClintock, a Latin professor at Hampden-Sydney College in Virginia, looked up one of the more obscure Latin words, consectetur, from a Lorem Ipsum passage, and going through the cites of the word in classical literature, discovered the undoubtable source. Lorem Ipsum comes from sections 1.10.32 and 1.10.33 of "de Finibus Bonorum et Malorum" (The Extremes of Good and Evil) by Cicero, written in 45 BC. This book is a treatise on the theory of ethics, very popular during the Renaissance. The first line of Lorem Ipsum, "Lorem ipsum dolor sit amet..", comes from a line in section 1.10.32. The standard chunk of Lorem Ipsum used since the 1500s is reproduced below for those interested. Sections 1.10.32 and 1.10.33 from "de Finibus Bonorum et Malorum" by Cicero are also reproduced in their exact original form, accompanied by English versions from the 1914 translation by H. Rackham. Why do we use it? It is a long established fact that a reader will be distracted by the readable content of a page when looking at its layout. The point of using Lorem Ipsum is that it has a more-or-less normal distribution of letters, as opposed to using 'Content here, content here', making it look like readable English. Many desktop publishing packages and web page editors now use Lorem Ipsum as their default model text, and a search for 'lorem ipsum' will uncover many web sites still in their infancy. Various versions have evolved over the years, sometimes by accident, sometimes on purpose (injected humour and the like). Where can I get some? There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don't look even slightly believable. If you are going to use a passage of Lorem Ipsum, you need to be sure there isn't anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend to repeat predefined chunks as necessary, making this the first true generator on the Internet. It uses a dictionary of over 200 Latin words, combined with a handful of model sentence structures, to generate Lorem Ipsum which looks reasonable. The generated Lorem Ipsum is therefore always free from repetition, injected humour, or non-characteristic words etc. ``` + 样例输出 `huffman-encode-list.txt` ```txt ascii code: 0, frequency: 0.0000000, huffman code: 100100001110010100000010010111111010000 ascii code: 1, frequency: 0.0000000, huffman code: 1001000011100101000000100100 ascii code: 2, frequency: 0.0000000, huffman code: 100100001110010100000010010111111010001 ascii code: 3, frequency: 0.0000000, huffman code: 10010000111001010001 ascii code: 4, frequency: 0.0000000, huffman code: 100100001110010100000010011 ascii code: 5, frequency: 0.0000000, huffman code: 1001000011100101000000100101000011 ascii code: 6, frequency: 0.0000000, huffman code: 100100001110010100000010010111111010011 ascii code: 7, frequency: 0.0000000, huffman code: 1001000011100010101 ascii code: 8, frequency: 0.0000000, huffman code: 10010000111000000010 ascii code: 9, frequency: 0.0000000, huffman code: 10010000111000000011101 ascii code: 10, frequency: 0.0038697, huffman code: 10010101 ascii code: 11, frequency: 0.0000000, huffman code: 10010000111001010000001001010001 ascii code: 12, frequency: 0.0000000, huffman code: 100100001110010100000010010111101 ascii code: 13, frequency: 0.0038697, huffman code: 11011011 ascii code: 14, frequency: 0.0000000, huffman code: 100100001110010100000010010111111010010 ascii code: 15, frequency: 0.0000000, huffman code: 1001000011100001 ascii code: 16, frequency: 0.0000000, huffman code: 10010000111000001 ascii code: 17, frequency: 0.0000000, huffman code: 100100001110010101 ascii code: 18, frequency: 0.0000000, huffman code: 10010000111000000100 ascii code: 19, frequency: 0.0000000, huffman code: 1001000011100000001111 ascii code: 20, frequency: 0.0000000, huffman code: 10010000111000000011010 ascii code: 21, frequency: 0.0000000, huffman code: 10010000111001010000001000 ascii code: 22, frequency: 0.0000000, huffman code: 10010000111000000011100001 ascii code: 23, frequency: 0.0000000, huffman code: 1001000011100101000000100101001 ascii code: 24, frequency: 0.0000000, huffman code: 1001000011100101000000100101110 ascii code: 25, frequency: 0.0000000, huffman code: 100100001110010100000010010100000 ascii code: 26, frequency: 0.0000000, huffman code: 100100001110010100000010010111100 ascii code: 27, frequency: 0.0000000, huffman code: 10010000111001010000001001011111011 ascii code: 28, frequency: 0.0000000, huffman code: 10010000111001010000001001011111111 ascii code: 29, frequency: 0.0000000, huffman code: 100100001110010100000010010111110101 ascii code: 30, frequency: 0.0000000, huffman code: 10010000111001010000001001011111100010 ascii code: 31, frequency: 0.0000000, huffman code: 100100001110011 ascii code: 32, frequency: 0.1618833, huffman code: 101 ascii code: 33, frequency: 0.0000000, huffman code: 1001000011100100 ascii code: 34, frequency: 0.0019349, huffman code: 110110100 ascii code: 35, frequency: 0.0000000, huffman code: 10010000111001011 ascii code: 36, frequency: 0.0000000, huffman code: 10010000111000101001 ascii code: 37, frequency: 0.0000000, huffman code: 1001000011100000000 ascii code: 38, frequency: 0.0000000, huffman code: 10010000111000000101 ascii code: 39, frequency: 0.0022573, huffman code: 100100000 ascii code: 40, frequency: 0.0006450, huffman code: 10011110110 ascii code: 41, frequency: 0.0006450, huffman code: 10010000110 ascii code: 42, frequency: 0.0000000, huffman code: 10010000111000000011011 ascii code: 43, frequency: 0.0000000, huffman code: 1001000011100000001110001 ascii code: 44, frequency: 0.0103193, huffman code: 1001110 ascii code: 45, frequency: 0.0012899, huffman code: 011100110 ascii code: 46, frequency: 0.0109642, huffman code: 1000101 ascii code: 47, frequency: 0.0000000, huffman code: 1001000011100101000000100101010 ascii code: 48, frequency: 0.0048371, huffman code: 10010001 ascii code: 49, frequency: 0.0048371, huffman code: 10010011 ascii code: 50, frequency: 0.0016124, huffman code: 011100100 ascii code: 51, frequency: 0.0022573, huffman code: 100100101 ascii code: 52, frequency: 0.0009674, huffman code: 1101101010 ascii code: 53, frequency: 0.0012899, huffman code: 1001000010 ascii code: 54, frequency: 0.0003225, huffman code: 1001000011101 ascii code: 55, frequency: 0.0000000, huffman code: 10010000111001010000001001010000101 ascii code: 56, frequency: 0.0000000, huffman code: 10010000111001010000001001010000100 ascii code: 57, frequency: 0.0006450, huffman code: 11011010111 ascii code: 58, frequency: 0.0000000, huffman code: 10010000111001010000001001011111110 ascii code: 59, frequency: 0.0000000, huffman code: 100100001110010100000010010111111001 ascii code: 60, frequency: 0.0000000, huffman code: 100100001110010100000010010111110100 ascii code: 61, frequency: 0.0000000, huffman code: 10010000111001010000001001011111101011 ascii code: 62, frequency: 0.0000000, huffman code: 10010000111001010000001001011111100011 ascii code: 63, frequency: 0.0012899, huffman code: 1001010011 ascii code: 64, frequency: 0.0000000, huffman code: 10010000111000100 ascii code: 65, frequency: 0.0006450, huffman code: 0111001111 ascii code: 66, frequency: 0.0012899, huffman code: 1001111100 ascii code: 67, frequency: 0.0025798, huffman code: 100111111 ascii code: 68, frequency: 0.0000000, huffman code: 100100001110001011 ascii code: 69, frequency: 0.0012899, huffman code: 1001111101 ascii code: 70, frequency: 0.0006450, huffman code: 0111001110 ascii code: 71, frequency: 0.0003225, huffman code: 11011010110 ascii code: 72, frequency: 0.0006450, huffman code: 10011110010 ascii code: 73, frequency: 0.0083844, huffman code: 1001011 ascii code: 74, frequency: 0.0000000, huffman code: 10010000111000101000 ascii code: 75, frequency: 0.0000000, huffman code: 1001000011100000011 ascii code: 76, frequency: 0.0074170, huffman code: 1101100 ascii code: 77, frequency: 0.0016124, huffman code: 011100101 ascii code: 78, frequency: 0.0000000, huffman code: 1001000011100101001 ascii code: 79, frequency: 0.0000000, huffman code: 100100001110010100001 ascii code: 80, frequency: 0.0003225, huffman code: 100100001111 ascii code: 81, frequency: 0.0000000, huffman code: 1001000011100000001100 ascii code: 82, frequency: 0.0009674, huffman code: 1001010010 ascii code: 83, frequency: 0.0006450, huffman code: 10011110111 ascii code: 84, frequency: 0.0022573, huffman code: 100101000 ascii code: 85, frequency: 0.0000000, huffman code: 1001000011100101000001 ascii code: 86, frequency: 0.0006450, huffman code: 10011110011 ascii code: 87, frequency: 0.0012899, huffman code: 1001111000 ascii code: 88, frequency: 0.0000000, huffman code: 100100001110000000111001 ascii code: 89, frequency: 0.0000000, huffman code: 100100001110010100000000 ascii code: 90, frequency: 0.0000000, huffman code: 100100001110010100000011 ascii code: 91, frequency: 0.0000000, huffman code: 1001000011100101000000011 ascii code: 92, frequency: 0.0000000, huffman code: 1001000011100101000000101 ascii code: 93, frequency: 0.0000000, huffman code: 10010000111000000011100000 ascii code: 94, frequency: 0.0000000, huffman code: 1001000011100101000000010 ascii code: 95, frequency: 0.0000000, huffman code: 100100001110010100000010010110 ascii code: 96, frequency: 0.0000000, huffman code: 1001000011100101000000100101011 ascii code: 97, frequency: 0.0512738, huffman code: 10000 ascii code: 98, frequency: 0.0116092, huffman code: 1000100 ascii code: 99, frequency: 0.0219284, huffman code: 100011 ascii code: 100, frequency: 0.0280555, huffman code: 11010 ascii code: 101, frequency: 0.0980329, huffman code: 000 ascii code: 102, frequency: 0.0158014, huffman code: 111001 ascii code: 103, frequency: 0.0141890, huffman code: 110111 ascii code: 104, frequency: 0.0270880, huffman code: 01100 ascii code: 105, frequency: 0.0528862, huffman code: 0011 ascii code: 106, frequency: 0.0012899, huffman code: 1001111010 ascii code: 107, frequency: 0.0077394, huffman code: 1110000 ascii code: 108, frequency: 0.0270880, huffman code: 01101 ascii code: 109, frequency: 0.0309578, huffman code: 11101 ascii code: 110, frequency: 0.0519187, huffman code: 0010 ascii code: 111, frequency: 0.0635279, huffman code: 1111 ascii code: 112, frequency: 0.0196711, huffman code: 100110 ascii code: 113, frequency: 0.0000000, huffman code: 1001000011100101000000100101111100 ascii code: 114, frequency: 0.0541761, huffman code: 0100 ascii code: 115, frequency: 0.0567559, huffman code: 0101 ascii code: 116, frequency: 0.0619155, huffman code: 1100 ascii code: 117, frequency: 0.0267656, huffman code: 01111 ascii code: 118, frequency: 0.0070945, huffman code: 0111000 ascii code: 119, frequency: 0.0077394, huffman code: 1110001 ascii code: 120, frequency: 0.0022573, huffman code: 100100100 ascii code: 121, frequency: 0.0135440, huffman code: 011101 ascii code: 122, frequency: 0.0000000, huffman code: 1001000011100101000000100101111110110 ascii code: 123, frequency: 0.0000000, huffman code: 10010000111001010000001001011111101010 ascii code: 124, frequency: 0.0000000, huffman code: 1001000011100101000000100101111110000 ascii code: 125, frequency: 0.0000000, huffman code: 10010000111001010000001001011111101110 ascii code: 126, frequency: 0.0000000, huffman code: 10010000111001010000001001011111101111 ascii code: 127, frequency: 0.0000000, huffman code: 1001000011100011 ``` `binary.txt`（为防止页面炸掉，已转换为十六进制表示，末尾不足补零） ```txt 9E 19 0C A6 B7 67 A0 ED 97 32 BF B2 9E DC AE CF 41 DB 2E 65 7F 69 AD 53 EC CD 76 E9 FD EB B7 04 93 2F F3 71 82 CC 86 58 65 BD 81 6A E3 B3 05 19 86 5B D3 2D 3D 71 1D 8B 76 7A 0E D9 73 2B FB 59 05 B1 00 2B 8C 14 CB 4F 5C 47 64 0B 57 20 5A 82 6A E9 FD EB B7 04 93 28 70 12 A9 94 62 E3 05 93 90 A4 64 56 75 E2 C0 56 05 5E 5C 0B F8 95 99 0C B0 25 CF FE 16 17 78 35 A1 DB FC DC 76 61 60 5A AB 1A 43 B1 1A 35 4F 2E 7D EC 38 0B 0B 8E CC 2A CC 23 3E 82 B1 3F F8 45 B2 F2 B2 0B 55 E8 E0 DC 0D 52 FC BE 4D 76 F2 6E 05 8C 16 3D 0C 2C EB 11 F9 60 D5 FB 8C 15 A2 13 53 2C FA 1A 23 C4 F2 38 EE 3B 30 51 98 65 BC EA 83 B0 32 32 DE 85 50 58 70 6B 5D AF 28 D9 02 DC 6A 2D 97 97 8C 16 CD F3 3D B0 43 51 AA 65 71 82 C9 ED 79 0E C8 AD E2 78 CB 8C 15 03 44 14 5F E6 EC 18 90 51 95 58 06 2D 8F CB 20 64 65 BD D9 E8 3B 65 CC AF ED 9A 0A B0 DC 2C EB 02 D5 EF A0 A8 23 05 8D 76 F1 3C 65 D0 5E 19 F3 59 9F 11 A6 AC 32 DE AF F3 9C 60 82 B4 F8 0A E7 B7 4F 5B 21 F0 DC 39 61 C0 25 32 8D AF D1 96 F5 C0 45 3F 25 BF CD D9 E8 3B 65 CC AF EC 5D B9 5D B9 59 E1 81 05 D7 85 A7 96 3F E8 BC A7 F6 53 DB 95 9F F9 62 41 1D B9 F6 6F 99 ED 82 58 81 A6 39 9D 76 7A 0E D9 73 2B FB 4D 69 7E 55 3E CC D7 6A 40 B5 FD B8 24 99 16 CB CA C8 2D 4F FC 5A 65 61 66 31 18 BF CD 8D B0 55 38 E0 DB B2 18 65 5A 78 12 18 F4 17 94 FE DD AA 42 B3 E4 FE 75 EC 38 19 6F 4F 2F B8 09 5C 92 32 32 35 D1 04 5B ED D4 5B 29 1C 6C 82 6A B9 63 9F B4 CB 3E 3E 13 AC 2E C8 61 95 99 3F 90 AB E9 61 96 79 43 B3 68 13 9A 7B BB A2 0E D9 FF B5 A3 71 4C AC F3 34 DC C8 E1 3A B7 FF 80 D5 7C D7 C8 5F E6 E3 05 EF A0 BF 11 63 7A 0B B2 18 65 78 FA 69 67 58 FC 94 47 83 1E 93 AF 29 FD B0 BB 3D 07 6C B9 95 FD B3 41 56 1B 89 D6 05 AB BF 99 6F 71 89 EF DD 97 18 2C 67 81 6F F3 71 82 F1 F4 D5 32 B1 B6 0A A7 1C 1B 5A 78 12 18 F4 13 AE 8D 63 F7 01 06 AE 30 57 96 BD F1 32 11 1A 2A FB D2 31 16 EC F4 1D B2 E6 57 F6 C7 FD 0B 79 4F ED 51 1E 1F 92 D9 38 B2 72 31 64 AE 4B 02 D5 93 8B 27 23 16 4B 25 BF CD DA 68 57 38 C8 E2 3D 6C F9 E5 E8 FE D1 95 CB 06 FA 3F BB 4B 3D A5 0C 16 7D 92 62 0E 85 BF CD DA DF FA B0 2D 59 F5 C1 B6 43 58 8E D9 F9 C6 13 E7 5E 28 79 80 A9 95 DA A4 2B 3E 4F E2 D9 43 0D 6C 4F FE 14 D6 C2 E2 08 61 A8 BE 57 18 2E 30 7A 3B 7F 9A 31 87 1A CE AE 02 3B 66 F9 9E D8 25 D3 D0 CB 7B 8C 16 52 05 03 55 81 46 22 D9 43 05 E4 D1 72 B4 C8 5F E6 EC F4 1D B2 E6 57 F6 75 DA 6C F4 1D A7 32 BF B7 5E DF 4A A7 96 1D 19 16 2E D2 75 8F FA 16 F2 9F DB 0A D3 21 4C AA 88 F0 FC AC 9C 59 39 18 B2 57 24 5D B9 59 43 05 5C 81 6A 09 AB 1B 1E 5C 2F F3 76 7A 0E D9 73 2B FB 5E A3 55 4C A3 17 18 2C 9C 85 23 22 B4 D6 A0 99 3F 4F 8C 6A C4 0D FE 37 9F 4B 8C F5 14 CB 02 05 C1 A8 B6 7B 88 F0 FC 96 C9 C5 93 91 8B 25 72 58 16 AC 9C 59 39 18 B2 59 2D E5 3F B7 69 A1 5C E3 23 88 F5 B3 E7 97 A3 FB 46 57 2C 1B E8 FE ED 2C 47 6C FC E3 09 F6 08 2C 1A BF 50 4C 9F A7 C6 35 4C AE 30 1A 51 24 84 79 7D 0F 73 28 36 F3 E9 D9 D6 11 C7 FD 9A 04 63 56 23 B6 7D 2D DA 6A CA E0 22 9F 92 DE 53 FB 71 82 C9 ED 79 3D AA E2 40 95 B0 C3 F2 B1 1D B3 CA 2D 94 A1 1F 06 43 B1 76 E5 76 E5 67 86 3B 75 F7 88 AF 51 4F 25 3D B9 59 79 4D 6C 2B 7C B7 A1 72 11 1A 6A C1 AB CC 23 CB 8C 86 58 54 10 D0 4B C4 DA DB 10 5D 1A E2 42 3C 1A B1 1D B8 C1 50 43 50 88 D1 63 F2 C0 59 7F 9B 0B 34 37 17 8B 01 56 FF F0 32 DE C3 29 E2 D6 C1 DF 7E 45 B2 86 0B 37 99 65 FE 6B D4 CB 7B B3 D0 76 CB 99 5F DA 6B 71 90 CA 79 59 05 B0 BD F4 0E 6F 47 33 42 AD 2F 4E C1 B7 46 B8 87 11 F8 7E 57 F9 AD 19 81 16 75 82 DF 9A 6F 51 AB 9F 5E A6 5B D9 04 FF CB 01 65 60 41 3A C7 E5 80 B2 B0 20 90 4E BD 87 03 2D E9 E5 6F FF 0A D3 E0 2A 08 6A 11 1A 2C FA 5B B4 D5 91 6B 96 04 ED D0 5E 19 F3 59 9F 11 A6 AC 32 DE CD 08 F8 43 70 B6 05 AB C4 44 B3 43 71 46 8F 3D 16 97 F1 AF 51 76 7A 0E D9 73 2B FB 60 B7 18 0D 2E 87 30 7B 72 F7 F4 1B 70 49 32 75 81 6A C2 A8 82 46 CB CF A5 90 37 D0 76 9C CA FE C8 2F 13 6B 6B CA 3F 70 12 F6 04 ED E2 22 55 3C 0B 57 0D AD A6 57 18 0D 29 97 30 28 DD 8B 67 9C 10 FD EB 5C 04 53 F2 5A C8 38 14 38 F6 B8 1A BE E0 25 C6 0A E8 82 2C EA BF D1 87 D0 B6 23 B6 11 C6 7A 05 93 AA FF 46 1F 42 DF 2B 33 D2 6F 51 67 B1 94 F4 23 C1 AA C7 F7 DE 96 05 AB 8C 15 A7 C0 48 68 BB 72 BB 72 B3 C3 02 0B 1C 0A CB BB 8C AB FD 12 9E DC AC A1 81 05 82 0B D8 13 B5 C4 10 E1 87 E4 B7 F9 B3 41 56 1B 85 BF CD D9 E8 3B 65 CC AF ED 83 88 1B 61 11 A2 75 88 FC B8 C1 7B 09 EB D0 F1 DA C8 38 15 5F CF 21 06 AC 1B 81 21 87 E5 4C AA FF 45 E7 D3 B3 AC 47 69 94 F4 23 C1 AA C7 F7 DE 93 AF A5 48 16 BF A6 A3 57 8F A6 96 F1 61 C6 CB AF 29 06 56 FF F0 A1 C0 2A AD 3D D9 8D 76 C4 0D 30 E2 11 1A 22 D9 7C D7 7D F6 08 2E FE 65 BD CF AF 51 61 66 82 AC 37 17 F9 BB 3D 07 6C B9 95 FD 9D 5D F7 D2 03 57 3E C4 15 5E 82 E3 02 0A 6A 52 0C B0 27 71 86 5B D1 D8 90 44 82 A9 96 F5 87 AD 02 A6 57 18 2F 4F 5A 68 BF CD C1 24 C8 B5 CF 6B 6E 30 5D 9E 83 B6 5C CA FE DD C1 04 86 7A 2D F2 B8 C1 65 96 04 21 97 01 6A E7 D4 13 08 65 99 06 87 26 43 56 36 3C B8 2D 82 D2 11 85 58 23 B3 AF 61 C0 CB 7B 8C 35 B8 C1 79 34 5C B8 8F 17 70 41 21 9E 97 CA E3 05 96 58 10 86 45 B2 F2 BD 42 D8 5D 1C 78 7E 50 47 6F F3 7D C0 4A E4 91 91 BB 21 86 57 8F A6 96 75 8F FB 10 C8 6A F1 3C 65 85 64 0B 5C BD B7 F9 BD FD 06 D5 05 80 A3 15 71 1F 1E 3D 02 CE B9 F7 70 41 21 82 EC F4 1D B2 E6 57 F6 F1 61 C6 CA DF FE 0B 50 41 7C A1 11 A2 2D 94 30 5D C1 04 86 0D 5D 9E 83 B6 5C CA FE D3 5B 8C 08 39 F4 16 0D E3 07 56 F2 80 5E 53 FB 50 4C 30 F0 FC A7 53 29 E8 47 83 55 8F EF BD 27 5F 4A 5E 4E 68 D9 04 84 78 10 D7 0E 3B C7 D3 4B 46 47 17 6E 54 ``` `decode-result.txt` ```txt What is Lorem Ipsum? Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book. It has survived not only five centuries, but also the leap into electronic typesetting, remaining essentially unchanged. It was popularised in the 1960s with the release of Letraset sheets containing Lorem Ipsum passages, and more recently with desktop publishing software like Aldus PageMaker including versions of Lorem Ipsum. Where does it come from? Contrary to popular belief, Lorem Ipsum is not simply random text. It has roots in a piece of classical Latin literature from 45 BC, making it over 2000 years old. Richard McClintock, a Latin professor at Hampden-Sydney College in Virginia, looked up one of the more obscure Latin words, consectetur, from a Lorem Ipsum passage, and going through the cites of the word in classical literature, discovered the undoubtable source. Lorem Ipsum comes from sections 1.10.32 and 1.10.33 of "de Finibus Bonorum et Malorum" (The Extremes of Good and Evil) by Cicero, written in 45 BC. This book is a treatise on the theory of ethics, very popular during the Renaissance. The first line of Lorem Ipsum, "Lorem ipsum dolor sit amet..", comes from a line in section 1.10.32. The standard chunk of Lorem Ipsum used since the 1500s is reproduced below for those interested. Sections 1.10.32 and 1.10.33 from "de Finibus Bonorum et Malorum" by Cicero are also reproduced in their exact original form, accompanied by English versions from the 1914 translation by H. Rackham. Why do we use it? It is a long established fact that a reader will be distracted by the readable content of a page when looking at its layout. The point of using Lorem Ipsum is that it has a more-or-less normal distribution of letters, as opposed to using 'Content here, content here', making it look like readable English. Many desktop publishing packages and web page editors now use Lorem Ipsum as their default model text, and a search for 'lorem ipsum' will uncover many web sites still in their infancy. Various versions have evolved over the years, sometimes by accident, sometimes on purpose (injected humour and the like). Where can I get some? There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don't look even slightly believable. If you are going to use a passage of Lorem Ipsum, you need to be sure there isn't anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend to repeat predefined chunks as necessary, making this the first true generator on the Internet. It uses a dictionary of over 200 Latin words, combined with a handful of model sentence structures, to generate Lorem Ipsum which looks reasonable. The generated Lorem Ipsum is therefore always free from repetition, injected humour, or non-characteristic words etc. ``` ### 图及算法 #### 农夫过河 农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小、除农夫之外每次只能运一种东西，还有一个棘手问题，就是如果没有农夫看着，羊会偷菜吃，狼会吃羊。请考虑一种方法，让农夫能够安全地安排这些东西和自己过河。 + 输入格式 无 + 输出格式 若干行，表示每次农夫从哪将运输或不运输什么东西，形如以下描述都是合法的。 + `农夫运输羊到对岸` + `农夫从对岸运输狼回来` + `农夫到对岸，不运输任何东西` + 样例输入 ```bash #N/A ``` + 样例输出 ```bash #无可奉告 ``` #### 实验三 ##### 图的遍历 给出一个图，指定开始节点，求其任意DFS序（深度优先搜索序）、BFS序（广度优先搜索序）。 + 输入格式 第一行两个整数 `n`，`m`，`s`，表示点数、边数和开始节点。 接下来 `m` 行，每行两个整数 `u`，`v`，表示从 `u` 至 `v` 有一条边。 输入保证开始节点能够到达所有节点。 + 输出格式 第一行 `n` 个整数，表示图的任意DFS序。 第二行 `m` 个整数，表示图的任意BFS序。 + 样例输入 ```bash 8 14 6 6 2 6 4 6 5 1 4 1 5 2 3 2 4 4 5 7 1 5 7 7 3 8 5 6 8 1 3 ``` + 样例输出 ```bash 6 8 5 7 1 3 4 2 6 8 5 4 2 7 3 1 ``` + 样例解释 如图： ![graph-1](img/graph-1.png) 显然可得从 `6` 开始的 DFS 序和 BFS 序。 ##### 工程安排 一项工程由多道工序组成，按照施工过程的要求，这些工序之间，客观上有一个必须遵守的先后关系。对那些紧接在已知工序前的工序叫紧前工序，把已知工序后边紧接的工序叫后项工序，只有已知工序的所有紧前工序都完成，已知工序才能开始施工。例如某项工程的工序表如下： | 代号 | 紧前工序 | 完成时间 | 代号 | 紧前工序 | 完成时间 | |:----:|:--------:|:--------:|:----:|:--------:|:--------:| | 1 | | 6 | 6 | 3 | 2 | | 2 | | 2 | 7 | 4 | 3 | | 3 | 1 | 3 | 8 | 2, 5 | 4 | | 4 | 1 | 5 | 9 | 8 | 2 | | 5 | 1 | 3 | 10 | 6, 7, 9 | 2 | 给出若干工序及其先后关系、完成所需时间，求完成所有工序所需最短时间。 + 输入格式 第一行两个整数 `n`，`m`，表示工艺数，关系数。 第二行 `n` 个整数，第 `i` 个整数表示第 `i` 号工序所需时间。 接下来 `m` 行，每行两个整数 `u`，`v`，表示 `u` 是 `v` 的紧前工序。 + 输出格式 第一行若干个整数，表示最长关键路径。 第二行一个整数，表示完成所有工序所需的最少时间。 + 样例输入 ```bash 10 11 6 2 3 5 3 2 3 4 2 2 1 3 1 4 1 5 2 8 3 6 4 7 5 8 8 9 6 10 7 10 9 10 ``` + 样例输出 ```bash 1 5 8 9 10 17 ``` + 样例解释 如图： ![graph-2](img/graph-2.png) 工艺线路 `1 -> 5 -> 8 -> 9 -> 10` 所耗费的时间最长，为 `6 + 3 + 4 + 2 + 2 = 17` 。 ### 查找 #### 二分查找 给出一个**有序**整数序列，每次询问一个数，求这个数在序列中的索引范围 `[a, b)` （上界和下界）。 为了使问题一般化，我们对上下界做出如下定义： 对于一个序列（数组） `a` 和一个数 `v` ： + 下界：最小的 `i` ，使得 `a[i] >= v` 。 + 上界：最小的 `i` ，使得 `a[i] > v` 。 **注**；作为练习，请使用二分查找，保证每次询问在`O(log(n))`时间复杂度内处理完成，否则会**超时**。 + 输入格式 第一行两个整数 `n`，`m`，表示序列长度和询问个数（`n <= 1e5`，`m <= 1e5`）。 第二行 `n` 个整数，表示这个序列。 接下来 `m` 行，每行一个整数，表示询问其上下界。 序列索引范围 `[1, ..., n]` + 输出格式 `m` 行，每行两个整数 `a`，`b`，表示每个询问的结果，即输出其上下界，表示区间 [a, b) 内有此数。 + 样例输入 ```bash 10 5 1 2 2 2 4 5 5 7 9 10 2 7 5 4 8 ``` + 样例输出 ```bash 2 5 8 9 6 8 5 6 9 9 ``` + 样例解释 #### 二叉搜索树 #### 跳表、AVL树与红黑树 阅读跳表、AVL树与红黑树相关原理介绍，完成以下任务： + 理解跳表、AVL树与红黑树原理。 + 实现跳表、AVL树或红黑树之一【选做】