CodeTour

基于 洛谷 的个人算法与数据结构学习记录。

系统整理算法与数据结构题目的实现、复盘和专题笔记。代码以 Python 为主，部分题目提供 C++ 对照版本。

目录结构

算法/
├─ 动态规划/
│  ├─ 背包/          # 01 背包、完全背包、多重背包、前 K 优解等
│  ├─ 区间/          # 区间 DP
│  ├─ 线性/          # 线性 DP
│  ├─ 树形/          # 树形 DP 预留专题
│  └─ 状压/          # 状态压缩 DP 预留专题
├─ 线性数据结构/
│  ├─ 栈/            # 栈、单调栈
│  └─ 队列/          # 队列、双端队列、单调队列
├─ 非线性数据结构/
│  ├─ 堆/            # 堆与优先队列
│  ├─ 并查集/        # 集合合并与连通性查询
│  ├─ 树/            # 二叉树、LCA、树遍历、哈夫曼树
│  ├─ 字典树/        # Trie
│  └─ 区间数据结构/  # 树状数组、线段树、ST 表
├─ 图论/             # 拓扑排序、最短路、负环、强连通分量、欧拉路径、最小生成树、Floyd、LCA
├─ 搜索/             # DFS、BFS、回溯、剪枝、状压搜索
├─ 字符串/           # KMP、Manacher、AC 自动机
├─ 数学/             # 数论、快速幂、筛法、矩阵、线性代数、高斯消元等
└─ 哈希/             # 字符串哈希、数值哈希、计数与查找

当前进度

截至 2026 年 8 月 25 日，仓库共有 111 个代码文件：

• Python：95 个
• C++：16 个
• 专题总结：7 份

分类	代码数量	主要覆盖内容
动态规划	28	背包、线性 DP、区间 DP
非线性数据结构	19	堆、并查集、树、Trie、树状数组、线段树、ST 表
数学	19	数论、筛法、快速幂、矩阵、线性方程组、行列式、矩阵求逆
搜索	13	DFS、BFS、组合、排列、数独、剪枝、状压搜索
哈希	10	字符串哈希、数值哈希、计数
线性数据结构	8	栈、单调栈、队列、双端队列、单调队列
字符串	5	KMP、Manacher、AC 自动机
图论	9	拓扑排序、Floyd、Dijkstra、负环、强连通分量、欧拉路径、最小生成树
合计	111

注：同一道题的不同实现会分别保留，例如带有 _ez 后缀的版本；代码数量不等于不同题目的数量。

代表性题目

动态规划

• P1048：01 背包
• P1077：组合计数与背包
• P1757：混合背包
• P1833：混合背包与时间规划
• P1775、P2858、P4170：区间 DP
• B3637、P1095、P1115、P1216：线性 DP
• P1858：前 K 优解背包

搜索与回溯

• B3625_1、B3625_2：迷宫 BFS 与 DFS
• P1162、P1443：Flood Fill 与网格最短路
• P1036：组合搜索与记忆化搜索
• P1157、P1706：组合与全排列
• P1219：八皇后与对角线剪枝
• P1731：多参数搜索、可行性剪枝、最优性剪枝
• P1784：数独、位掩码、MRV 剪枝
• P2392：二叉决策 DFS 与子集划分
• P1433：状态压缩搜索与记忆化 DP

图论

• B3644：拓扑排序
• B3647：Floyd 全源最短路
• P3371：Dijkstra 单源最短路
• P3366：Kruskal、并查集与最小生成树
• P3379：倍增 LCA
• P3385：SPFA、松弛与可达负环判断
• B3609：Tarjan 强连通分量
• P7771：Hierholzer 欧拉路径与字典序

非线性与区间数据结构

• P3378：堆与优先队列
• P3367：并查集
• P1305、B3642、P4913：二叉树建立、遍历与深度
• B2168：哈夫曼树与哈夫曼编码
• P8306：Trie 前缀统计
• P3374、P3368：树状数组
• P3372、P3373：线段树与懒标记
• P3865：ST 表与 RMQ

