洛谷-试炼场：省选斗兽场/NOI 神殿

原题单作者 @CLCK 编排的省选及以上训练参考，覆盖优化、动态规划、网络流、图论与高级数据结构。虚树、2-SAT、后缀自动机、可并堆、回文自动机五个专题为后续补充。

0 / 0 已完成

洛谷-试炼场：省选斗兽场/NOI 神殿

原题单作者：@CLCK。转载或引用请注明作者。

上一章：提高历练地

面向省选及以上选手的训练参考。省选水平的 OIer 通常已能自行组织训练，本章仅供参考。

目录

  1. 基础优化、动态规划与网络流
    1. 省选基础：读入/输出优化
    2. 省选基础：位运算
    3. 省选基础：打表
    4. 动态规划 1
    5. 动态规划 2
    6. 网络流：最大流
    7. 网络流：费用流
    8. 单调队列
    9. 概率期望
    10. 二分图
  2. 分治、字符串与树结构
    1. 点分治
    2. 虚树
    3. 2-SAT
    4. 后缀自动机
    5. 后缀数组
    6. 主席树
    7. 数位 DP
    8. AC 自动机
    9. 平衡树
    10. 树链剖分
    11. 动态树
    12. 可并堆 / 左偏树
    13. 回文自动机 / Manacher
    14. 树套树
  3. 高级数据结构与数论
    1. 可持久化 Trie 树
    2. 莫队算法
    3. 分块
    4. 莫比乌斯反演
    5. 其他

基础优化、动态规划与网络流

省选基础：读入/输出优化

读入与输出优化是省选刷题的必要技能。本组需要自行实现相应的处理。

省选基础：位运算

位运算常能优化常数、空间或时间，有时能多通过一些数据点。

省选基础：打表

打表通常不是正解，但能帮助取得会超时或超空间部分的数据点。

动态规划 1

动态规划 2

网络流：最大流

网络流：费用流

单调队列

概率期望

二分图

分治、字符串与树结构

点分治

虚树

虚树把一棵大树按「关键点 + 它们两两的 LCA」压缩成 O(k) 个节点的小树，让每次询问都能在 O(k log k) 而不是 O(n) 内完成。省选里凡是「每次询问给定一个点集，要求在树上做统计」的题，第一反应就该是虚树。

2-SAT

省选的高频送分题。识别信号是「每个对象只有两种选择，且选择之间有强制约束」，建图后跑 Tarjan 求 SCC 即可。近年省选几乎每年都有一道。

后缀自动机

后缀数组的强对手。SAM 的优势在于能在线构造、能维护 endpos 集合、能配合线段树合并处理多串问题。省选字符串难题基本绕不开它。

后缀数组

主席树

数位 DP

AC 自动机

平衡树

树链剖分

动态树

可并堆 / 左偏树

树上合并问题的主力工具。凡是「每个节点维护一个堆，需要把儿子的堆合并到父节点」的题（树上贪心、树上第 k 大），可并堆都是标准解法。

回文自动机 / Manacher

Manacher 求最长回文子串是 O(n)，回文自动机（PAM）则能在 O(n) 内建出所有本质不同回文子串的结构。省选里出现「回文」二字的题，基本就是这两个工具之一。

  • luogu P3805洛谷原题
    · 【模板】Manacher
  • luogu P4555洛谷原题
    · [国家集训队] 最长双回文串
  • luogu P1659洛谷原题
    · [国家集训队] 拉拉队排练
  • luogu P4287洛谷原题
    · [SHOI2011] 双倍回文
  • luogu P5496洛谷原题
    · 【模板】回文树 / 回文自动机（PAM）

树套树

高级数据结构与数论

可持久化 Trie 树

莫队算法

分块

莫比乌斯反演

其他