初赛笔记

CSP 初赛笔记，持续更新中。

出栈序列

出栈序列满足 FILO 的规则，也就是先进后出。

• 如果入栈的顺序是降序排列，那么可以快速判断的依据就是任意数A的后面比A大的数都是按照升序排列的
• 如果入栈的顺序是升序排列，那么可以快速判断的依据就是任意数A的后面比A小的数都是按照降序排列的

哈夫曼编码

哈夫曼编码详解——图解真能看了秒懂\_已知字符集abcdef,若各字符出现的次数-CSDN博客

第一步

先统计出每个字符在字符串中出现的次数。

第二步

每次选取数组中可以选取最小的两个数，进行以下操作。

• 如果这是第一次选取，那么把建一个树，父节点是这两个数的和，子节点是这两个数。

• 先把这两个数先小再大依次进行以下操作：

  • 如果这个数比现在的根节点的小，那么和这个根节点结合，再生成一个父节点。
  • 否则单独把这个数挑出来变为一棵树。

第三步

给每个叶子结点关联到字符，然后按 dfs 的顺序，左孩子标 0，右孩子标 1。