CSP蒙题小技巧

CSP初试快速指南

1. 给定入栈顺序，如何判断一个出栈顺序是否合法？
   对于出栈序列中的任意元素$x$，所有在$x$之后出栈且在入栈顺序中位于$x$之前的元素，必须按照与入栈顺序相反的顺序出栈。
2. 各类排序算法的时间复杂度与稳定性

   排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
   冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定
   选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
   插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定
   希尔排序	O(n^1.3)	O(n²)	O(n)	O(1)	不稳定
   归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
   快速排序	O(n log n)	O(n²)	O(n log n)	O(log n)	不稳定
   堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
   计数排序	O(n + k)	O(n + k)	O(n + k)	O(n + k)	稳定
   桶排序	O(n + k)	O(n²)	O(n)	O(n + k)	稳定
   基数排序	O(n × k)	O(n × k)	O(n × k)	O(n + k)	稳定

3. 各类基础算法的时间复杂度

   算法分类	具体算法/操作	时间复杂度
   1. 线性查找与访问	数组随机访问（按索引）	O(1)
   	线性查找（无序数组/链表）	O(n)
   	链表访问（按索引）	O(n)
   2. 高效查找	二分查找（有序数组）	O(log n)
   3. 排序算法	冒泡排序/插入排序	O(n²)
   	快速排序（平均情况）	O(n log n)
   	归并排序	O(n log n)
   	堆排序	O(n log n)
   4. 树与图基础	二叉树遍历（前/中/后序、层序）	O(n)
   	深度优先搜索（DFS）- 图/树	O(V + E)
   	广度优先搜索（BFS）- 图/树	O(V + E)
   5. 数学与简单操作	快速幂（计算 aⁿ mod m）	O(log n)
   	欧几里得算法（最大公约数）	O(log min(a,b))
   	前缀和（数组区间和）	O(n) 预处理/O(1) 查询

4. $X$进制转$Y$进制的实用方法 第一步，先把$X$进制数转成十进制数
   1. 先明确“权值”：X进制数从右往左数，第1位（最右边）的权是X⁰（也就是1），第2位是X¹，第3位是X²，以此类推。
   2. 计算总和：把X进制数的每一位数字，分别乘以它对应的权值，然后把所有结果加起来，得到的就是十进制数。
   e.g. 把二进制数“1011”转成十进制
   • 从右数，各位数字和权值对应：
     第0位（最右）：1 × 2⁰ = 1×1 = 1
     第1位：1 × 2¹ = 1×2 = 2
     第2位：0 × 2² = 0×4 = 0
     第3位（最左）：1 × 2³ = 1×8 = 8
   • 加起来：1+2+0+8 = 11 → 十进制就是11。
   第二步，再把十进制数转成$Y$进制数
   1. 反复做除法：用第一步得到的十进制数除以Y，每次都记下“余数”（这个余数就是Y进制数的一位，而且是从低位开始算的）。
   2. 倒序排余数：直到除法的商变成0，就停止计算。然后把之前记下的所有余数，从最后一个往第一个排，得到的就是Y进制数。
   举个例子：把十进制数“11”转成八进制
   • 第一次算：11 ÷ 8 = 1，余数是3（这是八进制的最低位）
   • 第二次算：1 ÷ 8 = 0，余数是1（这是八进制的高位）
   • 余数倒序排：1、3 → 八进制就是“13”。
   2的幂进制互转 如果X和Y都是2的倍数（比如2进制、4进制、8进制、16进制），不用过十进制，直接“按位分组”就行。
   比如二进制转16进制（16是2⁴）：把二进制数从右往左，每4位分成一组（不够4位的话，左边补0），然后每组转成十进制数，就是16进制的一位（10-15用A-F表示）。
   例子：二进制“1101011”转16进制
   • 分组：补0成“0110 1011”
   • 每组转十进制：0110=6，1011=11（即B）
   • 结果就是“6B”。
