Featured image of post CSP-S 0基础赛前闪击
计算机

CSP-S 0基础赛前闪击

感谢豆包独家赞助播出

废话不说了还有几天考试了我啥都不会

计算机基础知识

1. Linux 命令

Linux 是广泛应用于服务器、云计算等领域的操作系统，掌握其命令行操作至关重要。例如：

  • mkdir 目录名：创建目录，如 mkdir my_project，在当前路径下新建名为 my_project 的目录；

  • pwd：显示当前所在目录的完整路径，清晰知晓自己在文件系统中的位置；

  • ls：列出目录内容，常用参数：

    • ls -l：以详细列表形式展示文件 / 目录的权限、所有者、大小、修改时间等信息；
    • ls -a：显示包括隐藏文件（以 . 开头）在内的所有内容；

  • g++ 编译命令：编译 C++ 代码，如对 test.cpp 文件，执行 g++ test.cpp -o test 生成可执行文件 test，运行时输入 ./test 即可。

2. G++ 编译选项

-O2 是 g++ 的优化级别选项，使用该选项编译时，编译器会对生成的机器码进行优化（如减少执行时间、降低内存占用），不改变代码逻辑，通常用于发布版本的编译以提升程序性能。

数据结构

1. 线性表

（1）链表

是物理存储单元非连续、非顺序的存储结构，单链表的每个节点包含「数据域」和「指针域」，指针域指向下一个节点，通过指针串联所有节点，字符可视化如下：

1
2

[数据1|指针] → [数据2|指针] → [数据3|指针] → NULL
  节点1          节点2          节点3（尾节点）

  • 应用场景：如学生成绩管理系统，每个学生信息（成绩、姓名）作为数据域，指针连接不同节点，方便插入 / 删除操作；

  • 扩展：双向链表额外增加「指向前驱节点的指针」，支持双向遍历，适合频繁前后查找的场景。

（2）栈

遵循「后进先出（LIFO，Last In First Out）」规则的结构，仅允许在「栈顶」进行插入（压栈）和删除（弹栈）操作，字符可视化如下：

1
2
3
4
5
6
7

    栈顶
    ↓
[元素3]  # 最后入栈，最先出栈
[元素2]
[元素1]  # 最先入栈，最后出栈
    ↑
    栈底
  • 应用场景：函数调用栈（存储函数参数、局部变量）、括号匹配判断、表达式求值等。

（3）队列

遵循「先进先出（FIFO，First In First Out）」规则的结构，仅允许在「队尾入队」、「队首出队」，字符可视化如下：

1
2

队首 ← [元素1] → [元素2] → [元素3] ← 队尾
        出队（先入先出）          入队（后入后出）
  • 应用场景：广度优先搜索（BFS）中存储待访问节点、任务调度（如打印机排队）等。

2. 树

（1）二叉树

每个节点最多有两个子节点（左子节点、右子节点），字符可视化如下：

1
2
3
4
5

        根(1)
       /   \
    左子树(2) 右子树(3)
   /   \
(4)     (5)  # 叶子节点（无子女）

  • 核心遍历方式（必考）：

    • 前序遍历：根 → 左 → 右，示例顺序：1 → 2 → 4 → 5 → 3；
    • 中序遍历：左 → 根 → 右，示例顺序：4 → 2 → 5 → 1 → 3；
    • 后序遍历：左 → 右 → 根，示例顺序：4 → 5 → 2 → 3 → 1；

  • 应用：对存储整数的二叉排序树进行中序遍历，可得到从小到大的有序序列。

（2）完全二叉树

  • 特点：除最后一层外，每一层节点数均为最大值；最后一层节点「从左到右连续排列」，无空缺，字符可视化如下：
1
2
3
4
5

        1
       /   \
      2     3
     / \   /
    4   5 6  # 最后一层无7，左起连续
  • 应用：堆排序（用数组存储，无需指针，节省空间）。

（3）满二叉树

  • 特点：每一层节点数均为「2^(层数 - 1)」，所有叶子节点在同一深度，无空缺，字符可视化如下：
1
2
3
4
5

        1
       /   \
      2     3
     / \   / \
    4   5 6   7  # 叶子全在第3层，无空缺

