OI Wiki 学习地图 · 第 7 章 省选与 IOI 专题

OI Wiki 学习地图 · 第 7 章 省选与 IOI 专题

章节摘要:本章是省选与 IOI 级别的专题,讲计算几何(docs/geometry/ 14篇)与杂项难点(docs/misc/ 32篇)。莫队算法、插头 DP、LCT(Link-Cut Tree)是本章难点(★),做慢节奏精讲。本章还会引用 OI Wiki 自带的 docs/contest/roadmap.md 学习路线图。本章共 2 节,前置依赖为第 1-6 章。

路径坐标

省选/IOI(本章) → 实战备赛(第8章)

学习目标

1. 掌握计算几何基础(凸包/旋转卡壳/半平面交)。
2. 理解莫队算法(★)。
3. 理解插头 DP(★)。
4. 理解 LCT(★)。
5. 参考完整学习路线图。

子章节导航

01 计算几何(对应 docs/geometry/)

向量运算/叉积;凸包(Graham/Andrew);旋转卡壳;半平面交;扫描线;最近点对;引用 docs/geometry/ 14篇;计算几何的精度陷阱。

02 杂项难点精讲 ★(对应 docs/misc/)

莫队算法 docs/misc/mo-algo(离线区间查询/分块排序/指针移动/复杂度O(n√n));插头DP docs/misc/plug-dp(轮廓线DP/连通性状态编码/括号表示法,状压DP的极致);LCT docs/ds/lct.md(Link-Cut Tree/实链剖分/splay/makeroot/link-cut,动态树);其他杂项(折半搜索/模拟退火/杂项);docs/contest/roadmap.md 学习路线图(OI Wiki自带的完整路线,本教程参考扩展);慢节奏精讲三个难点。

前置知识与后续延伸

前置:第1-6章(状压DP→插头DP;树/平衡树→LCT;分块→莫队)。后续:第8章实战备赛。