路径D-DSA算法刷题

路径 D — 竞赛策略完全路线图

本路线图从零搭建算法竞赛的知识体系，覆盖数据结构和算法两大核心，同时包含字符串算法、数论基础、搜索进阶、DP 优化、计算几何、竞赛实务等模块。
路线图分为 12 个 Phase，建议按顺序推进。Phase 1-5 为必做核心，Phase 6-12 按需选学。

每条内容均会标注来源：(RootStack) 指本教程原有关联文件，(OI-wiki) 指经本地化改造后从 OI-wiki 移植的内容。

推荐阅读顺序：字符串 → 数论 → 搜索进阶 → DP优化 → 杂项技巧 → 计算几何 → 竞赛实务

---

学习方式: 四步法

1. 通读概念 — 理解数据结构的定义、性质、适用场景
2. 手写实现 — 不看参考代码，用 C++ 手动实现核心操作
3. STL 练习 — 用标准库容器/算法做题，熟悉接口
4. 洛谷刷题 — 按章节做推荐题目，每章 2-5 题

每章 1000+ 行，建议分 2-3 天完成。一天学概念+手写，一天 STL+案例，一天课后题+刷题。

---

Phase 1 — 入门基础：线形结构与排序 (建议 14 天)

Step 1: A 容器 Container (2 天)

重点: vector 扩容机制、迭代器原理、连续存储 vs 节点存储
必须手写: SimpleVector
配合算法: 数组基础 / 循环 / 分支

平台	题目编号	题目名	说明
洛谷	P1047	校门外的树	数组模拟
LeetCode	27	Remove Element	数组原地操作

---

Step 2: D 链表 LinkedList (2 天)

重点: 单向/双向链表全操作、STL list/forward_list
必须手写: 单向链表 (push/pop/reverse)、双向链表
配合算法: 双指针 (只读快慢指针部分)

平台	题目编号	题目名	说明
洛谷	P1996	约瑟夫问题	链表经典
LeetCode	206	Reverse Linked List	反转链表
LeetCode	141	Linked List Cycle	快慢指针判环

---

Step 3: B 栈 Stack (2 天)

重点: 数组栈/链表栈实现、函数调用栈原理、表达式求值
必须手写: ArrayStack、LinkedStack、MinStack

平台	题目编号	题目名	说明
洛谷	P1449	后缀表达式	栈经典应用
洛谷	P1739	表达式括号匹配	括号匹配
LeetCode	20	Valid Parentheses	括号匹配
LeetCode	155	Min Stack	最小栈

---

Step 4: F 队列 Queue (2 天)

重点: 循环队列实现、STL queue/deque 用法、BFS 队列
必须手写: ArrayQueue (循环队列)、LinkedQueue
配合算法: 搜索 (BFS 部分)

平台	题目编号	题目名	说明
洛谷	P1540	机器翻译	队列模拟
洛谷	P1996	约瑟夫问题	队列版
LeetCode	225	Implement Stack using Queues	队列变体

---

Step 5: Q 八大排序 Sorting (3 天)

学习顺序: 冒泡 → 选择 → 插入 → 希尔 → 归并 → 快速 → (堆排序待学完堆后回看) → 基数
必须手写: 冒泡、插入、归并、快排
配合算法: 递推递归 / 暴力枚举 / 排序应用

平台	题目编号	题目名	说明
洛谷	P1177	快速排序	排序模板题
洛谷	P1059	明明的随机数	去重+排序
洛谷	P1093	奖学金	多关键字排序
LeetCode	912	Sort an Array	排序综合
LeetCode	215	Kth Largest Element	快选/堆排

---

Step 6: 二分查找 (1 天)

重点: lower_bound/upper_bound 手写、二分查找变体
前置: 排序必须已完成

平台	题目编号	题目名	说明
洛谷	P2249	查找	二分查找模板
洛谷	P1102	A-B 数对	二分+计数
洛谷	P1678	烦恼的高考志愿	二分查找应用
LeetCode	704	Binary Search	基础二分
LeetCode	34	Find First and Last Position	二分变体

---

Phase 2 — 核心数据结构 (建议 14 天)

Step 7: G 哈希表 HashTable (2 天)