（4）哈夫曼树

  • 定义：带权路径长度最短的二叉树（权值通常为字符出现频率）；

  • 应用：数据压缩，对频率高的字符赋予短编码，频率低的赋予长编码，减少总存储量。

（5）二叉排序树（BST）

  • 规则：左子树所有节点值 <根节点值；右子树所有节点值> 根节点值，左右子树也为二叉排序树，字符可视化如下：
1
2
3
4
5

        5（根）
       /   \
      3     7  # 3 < 5 < 7
     / \   / \
    2   4 6   8  # 2 < 3 < 4，6 < 7 < 8
  • 优势：查找效率高，平均时间复杂度为 O (log n)，如存储单词的查找场景。

3. 图

（1）定义和概念

图由「顶点（节点）」和「边」组成，边用于连接顶点，分为两类：

  • 有向图：边带方向（箭头表示），字符可视化如下：
1
2
3

1 → 2 → 3
↑     ↗
4 ← 5

应用：社交网络的「关注关系」（A 关注 B ≠ B 关注 A）；

  • 无向图：边无方向（线段表示），字符可视化如下：
1
2
3

1 --- 2 --- 3
|     |
4 --- 5

应用：城市道路（A 到 B 与 B 到 A 路线相同）；

  • 连通图：无向图中任意两个顶点之间都存在路径相通。

（2）存储方式（必考）

存储方式 原理 适用场景
邻接矩阵 用二维数组 A[i][j] 表示顶点关系：- 有边：A[i][j] = 权值（或 1）- 无边：A[i][j] = 0（或无穷大） 稠密图（边数多，如 n² 级别）
邻接表 为每个顶点建链表，存储「相邻顶点 + 边权」，以上述无向图为例：- 1: 2 → 4- 2: 1 → 3 → 4 → 5- 3: 2- 4: 1 → 2 → 5- 5: 2 → 4 稀疏图（边数少，如 n 级别）

算法

1. 排序算法（必考，需记时间复杂度）

（1）冒泡排序

  • 核心思想：相邻元素两两比较，顺序错误则交换，每趟将最大（或最小）元素「浮到末尾」；

  • 时间复杂度：O (n²)；

  • 示例（升序排序 [3, 1, 4, 1, 5, 9]）：

第一趟：3 和 1 交换→[1,3,4,1,5,9] → 4 和 1 交换→[1,3,1,4,5,9]，最终第一趟结果 [1,3,1,4,5,9]，重复至有序。

（2）简单选择排序

  • 核心思想：每趟从待排序元素中选最小（或最大）元素，放到已排序区末尾；

  • 时间复杂度：O (n²)；

  • 示例（升序排序 [5, 3, 8, 4, 2]）：

第一趟选 2 放首位→[2,3,8,4,5] → 第二趟选 3（已在正确位置）→ 第三趟选 4 放第三位→[2,3,4,8,5]，直至有序。

（3）插入排序

  • 核心思想：将元素插入已排序区的正确位置（类似整理扑克牌）；

  • 时间复杂度：O (n²)；

  • 示例（升序排序 [4, 3, 2, 1]）：

3 插入[4]→[3,4] → 2 插入[3,4]→[2,3,4] → 1 插入[2,3,4]→[1,2,3,4]。

（4）归并排序

  • 核心思想：分治（拆分数组→子数组排序→合并有序子数组）；

  • 时间复杂度：O (n log n)；

  • 示例（排序 [5,2,4,7,1,3,2,6]）：

拆分：[5,2,4,7]和[1,3,2,6]→[5,2]/[4,7]/[1,3]/[2,6]→单个元素；

合并：[2,5]+[4,7]→[2,4,5,7]，[1,3]+[2,6]→[1,2,3,6]→最终[1,2,2,3,4,5,6,7]。

（5）快速排序

  • 核心思想：分治（选基准→小元素放左、大元素放右→递归排序）；

  • 时间复杂度：平均 O (n log n)，最坏 O (n²)（数组已有序时）；

  • 示例（排序 [3,1,4,1,5,9]）：

选 3 为基准→左[1,1]、右[4,5,9]→分别递归排序，最终有序。

