做过的题整理

按照处理对象

图论

• P2934 [USACO09JAN] Safe Travel G——无向图最短路树及其性质
• P1948 [USACO08JAN] Telephone Lines S——有趣的二分答案
• P1850 [NOIP 2016 提高组] 换教室——最短路+期望dp

树

• P2700 逐个击破——贪心/树上dp
• NOIP2016(D1T2)天天爱跑步——用桶存储贡献，dfn差分
• P3066 [USACO12DEC] Running Away From the Barn G——树上差分+树上倍增
• P6594 [YsOI2020] 换寝室 —— 树形dp+二分答案
• P14363 [CSP-S 2025] 谐音替换 / replace——链上统计转子树贡献 离线二维数点

区间

• P11233 [CSP-S 2024] 染色——某种对区间处理的trick?
• P5937 [CEOI 1999] Parity Game——前缀和与扩展域并查集
• P3205 [HNOI2010] 合唱队——区间dp

基环树

• P2081 [NOI2012] 迷失游乐园——期望+换根dp+基环树

序列

• P4375 [USACO18OPEN] Out of Sorts G——找规律+权值树状数组

算法

贪心

• P2934 [USACO09JAN] Safe Travel G——无向图最短路树及其性质
• P1248 加工生产调度
• P12007 【MX-X10-T3】[LSOT-4] 全国联赛？——换根dp+贪心
• P2700 逐个击破——贪心/树上dp

dp

• P11233 [CSP-S 2024] 染色——某种对区间处理的trick?
• P1410 子序列——dp但是没想到
• P1386 座位安排——被想歪了的dp
• P1437 [HNOI2004] 敲砖块——超酷的dp
• P3572 [POI 2014] PTA-Little Bird——简单的单调队列
• P1654 OSU!——期望的线性性质与转化
• P2704 [NOI2001] 炮兵阵地——我不熟的状压
• P2081 [NOI2012] 迷失游乐园——期望+换根dp+基环树
• P4206 [NOI2005] 聪聪与可可——期望，记搜
• P1850 [NOIP 2016 提高组] 换教室——最短路+期望dp
• P2700 逐个击破——贪心/树上dp
• P3205 [HNOI2010] 合唱队——区间dp
• P1220 关路灯——简单的区间dp
• P6594 [YsOI2020] 换寝室 —— 树形dp+二分答案
• P2224 [HNOI2001] 产品加工——奇怪的状态优化
• P9870 [NOIP2023] 双序列拓展——dp转二维网格问题——从转化后的问题生成过程发现问题结构
• P14364 [CSP-S 2025] 员工招聘 / employ——钦定方案+容斥

二分 & 倍增

• P1948 [USACO08JAN] Telephone Lines S——有趣的二分答案
• P4155 [SCOI2015] 国旗计划——倍增加速贪心
• P3509 [POI 2010] ZAB-Frog——双指针+快速幂（倍增）
• P3066 [USACO12DEC] Running Away From the Barn G——树上差分+树上倍增
• P6594 [YsOI2020] 换寝室 —— 树形dp+二分答案

分治

• 平面最近点对——分治

数据结构

• P2391 白雪皑皑——经典并查集
• P1383 高级打字机——字典树与栈
• P3522 [POI 2011] TEM-Temperature——单调队列之我的倍增怎么似了😭
• P2572 [SCOI2010] 序列操作——复杂线段树之我的史山
• P2042 [NOI2005] 维护数列——FHQ-Treap维护序列
• P14363 [CSP-S 2025] 谐音替换 / replace——链上统计转子树贡献 离线二维数点

杂项

• P4331 [BalticOI 2004] Sequence 数字序列 slope trick
• P4375 [USACO18OPEN] Out of Sorts G——找规律+权值树状数组