重点: 链地址法/开放地址法、STL unordered_map/unordered_set
必须手写: 基于链地址法的 HashMap (put/get/remove)
配合算法: 下标技巧

平台	题目编号	题目名	说明
洛谷	P3405	Cities and States	hash + map 计数
LeetCode	1	Two Sum	哈希表经典
LeetCode	387	First Unique Character	字符计数

---

Step 8: AVL (3 天)

重点: 四种遍历 (递归+迭代)、BST 增删查、AVL 四种旋转
必须手写: BST (insert/search/delete)
配合算法: 搜索 / 递推递归

平台	题目编号	题目名	说明
洛谷	P3369	普通平衡树	BST/AVL 综合
洛谷	P1364	医院设置	树的重心
LeetCode	94	Binary Tree Inorder Traversal	中序遍历
LeetCode	98	Validate Binary Search Tree	BST 判定
LeetCode	104	Maximum Depth of Binary Tree	树高

---

Step 9: C 堆 Heap (2 天)

重点: siftUp/siftDown、建堆 O(n)、STL priority_queue
必须手写: MaxHeap (insert/extractMax/heapify)
配合算法: 贪心 (优先队列应用) — 需要树的二叉树概念作为前置
回顾: 堆排序部分

平台	题目编号	题目名	说明
洛谷	P1090	合并果子	贪心+优先队列
洛谷	P1168	中位数	对顶堆
LeetCode	215	Kth Largest Element	堆解法
LeetCode	347	Top K Frequent Elements	堆+哈希

---

Step 10: J 字典树 Trie (1 天)

重点: Trie 节点结构、插入/查找/前缀匹配
配合算法: 字符串

平台	题目编号	题目名	说明
洛谷	P2580	于是他错误的点名开始了	Trie 模板
LeetCode	208	Implement Trie	Trie 实现
LeetCode	14	Longest Common Prefix	前缀匹配

---

Phase 3 — 算法专题深化 (建议 14 天)

Step 11: 二分答案 (2 天)

前置: 二分查找

平台	题目编号	题目名	说明
洛谷	P1182	数列分段	最小化最大值
洛谷	P2678	跳石头	最大化最小值
洛谷	P3853	路标设置	二分答案
LeetCode	875	Koko Eating Bananas	二分答案

---

Step 12: 前缀和 + 差分 (2 天)

重点: O(1) 区间求和、O(1) 区间修改

平台	题目编号	题目名	说明
洛谷	P8218	求区间和	前缀和模板
洛谷	P3131	被7整除的子序列	前缀和+数学
洛谷	P3397	地毯	二维差分模板
洛谷	P4552	IncDec Sequence	差分
LeetCode	303	Range Sum Query	前缀和
LeetCode	560	Subarray Sum Equals K	前缀和+哈希

---

Step 13: 贪心 (2 天)

重点: 局部最优 -> 全局最优思想、交换论证法证明
前置: 堆 / 排序

平台	题目编号	题目名	说明
洛谷	P1223	排队接水	简单贪心
洛谷	P1090	合并果子	贪心+优先队列
洛谷	P2240	部分背包问题	贪心 vs DP
洛谷	P1106	删数问题	贪心
LeetCode	455	Assign Cookies	简单贪心
LeetCode	55	Jump Game	贪心

---

Step 14: 滑动窗口 + 双指针 (2 天)

前置: 队列 / 前缀和

平台	题目编号	题目名	说明
洛谷	P1886	滑动窗口	单调队列模板
洛谷	P1638	逛画展	不定长滑动窗口
洛谷	P1102	A-B 数对	双指针
洛谷	P1147	连续自然数和	双指针
LeetCode	3	Longest Substring Without Repeating	滑动窗口
LeetCode	209	Minimum Size Subarray Sum	滑动窗口
LeetCode	11	Container With Most Water	双指针

---

Step 15: 递推与递归 (2 天)

重点: 递推 vs 递归、记忆化搜索、斐波那契/卡特兰数
前置: 栈 (递归=系统栈) / 排序

平台	题目编号	题目名	说明
洛谷	P1028	数的计算	递推
洛谷	P1255	数楼梯	斐波那契/高精度
洛谷	P1044	栈	卡特兰数
洛谷	P1164	小A点菜	01背包方案数
LeetCode	509	Fibonacci Number	递推递归
LeetCode	70	Climbing Stairs	简单递推

