个人算法题单整理

记录个人刷过的算法经典题目（好题），以备复习回顾。

一级目录参考 OI Wiki 进行设置。

语言基础

1 STL

1.1 set

知识点	难度	来源
multiset插入删除，异或运算性质：相邻元素值异或小于非相邻元素异或	ABC-600-Points	ABC308G

算法基础

1 递归&分治

$nlogn$ 可以试着往分治上面想

知识点	难度	来源
分治		2023CCPC深圳A

2 贪心

• 反悔贪心：用时固定模型 和 价值固定模型。一般都需要按某关键字排序 ，要尝试不同排序方法。

  反悔操作：维护一个堆，存储之前做过的所有操作；当前操作无法操作时，查看是否存在当前操作比之前操作更优的操作，更新掉。

知识点	难度	来源
贪心，排序，优先队列维护	ABC-500-Points	ABC308F 23年天大预推免机试题摘自此处

3 二分

知识点	难度	来源
二分中位数答案		2023CCPC桂林

4 构造

知识点	难度	来源
构造-分治，二进制，二分图，思维	绿题	LuoGuP9384/THUPC2023决赛

搜索

动态规划

1 线性DP

知识点	难度	来源
线性DP，前 $i$ 个选 $j$ 个的最优值	ABC-475-Points	ABC327E

2 背包DP

2.1 01背包

知识点	难度	来源
01背包+贪心	easy-medium	2023ICPC南京G
bitset优化，数量上的二进制优化	CF-rating-2700	CF1856E2
01背包+超大体积和价值，二进制拆分，分组背包思想	紫题	LuoGuP3188
前后缀背包		2022ICPC杭州C
回退背包 ，01背包计数回退	ABC-525-Points	ABC321F

2.2 多重背包

3 区间DP

4 树形DP

知识点	难度	来源
经典换根DP	CF-Rating-1900	CF1882D
贪心 + 树形DP		2023CCPC桂林H

5 状压DP

6 数位DP

参考 知乎数位DP总结

知识点	难度	来源
二进制拆分+组合计数+数位DP	银牌题	2022CCPC广州M
经典数位DP题目，需要注意pos为0时return的顺序，先判cnt，再判pos	CF-Rating-1900	CF1036C

字符串

1 字典树Trie

知识点	难度	来源
字典树，逆序字符串对统计		2022ICPC杭州K

数学

1 数论

1.1 数论分块

知识点	难度	来源
数论分块，找到 $l,r$ 很关键	蓝题	LuoGuP2261
整除分块+莫比乌斯反演	蓝题	LuoGuP3455

2 线性代数

2.1 线性基

常见问题

知识点	难度	来源
线性基	紫题	LuoGuP4151
线性基，统计子集异或和为0的所有元素个数之和		2019牛客多校1H | 题解
线性基，预处理因子，统计异或和为 0 和 x 的子集个数		2023CCPC桂林C

3 博弈论

知识点	难度	来源
找规律，sg函数，有向图游戏和		2023CCPC哈尔滨J

数据结构

1 并查集

知识点	难度	来源
区间合并，并查集判环		2023CCPC哈尔滨G

2 线性数据结构

2.1 单调栈

知识点	难度	来源
单调栈应用：求左（右）边第一个小（大）于 $a[i]$ 的位置 启发式分裂，两边都可以枚举统计答案，每次枚举数量较少的一遍	CF-rating-2300	CF1849E

3 树状数组

知识点	难度	来源
树状数组求区间不同颜色数+贪心+数据范围细节		2023CCPC桂林I

图论

1 树上问题

1.1 树链剖分

知识点	难度	来源
长链剖分+贪心		2022ICPC西安L
长链剖分优化DP模板题	CF-Rating-2300	CF1009F

1.2 树哈希

知识点	难度	来源
树同构+树哈希+基环树找环		2022ICPC杭州G （判断一个图的所有生成树是否同构）

2 最短路

2.1 Dijkstra

知识点	难度	来源
最短路径树板题（直接用dijkstra求从根出发的最短路，根到其他节点的最短路就形成一棵树，记一下pre就行）	CF-Rating-2000	CF545E

计算几何

1 扫描线

知识点	难度	来源
一维数组上的扫描线	偏思维，easy	CF1884C ABC188D

杂项