（6）快速排序：也是分治算法，先从数列中挑出一个元素作为基准值，将比它小的元素放在左边，比它大的元素放在右边，然后对左右两个子数列分别进行快速排序，平均时间复杂度为 O (n log n) ，但在最坏情况下（如数组已经有序）时间复杂度会退化为 O (n²) 。例如对数组[3, 1, 4, 1, 5, 9]，选 3 作为基准，小于 3 的放左边→[1,1]，大于 3 的放右边→[4,5,9]；再对[1,1]（选 1 为基准，左右无元素）和[4,5,9]（选 4 为基准，小于 4 的无，大于 4 的→[5,9]）分别排序，最终得到有序数组。

2. 图论算法（必考）

（1）DFS（深度优先遍历）

  • 核心逻辑：从起点出发，优先深入探索路径，无法前进时回溯，直至遍历所有顶点；

  • 示例（无向图，起点 1）：

图结构：

1
2
3

1 --- 2 --- 3
|     |
4 --- 5

遍历顺序（有效）：1→2→3→5→4（访问过的顶点标记，避免重复）；

  • 应用：迷宫路径探索、连通性判断。

（2）BFS（广度优先遍历）

  • 核心逻辑：从起点出发，先访问所有邻接顶点，再逐层访问邻接顶点的邻接顶点（类似水波扩散）；

  • 示例（同上无向图，起点 1）：

遍历顺序：1→2→4→3→5；

  • 应用：最短路径（无权图）、层序遍历。

（3）Dijkstra 算法

  • 功能：求图中「单源最短路径」（从一个起点到所有其他顶点的最短路径）；

  • 示例（带权有向图，起点 1）：

图结构：

1
2
3
4
5

1 → 2 (权2)
|     ↓
(权1) 4
|     ↑
3 → 2 (权3)

步骤：

    1. 初始距离：1→1=0，其他为无穷大；
    1. 访问 1 的邻接顶点 2（距离 2）、3（距离 1），标记 1 为已确定；
    1. 选距离最小的 3（距离 1），更新其邻接顶点 2（原距离 2>1+3=4，不更新），标记 3；
    1. 选距离最小的 2（距离 2），更新其邻接顶点 4（距离 2+1=3），标记 2；
    1. 最终最短距离：1→1=0，1→2=2，1→3=1，1→4=3。

（4）Prim 算法（最小生成树）

  • 功能：在连通无向图中，找到「总权值最小的边集合」，连接所有顶点（无环）；

  • 逻辑：从起点开始，每次选「与当前生成树相连的最小权边」，加入顶点，直至所有顶点加入；

  • 示例（无向图：顶点 1-5，边权 1-2=2、1-4=1、2-3=3、2-4=2、2-5=4、4-5=3）：

步骤：1→加 4（权 1）→加 2（权 2）→加 3（权 3）→加 5（权 3），总权 1+2+3+3=9。

（5）Kruskal 算法（最小生成树）

  • 逻辑：所有边按权值从小到大排序，依次选边，若不构成环则加入，直至连接所有顶点；

  • 示例（同上无向图）：

边排序：1-4 (1)、1-2 (2)、2-4 (2)、4-5 (3)、2-3 (3)、2-5 (4)；

选边：1-4（无环）→1-2（无环）→2-4（环，跳过）→4-5（无环）→2-3（无环），总权同 Prim。

（6）拓扑排序

  • 功能：对「有向无环图（DAG）」排序，使所有边 (u, v) 满足 u 在 v 之前；

  • 示例（课程依赖图：数学→物理、数学→化学、物理→生物、化学→生物）：

图结构：

1
2
3

数学 → 物理 → 生物
      ↓
    化学 → 生物

可能排序：数学→物理→化学→生物 或 数学→化学→物理→生物比如在安排课程学习顺序时，课程之间有先修关系，利用拓扑排序可以得到一个合理的课程学习顺序，避免出现 “先学后续课程、再学先修课程” 的逻辑矛盾。