---

Step 16: BFS (2 天)

重点: DFS 回溯框架、BFS 层序遍历框架、状态恢复
前置: 栈 / 队列 / 树

平台	题目编号	题目名	说明
洛谷	P1605	迷宫	DFS 模板
洛谷	P1443	马的遍历	BFS 模板
洛谷	P2404	自然数拆分	回溯 DFS
LeetCode	200	Number of Islands	DFS/BFS
LeetCode	46	Permutations	回溯

POJ 经典搜索题: POJ 2386 Lake Counting, POJ 1979 Red and Black
HDU 搜索训练: HDU 1010 Tempter of the Bone, HDU 1043 Eight
Codeforces 搜索 tag → 按 rating 1500+ 筛选

---

Step 17: 动态规划 (3-4 天)

重点: 状态定义、状态转移方程、记忆化搜索 vs 递推、0/1背包、完全背包、LIS、LCS
前置: 递推递归 / 容器

平台	题目编号	题目名	说明
洛谷	P1048	采药	0/1 背包模板
洛谷	P1049	装箱问题	0/1 背包
洛谷	P1115	最大子段和	线性 DP
洛谷	P1616	疯狂的采药	完全背包
洛谷	P1439	LCS	最长公共子序列
LeetCode	416	Partition Equal Subset Sum	0/1 背包
LeetCode	322	Coin Change	完全背包
LeetCode	300	Longest Increasing Subsequence	LIS
LeetCode	1143	Longest Common Subsequence	LCS
LeetCode	53	Maximum Subarray	最大子数组
LeetCode	198	House Robber	线性 DP

POJ DP 经典: POJ 1163 The Triangle, POJ 1458 Common Subsequence, POJ 3624 Charm Bracelet
HDU DP 训练: HDU 2084 数塔, HDU 1176 免费馅饼, HDU 1114 Piggy-Bank
Codeforces DP tag → 按 rating 1400+ 筛选

---

Phase 4 — 图论 (建议 10 天)

Step 18: H 图 Graph (3 天)

重点: 邻接矩阵/邻接表存储、DFS/BFS 遍历、Dijkstra
配合算法: 图论算法

平台	题目编号	题目名	说明
洛谷	P3371	单源最短路径	Dijkstra (弱化版)
洛谷	P4779	堆优化 Dijkstra	Dijkstra 模板
洛谷	P3366	最小生成树	Prim/Kruskal
LeetCode	743	Network Delay Time	Dijkstra
LeetCode	207	Course Schedule	拓扑排序

---

Step 19: K 并查集 UnionFind (2 天)

重点: 路径压缩 + 按秩合并、Kruskal 算法、连通分量
配合算法: 连通性

平台	题目编号	题目名	说明
洛谷	P3367	并查集	模板题
洛谷	P1551	亲戚	并查集应用
LeetCode	547	Number of Provinces	并查集
LeetCode	684	Redundant Connection	并查集判环

---

Step 20: P 图高级算法 (3 天)

重点: 拓扑排序、Floyd、Bellman-Ford 判负环、网络流入门

平台	题目编号	题目名	说明
洛谷	P1113	杂务	拓扑排序
洛谷	P3385	负环	Bellman-Ford / SPFA
LeetCode	210	Course Schedule II	拓扑排序
LeetCode	787	Cheapest Flights	Bellman-Ford / DP

POJ 图论经典: POJ 2387 Til the Cows Come Home, POJ 1258 Agri-Net, POJ 1860 Currency Exchange
HDU 图论训练: HDU 2544 最短路, HDU 1874 畅通工程续, HDU 1875 畅通工程再续
Codeforces 图论 tag → 按 rating 1500+ 筛选

---

Phase 5 — 进阶数据结构 (选学)

Step 21: L 线段树 SegmentTree

前置: 数组 + 递归
配合算法: 优化

平台	题目编号	题目名	说明
洛谷	P3372	线段树 1	区间加+区间和
洛谷	P3373	线段树 2	区间加+区间乘
LeetCode	307	Range Sum Query - Mutable	线段树/树状数组

---

Step 22: M 树状数组 BIT