5. 链表和数组的区别？

   对比维度	数组（Array）	链表（Linked List）
   内存存储	连续内存空间，需预先分配（或动态扩容）	非连续内存空间，节点按需分配，靠指针/引用连接
   访问效率	O(1)（随机访问，通过下标直接定位）	O(n)（顺序访问，需从表头遍历到目标节点）
   插入/删除	O(n)（中间/头部操作需移动后续元素）	O(1)（已知前驱节点时，仅需修改指针/引用）
   空间效率	可能有内存浪费（如预分配过大），无额外开销	无内存浪费，但每个节点需额外存储指针/引用（如单链表每个节点多存1个地址）
   长度灵活性	固定长度（静态）或动态扩容（需复制旧数据，有性能损耗）	长度动态可变，增减节点无需整体调整
   适用场景	频繁随机访问（如按索引查数据）、数据量固定或变化少	频繁插入/删除（如链表头部/中间操作）、数据量动态变化大

6. 如何快速判断一个给定的哈夫曼编码组是否合法？
   将所有待验证的哈夫曼编码，按长度升序排列；若长度相同，按编码的字典序（如 0<1）排列。
   依次对比排序后相邻的两个编码，判断较短编码是否是较长编码的前缀。

7. 如何快速判断一个给定的二进制格雷码组是否合法？
   检查完整性：若为 n 位格雷码，编码总数必须是 2ⁿ 个（例如 3 位格雷码有 8 个编码），且每个编码长度均为 n 位（不足补前导 0）。
   排序编码：按二进制数值从小到大排序（或按格雷码的自然顺序排列）。
   验证相邻差异：依次检查排序后每对相邻编码，确认它们之间恰好只有 1 位二进制不同（0 和 1 的差异）。
   检查首尾循环性（可选，取决于是否要求 “循环格雷码”）：若为循环格雷码，第一个编码和最后一个编码也需满足 “仅 1 位不同”。
8. 不同数据类型的数据范围

   数据类型	字节数	数据范围（十进制）
   short	2	-32768 ～ 32767
   unsigned short	2	0 ～ 65535
   int	4	-2147483648 ～ 2147483647
   unsigned int	4	0 ～ 4294967295
   long	4（32位系统）/8（64位系统）	-2147483648 ～ 2147483647（32位）-9223372036854775808 ～ 9223372036854775807（64位）
   unsigned long	4（32位系统）/8（64位系统）	0 ～ 4294967295（32位）0 ～ 18446744073709551615（64位）
   long long	8	-9223372036854775808 ～ 9223372036854775807
   unsigned long long	8	0 ～ 18446744073709551615

9. 前、中、后缀表达式的快速转换技巧
   • 中缀转后缀
     1. 无括号场景（如 a+b*c-d）： 第一步：按运算符优先级给“先算的部分”打隐形括号 → a+(b*c)-d 第二步：把每个括号里的“运算符”移到括号右边 → a (b c *) + d - 第三步：去掉括号连起来 → a b c * + d -（直接出结果）
     2. 有括号场景（如 a+(b*c-(d/e))）： 第一步：从最内层括号开始，把运算符移到括号右边 → 内层 (d e /)，中层 (b c * d e / -) 第二步：去掉所有括号，按原顺序连 → a b c * d e / - +（心算时先拆内层，再拼外层）
   • 中缀转前缀
         示例（a+b*c-d）：        第一步：按优先级打隐形括号 → (a+(b*c))-d        第二步：把每个括号里的“运算符”移到括号左边 → - (+ a (* b c)) d        第三步：去掉括号连起来 → - + a * b c d（心算时先找最右边的运算符，再往左推）
   • 后缀转中缀
          示例（a b c * + d -）：        从左到右看，遇到第一个符号*，就把它前面两个数“抱起来” → (b*c)        接着遇到+，再抱前面两个（a和刚算的结果） → (a+(b*c))        最后遇到-，抱前面两个 → (a+(b*c))-d（直接出中缀，不用记顺序）
   • 前缀转中缀
          示例（- + a * b c d）：        从右到左看，遇到第一个符号*，抱后面两个 → (b*c)        遇到+，抱后面两个（a和刚算的结果） → (a+(b*c))        遇到-，抱后面两个 → (a+(b*c))-d（反向看，不会乱序）