3. 动态规划

  • 基本思路：将一个复杂问题分解为一系列相互关联的子问题，通过求解子问题并保存子问题的解（通常用数组或表格存储，称为 “状态数组”），避免重复计算，从而高效地解决原问题。核心是找到 “状态定义” 和 “状态转移方程”—— 前者明确子问题的含义，后者明确如何从子问题的解推出原问题的解。

  • 背包问题：最经典的动态规划场景之一，分为 0-1 背包（每个物品只能选或不选）、完全背包（每个物品可选多次）等。以 0-1 背包为例：假设有一个容量为W=5的背包，3 个物品的重量和价值分别为w=[2,3,4]、v=[3,4,5]，求能放入背包的最大价值。

    • 状态定义：dp[i][j]表示 “前i个物品放入容量为j的背包的最大价值”。
    • 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（若j >= w[i]，则选 “不装第i个物品” 或 “装第i个物品” 的最大值；若j < w[i]，则只能不装，dp[i][j] = dp[i-1][j]）。
    • 最终通过填充dp表格，得到dp[3][5] = 7（选重量 2 和 3 的物品，价值 3+4=7）。

  • 区间 DP：针对 “区间类问题”（如字符串、数组的区间操作）的动态规划，状态通常定义为 “区间[l, r]的最优解”，通过枚举区间长度和分割点来推导。例如 “石子合并问题”：有n堆石子排成一排，每次合并相邻两堆，合并成本为两堆石子数量之和，求合并成一堆的最小成本。

    • 状态定义：dp[l][r]表示 “合并第l到第r堆石子的最小成本”。
    • 状态转移方程：dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum(lr))（k为l到r-1之间的分割点，sum(lr)为区间[l,r]的石子总数，需提前预处理前缀和数组）。

4. 贪心算法

  • 概念：在对问题求解时，不考虑整体最优，而是每次做出在当前看来是 “局部最优” 的选择，试图通过一系列局部最优解堆叠出全局最优解。核心是 “贪心策略的正确性”—— 必须证明当前的局部最优选择能导向全局最优，否则可能得到错误结果。

    • 示例：购物找零问题（假设币种为 1 元、5 元、10 元、20 元），要找零 37 元，贪心策略为 “优先选最大面额”：20 元→10 元→5 元→1 元 ×2，共 4 张纸币，这是最优解。

  • 应用场景：仅适用于 “贪心选择性质” 和 “最优子结构” 的问题：

    • 任务调度：有多个任务，每个任务有 “开始时间、结束时间、收益”，选择不重叠的任务使总收益最大，贪心策略为 “优先选结束时间最早的任务”。
    • 霍夫曼编码：构建哈夫曼树时，每次选两个权值最小的节点合并，这是贪心策略的典型应用，能保证最终编码的总长度最短。

  • 注意事项：贪心算法并非万能，若问题不满足 “贪心选择性质”，则无法得到全局最优。例如特殊币种找零（币种为 1 元、3 元、4 元，找零 6 元）：贪心策略选 4 元 + 1 元 ×2（共 3 张），但最优解是 3 元 ×2（共 2 张），此时贪心失效。

数学知识

1. 初等数论

  • 整除：若整数a除以非零整数b，商为整数且余数为 0，则称a能被b整除，记作b | a（读作 “b整除a”）。例如6 ÷ 3 = 2，余数为 0，即3 | 6；7 ÷ 3 = 2余 1，则3不能整除7，记作3 ∤ 7。

  • 因数、倍数：若b | a，则b是a的 “因数”（或 “约数”），a是b的 “倍数”。例如3 | 6，则 3 是 6 的因数，6 是 3 的倍数；6 的所有因数为 1、2、3、6，6 的倍数有 6、12、18、…。

  • 质数、合数：

    • 质数（素数）：大于 1 的自然数，除了 1 和自身外，无法被其他自然数整除的数，例如 2、3、5、7、11 等（注意：2 是唯一的偶质数）。
    • 合数：大于 1 的自然数，除了 1 和自身外，还能被其他自然数整除的数，例如 4（2×2）、6（2×3）、8（2×4）、9（3×3）等。
    • 1 既不是质数也不是合数。

  • 同余：给定正整数m，若两个整数a和b满足(a - b)能被m整除，则称a与b对模m同余，记作a ≡ b (mod m)。例如17 - 5 = 12，12 能被 6 整除，即17 ≡ 5 (mod 6)；常见应用：判断奇偶数（a ≡ 0 mod 2为偶数，a ≡ 1 mod 2为奇数）。

  • 欧几里德算法（辗转相除法）：用于计算两个非负整数a、b的最大公约数（GCD，Greatest Common Divisor），核心原理是 “gcd(a, b) = gcd(b, a mod b)”，直到b = 0，此时a即为最大公约数。

    • 示例：求gcd(24, 18)：
      1. 24 mod 18 = 6 → gcd(18, 6)
      1. 18 mod 6 = 0 → 此时b=0，a=6，即gcd(24,18)=6。