重点: lowbit、单点更新+前缀和查询（比线段树更轻量）

平台	题目编号	题目名	说明
洛谷	P3374	树状数组 1	单点加+区间和
洛谷	P3368	树状数组 2	区间加+单点查
LeetCode	307	Range Sum Query - Mutable	BIT 写法

---

Step 23: E 红黑树 RedBlackTree

前置: BST / AVL
(主要理解原理，不要求手写——STL map/set 的底层实现即为红黑树)

---

Step 24: O B树 B-Tree

前置: 树 + 文件系统概念
(磁盘友好型多路搜索树，数据库索引核心)

---

Step 25: N 跳表 SkipList

前置: 链表 + 哈希
(概率型快速查找结构)

POJ 线段树/树状数组: POJ 3468 A Simple Problem with Integers, POJ 2352 Stars
HDU 线段树: HDU 1166 敌兵布阵, HDU 1754 I Hate It
Codeforces 线段树 tag → 按 rating 1600+ 筛选

---

算法技巧补充速查

以下文件在整个 DSA 学习过程中按需查阅，已在上方各 Step 中标注对应关系：

• 顺序结构 — 基础
• 分支 — 基础
• 循环 — 基础
• 数组 — Phase 1
• 字符串 — Phase 2-3
• 函数与结构体 — 基础
• 模拟与高精度 — 任何时候
• 排序应用 — Phase 1 Step 5
• 暴力枚举 — Phase 1 Step 5
• 前缀和 — Phase 3 Step 12
• 差分 — Phase 3 Step 12
• 双指针 — Phase 1 Step 2 / Phase 3 Step 14
• 滑动窗口 — Phase 3 Step 14
• 下标技巧 — Phase 2
• 贪心 — Phase 3 Step 13
• 二分查找 — Phase 1 Step 6
• 二分答案 — Phase 3 Step 11
• 递推递归 — Phase 3 Step 15
• 搜索 — Phase 3 Step 16
• 动态规划 — Phase 3 Step 17
• 图论算法 — Phase 4 Step 18
• 连通性 — Phase 4 Step 19
• 概率与期望 — 选学
• 优化 — Phase 5

---

推荐算法资源

以下开源项目可配合本路线各 Phase 使用，按推荐优先级排列。

OI-wiki — 编程竞赛百科

• 仓库: https://github.com/OI-wiki/OI-wiki
• 在线站: https://oi-wiki.org
• Stars: 26.3k
• 语言: 中文

OI-wiki 是中文编程竞赛领域最完整的知识整合站点，覆盖 OI/ICPC 的全部知识点（基础语法、搜索、DP、图论、数论、计算几何等）。做题遇到不会的知识点，先去 OI-wiki 查——它的知识树结构和本教程的 DSA 路线高度互补。如果你发现在某个知识点上本教程讲得不够深，OI-wiki 通常是下一步的绝佳去处。

---

TheAlgorithms 系列 — 多语言参考实现

TheAlgorithms 社区在多个语言中提供了算法实现，所有代码均为教育目的编写，有测试、有文档、无外部依赖。

仓库	Stars	与本教程的关系
TheAlgorithms/Python	223k	Python 刷题时对照参考
TheAlgorithms/C-Plus-Plus	34.5k	本教程 C++ 主线直接对照
TheAlgorithms/C	22.2k	本教程 C 主线直接对照
TheAlgorithms/Java	66k	Java 备查
TheAlgorithms/Rust	25.9k	Rust 备查
TheAlgorithms/Go	18.1k	Go 备查

使用建议：学完某个数据结构后，打开对应仓库搜索该结构，阅读其实现代码。对比不同语言对同一算法的实现差异——这本身就是极好的学习方式。

---

awesome-algorithms — 精选资源导航

• 仓库: https://github.com/tayllan/awesome-algorithms
• Stars: 25.4k

一份精选的算法学习资源列表，按 Beginner-Friendly / Programming Contest / Theory & Fundamentals / Cheat Sheet 等分类。包含：

• 书籍推荐：CLRS、Algorithm Design Manual、TAOCP
• 在线课程：MIT 6-006、6-046j
• 竞赛平台：Codeforces、AtCoder、LeetCode、HackerEarth
• 可视化工具：VisuAlgo、See Algorithms