10. 树论、图论常用公式

    类别	公式/性质描述	数学表达式/公式	说明
    树论	节点与边的关系	边数 = 节点数 - 1	n个节点的树必有n-1条边，反之亦然（连通图）
    	完全k叉树叶子节点与非叶子节点关系	$L = (k-1) \times N + 1$	L为叶子数，N为非叶子数
    	完全k叉树前h层最多节点数	$S(h) = \frac{k^h - 1}{k - 1}$	根节点为第1层，k≠1
    	k叉树最小高度（n个节点，根为第1层）	满足$\frac{k^h - 1}{k - 1} \geq n$的最小h	求最小h使前h层节点数≥n
    	二叉树第i层最多节点数	$2^{i-1}$	i≥1
    	高度为h的二叉树最多节点数	$2^h - 1$	满二叉树情况
    	二叉树叶子节点与度为2节点关系	$n_0 = n_2 + 1$	n₀为叶子数，n₂为度为2的节点数
    图论	无向完全图最大边数	$\frac{n(n-1)}{2}$	n为节点数
    	有向完全图最大边数	$n(n-1)$	n为节点数
    	无向图度数和公式	$\sum \text{度数} = 2E$	E为边数
    	有向图度数关系	$\sum \text{入度} = \sum \text{出度} = E$	E为边数
    	最小生成树边数	边数 = 节点数 - 1	与树的边数性质一致

11. 排列组合常用公式

    类型	公式名称	数学表达式	含义说明
    基础概念	阶乘	$n! = n \times (n-1) \times \dots \times 1$	正整数n的阶乘，表示1到n的所有整数乘积（规定0! = 1）
    排列	选排列（无重复）	$A_n^k = \frac{n!}{(n-k)!}$	从n个不同元素中选k个，按顺序排列的方案数（k ≤ n）
    	全排列	$A_n^n = n!$	从n个不同元素中选n个（全部），按顺序排列的方案数
    	可重复排列	$n^k$	从n个不同元素中选k个，允许重复选择，按顺序排列的方案数
    组合	无重复组合	$C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}$	从n个不同元素中选k个，不考虑顺序的方案数（k ≤ n）
    	组合数性质1（对称性）	$C_n^k = C_n^{n-k}$	从n个元素中选k个，与选n-k个的方案数相同
    	组合数性质2（递推式）	$C_n^k = C_{n-1}^k + C_{n-1}^{k-1}$	从n个元素中选k个，等于“不选第n个元素”加“选第n个元素”的方案数之和
    	可重复组合	$C_{n+k-1}^k$	从n个不同元素中选k个，允许重复选择，不考虑顺序的方案数
    其他	二项式定理	$(a+b)^n = \sum_{k=0}^n C_n^k a^{n-k} b^k$	二项式展开式，系数为组合数
    	组合数求和	$\sum_{k=0}^n C_n^k = 2^n$	n个元素的所有子集（包括空集）的总数

12. 哈夫曼树的合法性判断
    方法：
    • 频率最高的字符，编码必须最短。
    • 频率最低的 2 个字符（如本题 a=5%、b=9%），在哈夫曼树中必为 “兄弟节点”，编码仅最后 1 位不同，前几位完全相同（同前缀）。
    • 任意字符的编码，不能是另一个字符编码的前缀。
13. 有向无环图的有效的拓扑排序如何判断？
    所有前驱节点（有边指向当前节点的节点）都排在当前节点之前

• 根据题目中的 4 条边，先快速画出节点依赖（谁必须在谁前面）：
• 边 (1,2)、(1,3) → 1 必须在 2、3 之前（1 是 2、3 的前驱）
• 边 (2,4)、(3,4) → 2、3 必须在 4 之前（2、3 是 4 的前驱）
• 1 要先于 2、3；2、3 要先于 4（1 是 “源头”，4 是 “终点”）