字符串

• P3375：KMP
• P3805：Manacher
• P3808：AC 自动机

数学与哈希

• P1075、P1029：因数、质因数、最大公约数与最小公倍数
• P1226：快速幂与二进制分解
• P3383、P3811、P1082：线性筛、乘法逆元、扩展欧几里得与同余方程
• P3389：高斯消元求解线性方程组
• P7112：任意模数下的行列式求值
• P3390、P1939：矩阵快速幂与递推数列
• P4783：费马小定理、模逆元与矩阵求逆
• 哈希目录包含字符串哈希、数值哈希、重复结构查找和计数类题目。

近期学习重点

最近的学习重点从基础图论和数论，延伸到了图论综合模板与线性代数算法：

• 图论：负环、强连通分量、欧拉路径。
• 数学：带余除法、扩展欧几里得、同余方程、模逆元。
• 线性代数：高斯消元、行列式、矩阵求逆、矩阵快速幂。
• 递推加速：将线性递推转化为状态转移矩阵，再用矩阵快速幂降低复杂度。

每道题除了保留可提交代码，也尽量在文件底部补充：

• 数学定义和理论依据；
• 状态、转移和边界；
• 关键代码的逐步解释；
• 正确性直觉；
• 时间复杂度和空间复杂度。

学习路线

当前的学习顺序大致为：

线性数据结构
    ↓
树、堆、并查集、Trie
    ↓
树状数组、线段树、ST 表
    ↓
DFS、BFS、回溯与剪枝
    ↓
动态规划
    ↓
图论与字符串算法
    ↓
数学算法与线性代数
    ↓
哈希与更复杂的综合题

搜索专题中的基本范式：

组合：start
排列：used
网格搜索：visited
约束搜索：候选集合 + 剪枝
状压搜索：mask

动态规划专题重点记录：

状态定义
状态转移
初始化
遍历顺序
空间优化
复杂度分析

文件规范

• 解题代码使用 Python 3 编写，文件名以题号为主，例如 P1048.py、B2173.py。
• C++ 对照实现使用 .cpp 后缀。
• 同题的补充实现通过简短后缀区分，例如 P1077_ez.py。
• 专题知识整理统一命名为 总结.md。
• 代码尽量保留状态定义、转移过程、边界处理和复杂度说明。
• 代码注释以帮助理解算法为主，避免与语句含义重复的空泛注释。

本地运行

克隆仓库：

git clone https://github.com/sinxy-sai/CodeTour.git
cd CodeTour

运行 Python 题目：

python "搜索/P1784.py"

运行 C++ 题目：

g++ -std=c++17 -O2 "非线性数据结构/区间数据结构/P3372.cpp" -o main
./main

Windows PowerShell 下可以使用：

g++ -std=c++17 -O2 "非线性数据结构/区间数据结构/P3372.cpp" -o main.exe
.\main.exe

程序按照洛谷题目的标准输入格式读取数据，并将答案输出到标准输出。题目要求、输入格式和样例请以洛谷对应题目页面为准。

代码说明

本仓库以“理解算法模型”为主要目标：

1. 先独立分析题目和数据范围。
2. 明确状态、选择、转移和终止条件。
3. 编写 Python 版本并通过样例与评测。
4. 对容易混淆的代码补充中文注释。
5. 对性能敏感的题目记录 TLE、MLE、RE 等问题。
6. 必要时使用 C++ 对照实现，理解语言性能差异。

部分题目存在多种实现，例如：

• 递归与非递归；
• 普通写法与 _ez 简化写法；
• Python 与 C++；
• 暴力搜索与剪枝搜索。

这些版本会根据学习过程同时保留，便于比较不同算法和实现方式。

使用说明

仓库内容是个人学习过程的记录，解法不一定是唯一或最优实现。建议先独立思考，再将代码作为思路参考；不同语言版本、Python 版本和评测环境可能影响运行结果。

License

本项目基于 MIT License 开源。