适合在本路线学完某个阶段后，按需去 awesome-algorithms 里找对应的书或课程深入。

---

Algo-Atlas — LeetCode 2000 题刷题计划

• 仓库: https://github.com/lvy010/Algo-Atlas
• Stars: 493
• 语言: C++ / Python

作者整理的 LeetCode 刷题笔记（8 个月 2000 题计划），按题型分类整理（双指针、滑动窗口、前缀和、位运算、DFS/BFS、DP、贪心等）。每个大类下有典型例题的详细题解（CSDN 博客），适合按本路线 Phase 3（算法专题深化）的顺序做对照刷题。

使用方式：git clone 到本地，用 Typora 或 Obsidian 打开 .md 文件，可边看题解边写代码。

---

---

Phase 6 — 字符串算法 (建议 10 天)

字符串是算法竞赛中仅次于数组的第二高频考察对象。推荐学习顺序：字符串哈希 → KMP → 字典树 → AC 自动机 → Manacher。

Step 26: 字符串哈希 (String Hashing) (2 天)

重点: 滚动哈希、双哈希防冲突、O(1) 子串比较、哈希应用
前置: 前缀和思想
来源: OI-wiki

平台	题目编号	题目名	说明
洛谷	P3370	字符串哈希	哈希模板
洛谷	P2757	等差数列	哈希+数学
LeetCode	1044	Longest Duplicate Substring	二分+哈希

Step 27: KMP 算法 (2 天)

重点: next 数组的构建与含义、匹配过程、时间复杂度分析 O(n+m)
前置: 字符串基础
来源: OI-wiki

平台	题目编号	题目名	说明
洛谷	P3375	KMP 字符串匹配	模板题
洛谷	P2375	动物园	KMP 变体
LeetCode	28	Find the Index of First Occurrence	基础匹配

Step 28: 字典树 Trie (1 天)

前置: Trie (RootStack)
来源: OI-wiki 补充 / RootStack 已有
(本教程已有字典树章节，OI-wiki 的内容可作为补充阅读，重点看前缀统计和异或对问题)

平台	题目编号	题目名	说明
洛谷	P2580	于是他错误的点名开始了	Trie 模板
洛谷	P4551	最长异或路径	Trie + 异或
LeetCode	208	Implement Trie	Trie 实现

Step 29: AC 自动机 (Aho-Corasick) (3 天)

重点: Trie + fail 指针、多模式串匹配、与 KMP 的联系
前置: Trie + KMP
来源: OI-wiki

平台	题目编号	题目名	说明
洛谷	P3808	AC 自动机（简单版）	模板题
洛谷	P3796	AC 自动机（加强版）	统计出现次数
洛谷	P5357	AC 自动机（二次加强版）	fail 树优化

Step 30: Manacher (回文串算法) (2 天)

重点: 奇偶统一处理、对称半径、O(n) 回文串检测
前置: 字符串基础
来源: OI-wiki

平台	题目编号	题目名	说明
洛谷	P3805	Manacher 模板	最长回文子串
LeetCode	5	Longest Palindromic Substring	最长回文子串
LeetCode	647	Palindromic Substrings	回文子串计数

POJ 字符串经典: POJ 3461 Oulipo (KMP), POJ 2406 Power Strings (KMP period)
HDU 字符串训练: HDU 2087 剪花布条 (KMP), HDU 1711 Number Sequence (KMP)
Codeforces 字符串 tag → 按 rating 1500+ 筛选

---

Phase 7 — 数论基础 (建议 10 天)

数论是算法竞赛中数学部分的基石。O(1) 快速幂、素数筛、GCD 等技巧几乎是每场比赛的必考内容。

Step 31: 快速幂与模运算 (2 天)

重点: 二分幂 O(log n)、模运算性质、大数取模
来源: RootStack: 快速幂与模运算

平台	题目编号	题目名	说明
洛谷	P1226	快速幂	模板题
LeetCode	50	Pow(x, n)	快速幂实现

Step 32: 素数筛 (1 天)

重点: 埃氏筛、欧拉筛(线性筛)、质因数分解
来源: RootStack: 素数筛