2. 组合数学

  • 加法原理：若完成一件事有n类 “互斥” 的办法（即选一类办法就不能选其他类），第i类办法有m_i种方法，则完成这件事的总方法数为N = m_1 + m_2 + … + m_n。

    • 示例：从甲地到乙地，有 3 趟火车（办法 1）、2 趟汽车（办法 2）、4 趟飞机（办法 3），三类方式互斥，总出行方式为3 + 2 + 4 = 9种。

  • 乘法原理：若完成一件事需要n个 “先后衔接” 的步骤（即必须完成所有步骤才能完成此事），第i步有m_i种方法，则总方法数为N = m_1 × m_2 × … × m_n。

    • 示例：从 A 到 B 有 2 条路，从 B 到 C 有 3 条路，从 A 到 C 必须经过 B，总路线数为2 × 3 = 6种（每条 A→B 的路对应 3 条 B→C 的路）。

  • 排列：从n个不同元素中取出m个元素（m ≤ n），按 “顺序” 排成一列，所有不同排列的个数称为排列数，记作A(n, m)（或P(n, m)），计算公式为：

A(n, m) = n! / (n - m)!（n!表示n的阶乘，即n! = n × (n-1) × … × 1，规定0! = 1）。

    • 示例：从 5 人中选 3 人排队，排列数A(5,3) = 5! / (5-3)! = 5×4×3 = 60种（第 1 个位置有 5 种选法，第 2 个位置有 4 种，第 3 个位置有 3 种，共 5×4×3=60）。

  • 组合：从n个不同元素中取出m个元素（m ≤ n），不考虑顺序组成一组，所有不同组合的个数称为组合数，记作C(n, m)（或C(n, m)），计算公式为：

C(n, m) = n! / [m! × (n - m)!]（组合数性质：C(n, m) = C(n, n - m)，例如C(5,3)=C(5,2)=10）。

    • 示例：从 5 个水果中选 3 个，组合数C(5,3) = 5! / (3!×2!) = (5×4×3)/(3×2×1) = 10种（不考虑选的顺序，只看选的是哪 3 个）。

时间复杂度

1. 分析方法

时间复杂度用于描述 “算法执行时间随输入规模n增长的趋势”，不计算具体执行时间，而是关注 “基本操作的执行次数与n的关系”。分析时需忽略常数项、低次项和系数，只保留最高次项。

  • 示例 1：单循环（for(int i=0; i<n; i++) { … }）：循环执行n次，基本操作执行n次，时间复杂度为O(n)。

  • 示例 2：嵌套循环（for(int i=0; i<n; i++) for(int j=0; j<n; j++) { … }）：外层循环n次，内层循环每次n次，总执行n×n = n²次，时间复杂度为O(n²)。

  • 示例 3：二分查找（while(l <= r) { mid = (l + r)/2; … }）：每次循环将区间缩小一半，最多执行log₂n次，时间复杂度为O(log n)。

2. 常见时间复杂度（按增长速度排序）

  • O(1)：常数时间，算法执行时间与n无关，例如访问数组中某个固定下标元素（a[5]）、两数相加（x + y）。

  • O(log n)：对数时间，增长极慢，常见于 “二分” 类操作（二分查找、快速幂、归并排序的分治步骤）。

  • O(n)：线性时间，执行时间与n成正比，例如遍历数组、单循环操作。

  • O(n log n)：线性对数时间，常见于高效排序算法（归并排序、快速排序、堆排序），是大规模数据排序的常用复杂度。

  • O(n²)：平方时间，常见于简单排序算法（冒泡、选择、插入排序），n较大时（如n>1e4）效率较低。

  • O(2ⁿ)：指数时间，增长极快，仅适用于n很小的场景（如递归求解斐波那契数列的暴力算法），通常需优化。