平台	题目编号	题目名	说明
洛谷	P3383	线性筛素数	模板题
洛谷	P1835	素数密度	区间筛
LeetCode	204	Count Primes	素数计数

Step 33: GCD / EXGCD 与模逆元 (2 天)

重点: 欧几里得算法、扩展欧几里得、模逆元（费马小定理 / EXGCD）、线性求逆元
来源: RootStack: GCD与EXGCD

平台	题目编号	题目名	说明
洛谷	P1082	同余方程	EXGCD 模板
洛谷	P3811	模意义下的乘法逆元	逆元模板
洛谷	P5431	模意义下的乘法逆元 2	O(n) 求多个逆元

Step 34: 中国剩余定理 (CRT) (2 天)

重点: 一元线性同余方程组、CRT 公式、EXCRT（模不互质）
前置: EXGCD
来源: RootStack: 中国剩余定理

平台	题目编号	题目名	说明
洛谷	P1495	曹冲养猪	CRT 模板
洛谷	P4777	EXCRT 模板	扩展中国剩余定理

Step 35: 组合数学基础 (3 天)

重点: 排列组合公式、卢卡斯定理、卡特兰数、容斥原理
来源: RootStack: 组合数学基础

平台	题目编号	题目名	说明
洛谷	P3807	卢卡斯定理	Lucas 模板
洛谷	P1044	栈	卡特兰数
洛谷	P1450	硬币购物	容斥原理

POJ 数论经典: POJ 1995 Raising Modulo Numbers (快速幂), POJ 1845 Sumdiv (模运算+分治)
HDU 数论训练: HDU 2035 人见人爱A^B, HDU 1576 A/B (逆元)
Codeforces 数论 tag → 按 rating 1400+ 筛选

---

Phase 8 — 搜索进阶 (建议 7 天)

搜索是暴力解法的终极形态。DFS/BFS 之后的进阶方向包括启发式搜索、双向搜索和精确覆盖。

Step 36: 双向搜索 (Meet in the Middle) (2 天)

重点: 折半枚举、状态合并、空间换时间
前置: DFS / BFS
来源: RootStack: 双向搜索

平台	题目编号	题目名	说明
洛谷	P4799	世界冰球锦标赛	折半搜索
洛谷	P2962	灯	meet-in-the-middle

Step 37: A* 算法 (2 天)

重点: 启发函数设计、估价函数的可采纳性 (admissible)、曼哈顿距离/欧氏距离
前置: BFS + 优先队列
来源: RootStack: A* 算法

平台	题目编号	题目名	说明
洛谷	P1379	八数码难题	A* 经典题
LeetCode	752	Open the Lock	BFS / A*

Step 38: IDA* 与迭代加深 (1 天)

重点: 深度限制 + 启发式剪枝、IDA* vs A* 对比
前置: DFS + 迭代加深
来源: RootStack: IDA* 算法

平台	题目编号	题目名	说明
洛谷	P2324	骑士精神	IDA* 模板

Step 39: Dancing Links (选学) (2 天)

重点: 十字链表、精确覆盖问题 (Algorithm X)、数独/拼图应用
来源: OI-wiki

平台	题目编号	题目名	说明
洛谷	P4929	DLX 模板	精确覆盖模板

POJ 搜索进阶: POJ 1077 Eight (A*), POJ 2449 Remmarguts’ Date (K短路)
HDU 搜索训练: HDU 1043 Eight (多种解法), HDU 3567 Eight II
Codeforces 搜索 tag → 按 rating 1700+ 筛选

---

Phase 9 — DP 优化 (建议 7 天)

动态规划是竞赛中区分度的核心。仅掌握基础 DP 远远不够，优化技巧是冲金必学。

Step 40: 单调队列 / 单调栈优化 DP (2 天)

重点: 用单调队列维护决策集合、状态转移的滑动窗口形式
前置: 队列 / 滑动窗口
来源: RootStack: 单调队列优化 DP

平台	题目编号	题目名	说明
洛谷	P1886	滑动窗口	单调队列模板
洛谷	P1776	宝物筛选	多重背包单调队列优化
洛谷	P1725	琪露诺	DP + 单调队列

Step 41: 斜率优化 (CHT) (3 天)

重点: 将状态转移化为线性规划、维护下凸包/上凸包、二分斜率
前置: 堆 / 单调队列
来源: RootStack: 斜率优化 CHT

平台	题目编号	题目名	说明
洛谷	P3195	玩具装箱	斜率优化模板
洛谷	P3628	特别行动队	斜率优化
洛谷	P2900	Land Acquisition	斜率优化 + 贪心排序

Step 42: 四边形不等式优化 (2 天)

重点: 决策单调性、四边形不等式、Knuth 优化、分治优化
来源: RootStack: 四边形不等式优化

平台	题目编号	题目名	说明
洛谷	P4767	邮局	决策单调性
洛谷	P1912	诗人小G	四边形不等式

POJ DP 优化: POJ 3709 K-Anonymous Sequence (斜率优化), POJ 1180 Batch Scheduling (DP优化)
HDU DP 优化: HDU 3507 Print Article (斜率优化), HDU 2829 Lawrence (DP优化)
Codeforces DP tag → 按 rating 1800+ 筛选

---

Phase 10 — 杂项技巧 (建议 7 天)

这些技巧无法归入单一类别，但在竞赛中出现频率极高。

Step 43: Mo’s 算法 (2 天)

重点: 分块 + 离线处理、区间查询、奇偶优化排序
前置: 线段树 / 哈希表
来源: RootStack: 莫队算法

平台	题目编号	题目名	说明
洛谷	P1972	区间不同数的个数	HH 的项链 (Mo’s)
洛谷	P2709	小B的询问	Mo’s 模板
洛谷	P1494	小Z的袜子	Mo’s 统计概率

Step 44: CDQ 分治 (2 天)

重点: 三维偏序、分治降维、归并排序思想
前置: 排序 / 树状数组
来源: RootStack: CDQ 分治

平台	题目编号	题目名	说明
洛谷	P3810	三维偏序	CDQ 模板
洛谷	P3157	动态逆序对	CDQ + BIT

Step 45: 离散化与平行二分搜索 (2 天)

重点: 坐标压缩、整体二分、WQS 二分
前置: 二分查找
来源: RootStack: 整体二分与 WQS 二分

平台	题目编号	题目名	说明
洛谷	P1525	关押罪犯	二分+染色
洛谷	P3527	Meteors	整体二分模板

Step 46: Old Driver Tree (ODT) (1 天)

重点: set 维护连续段、区间染色、随机数据下的均摊复杂度
前置: BST
来源: RootStack: ODT 珂朵莉树

平台	题目编号	题目名	说明
洛谷	P2787	语文1	ODT 应用
洛谷	CF896C	Willem, Chtholly and Seniorious	ODT 出处题

POJ 分治: POJ 2299 Ultra-QuickSort (归并/逆序对), POJ 2104 K-th Number (主席树/整体二分)
HDU 数据结构: HDU 2665 Kth number (主席树), HDU 4417 Super Mario
Codeforces 数据结构 tag → 按 rating 1800+ 筛选

---

Phase 11 — 计算几何入门 (建议 5 天)

计算几何在 ICPC 中频繁出现，需要掌握向量运算基础。

Step 47: 二维几何基础 (2 天)

重点: 向量运算、叉积/点积、线段相交、点在多边形内
来源: RootStack: 二维几何基础

平台	题目编号	题目名	说明
洛谷	P1153	点和线	几何基础
洛谷	P1355	海伦公式	几何面积

重点: Graham Scan、Andrew 算法、极角排序
前置: Step 47
来源: RootStack: 凸包

平台	题目编号	题目名	说明
洛谷	P2742	凸包模板	Graham/Andrew
洛谷	P1452	旋转卡壳	求最远点对

Step 49: 半平面交 (1 天)

重点: 极角排序 + 双端队列、多边形的核
前置: Step 47
来源: RootStack: 半平面交

平台	题目编号	题目名	说明
洛谷	P4196	半平面交模板	多边形的核

POJ 计算几何: POJ 2318 TOYS (点线位置), POJ 1113 Wall (凸包), POJ 2007 Scrambled Polygon (极角排序)
HDU 计算几何: HDU 1392 Surround the Trees (凸包), HDU 2036 改革春风吹满地 (多边形面积)
Codeforces 几何 tag → 按 rating 1500+ 筛选

---

Phase 12 — 竞赛实务与策略 (建议 5 天)

除了算法本身，竞赛中的战术决策同样重要。如何快速读入、如何避免低级错误、如何应对交互题，这些能力直接影响比赛成绩。

Step 50: 输入输出与文件操作 (1 天)

重点: scanf/printf vs cin/cout 取消同步、快读模板、文件重定向

快读模板（整数）：

int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

cin/cout 加速：

ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

文件重定向：

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

Step 51: 常见错误与调试 (1 天)

重点: 数组越界、整数溢出、未初始化变量、浮点精度、多测不清空

错误类型	说明	预防
数组越界	索引超出声明范围	开大 5~10；使用 vector::at()
整数溢出	int 存不下 $10^9+7$ 相乘	多用 long long
未初始化	局部变量默认值不确定	声明即赋值 int x = 0
浮点精度	double 比较用 eps	fabs(a-b) < 1e-9
多测不清空	全局容器残留数据	在 main 开头处理

对拍脚本（Linux）：

# gen: 随机数据生成器 (输出到 stdout)
# brute: 暴力解
# main: 优化解
while true; do
    ./gen > in.txt
    ./brute < in.txt > ans.txt
    ./main < in.txt > out.txt
    diff ans.txt out.txt || break
done

Step 52: 常见技巧与策略 (2 天)

重点: 打表找规律、对拍、随机化、构造题思路、卡常技巧

• 打表找规律：小数据暴力枚举，观察输出模式
• 随机化：随机打乱输入避免特殊构造数据
• 构造题：从边界到一般，先找特例再推广
• 卡常技巧：O2 优化、const / constexpr、引用传参、++i 代替 i++
• 题目顺序：先做有思路的题，倒序开题有时有效

Step 53: 交互题 (1 天)

重点: flush 输出、二分交互、图论交互与猜测

// 二分猜数示例
int l = 1, r = 1e9;
while (l < r) {
    int mid = (l + r) / 2;
    cout << "? " << mid << endl;  // flush automatically if endl
    int resp; cin >> resp;
    if (resp == 0) { cout << "! " << mid << endl; return; }
    if (resp > 0) r = mid - 1;
    else l = mid + 1;
}

关键点：

• 使用 endl 而不是 \n（自动 flush）
• 或手动 cout.flush() / fflush(stdout)
• 注意交互题读入格式要求

平台	题目编号	题目名	说明
洛谷	P1948	交互题模板	交互基本实现
Codeforces	交互标签	大量练习题	搜索交互标签

POJ 竞赛实务: POJ 1000-5000 经典题单按序号刷, POJ 3278 Catch That Cow (基础BFS)
HDU 竞赛实务: HDU 1000-2000 入门题单, HDU 1043 Eight (多解法对比)
Codeforces 按 rating 分级 → 从 800 开始逐级上分

---

推荐阅读物

• Introduction to Algorithms (CLRS)
• Algorithms (Robert Sedgewick)
• 算法导论 (中文版)
• 算法竞赛入门经典 (刘汝佳)
• 挑战程序设计竞赛

语言官方文档

• cppreference (STL reference): https://en.cppreference.com/
• 洛谷 (刷题平台): https://www.luogu.com.cn/
• LeetCode: https://leetcode.com/
• AtCoder: https://atcoder.jp/
• Codeforces: https://codeforces.com/

---

竞赛进阶资源

以下平台适合有志于ACM/ICPC/OI竞赛的学习者：

平台	链接	特点
洛谷	https://www.luogu.com.cn/	中文社区，题解丰富，难度分级清晰
POJ (北大OJ)	http://poj.org/	经典题库，适合打基础
HDU (杭电OJ)	https://acm.hdu.edu.cn/	多校训练，暑期集训
Codeforces	https://codeforces.com/	国际竞赛，实时rating
AtCoder	https://atcoder.jp/	日本竞赛，题目质量高
Virtual Judge	https://vjudge.net/	聚合平台，多OJ一站式刷题
牛客竞赛	https://ac.nowcoder.com/	国内校招+竞赛

普通学习/面试 → 力扣 (LeetCode) 足够
竞赛道路 → 洛谷 + Codeforces + POJ/HDU 必不可少