待写 #03

[垃圾桶 #05](https://www.luogu.com.cn/training/419165) **Let's f\*\*king go!** 咕咕咕，好像没人看，断更了 --- `Ctrl + 'F'` 可实现快速查找 exlg 可显示难度并点击题号跳转题目 --- - SP3928，数位入门 - AT_arc150_c，推子序列的性质，然后 dijkstra 秒掉，很好玩 - P2515，裸的树形 dp，用 Tarjan 优化一下就过了 - P3089，裸的单调队列 - AT_arc151_b，并查维护联通块统计贡献，挺好玩的 - P4168，P2801，分块入门 - P2572，九个信息，三个懒标记，裸的但码量大 - AT_arc073_d，线段树优化 dp，比较恶心 - P6348，线段树优化建图（在线段树上建图） - P4559，毒瘤主席树 - P3293，裸的主席树 - P2824，AT_abc237_g，CF1486D，一个小套路，用 `01` 表示一个数与 $X$ 的关系，剩下用线段树维护就行，AT_agc006_d 用二分找答案 - P3806，P2634，裸的点分治 - P4003，网络流巨型分讨题（知道是网络流就比较好想） - SP1557，线段树妙题 - AT_abc284_f，哈希题，卡一下模数就过了 - CF519E，水题，随便分讨一下 - P2486，水题，注意链上区间合并的左右端点细节 - P6587，水题，可以暴力线段树做 - P5588，树上分讨 - AT_arc143_e，树上好题，推性质 - CF629E 裸题，含括很多套路 - P4396，P4113，P1997，P3709 莫队裸题 - P4592，树剖 + 可持久 + 01trie + 动态开点，水 - P1903，回滚莫队，注意移动时间戳时只有更改在区间查询范围时才直接对答案造成影响 - CF817F，大水题，用脚想 mex 当然只可能是 $1$，$l-1$，$l$，$r$，$r+1$，不如 P2572 - CF1516D，倍增套路题，裸的 - CF1514D，性质好玩，然后裸的主席树 - CF1034B，懒得推性质，所以直接数据分治，特判 $n=1$ 或 $m=1$ - P3521，性质随便推一下，然后用动态开点维护 - P8867，边双缩点，然后变成了毒毒的树形 dp，要比较细心写 - CF1076E，离线，以 dfn 为时间轴，dep 为 y 轴，随便维护 - CF1324F，裸的换根 dp - U41492， 树上~~人类智慧~~启发式合并模板 - CF600E，裸的 - CF208E，CF246E，CF375D，CF570D，CF1009F，裸的 - CF960E，比较恶心，对拍了九组数据才过 - P4838，裸题 - CF1110G，神仙题，推性质然后运用拆点思想 - SP13015，珂朵莉树可爱 - CF741D，好题。建议先做 CF570D，位运算处理路径字符情况，用桶维护合并。 - CF280C，水，考虑单点被选中的概率，即其在所有父节点之前被选的概率，即 $\frac{1}{dep_i}$，加起来就好。 - CF1110F，送分裸题，直接 dfs 离线计算答案，换根 dp 用线段树维护，打个懒标记就行了。 - CF893F，有趣的主席树，以深度为时间轴建树，以 dfn 序做下标。 - P1648，枚举十六个象限的极点，对所有点计算曼哈顿距离，取极差的最大值即为答案。 - CF1187E，树形 dp，$f_{x,1}$ 表示以 $x$ 为子树符合约束条件，且 $x$ 分割后所在的联通块含 $1$。 - P2986，裸的换根 dp - P4084，简单的树形 dp - P1453，P2607 基环树，dp 两次，注意森林 - P3554，从子节点考虑 - P3565，枚举 LCA 作根，计算子树贡献 - CF940F，带修莫队 + 暴力 - P1975，数据范围太水，直接暴力 - CF1646D，简单的树形 dp - CF785E，分块暴力树状数组维护出现次数，计算逆序对的变化 - CF916E，裸的树剖 + 比较恶心的分讨，一个小结论：题中 $\texttt{LCA}$ 就是 $\texttt{LCA}(x,y)$，$\texttt{LCA}(x,r)$，$\texttt{LCA}(y,r)$ 这三者中深度最大的 - CF1045G，将位置离散化，对 $q_i$ 进行 CDQ，树状数组维护位置 - P1600，将路径拆成 $s\to\texttt{LCA}(s,t)$，$\texttt{LCA}(s,t)\to t$，移项一下统计答案的方程，用两个桶维护，符合区间加性质，dfs 作差 - P3157，将删除时间作为一个维度进行 CDQ，当然也可以分块 + 树状数组 - P4427，树剖裸题，分别维护次方和 - P4092，P6098，裸的树剖 - CF911G，动态开点 + 线段树合并，维护结构 - CF852D，二分 + 网络流，好做 - P3806，板题，比较卡常 - P2634，P4178，裸题 - P4149，还是比较裸 - CF825G，树上性质题 - CF1041E，构造题，好做 - P8817，$n$ 次 bfs，然后很明显的路径折半，保证点不重复可以保存两个次优决策 - P2680，树剖好题，改边当然在最长路径上，考虑改边之后的最大值，经过被改边的路径不如最长路径大，用路径更新边就可以 - P3730，莫队 + 值域分块 - P3029，双指针 - AT_arc066_c，好玩的性质题，看样例 #3 比较好想 - AT_arc084_b，图论建模，以价值作连边，跑 01bfs - CF18E，简单 dp 题 - AT_arc089_b，裸题，前缀和优化 - AT_abc165_f，树上 $\texttt{LIS}$ - AT_abc229_g，非常综合的一道思维题 - CF36D，打表找规律（ - CF131D，基环树裸题 - P6037，随便推一个性质就做完了 - P1099，U89620，P2491，三倍经验，扫出来树上直径然后跑双指针 + 单调队列 - P2018，水题，暴力 - P2146，裸的树剖 - P5801，博弈，树上完美匹配 - P4097，李超线段树模板 - P6047，推性质，方程 $ij$ 项为负 - AT_abc160_f，换根 dp，用逆元维护转移 - CF1771D，树上区间 dp - P5300，水题，对于每一位计算贡献，变成两个子问题，用单调队列进行维护 - AT_dp_w，线段树优化 dp - P3514，思维题，左/右存在 $2$，或左右和为 $2$ - P4180，建生成树，对于每条非树边，考虑代替与其形成环的路径上最大/次大边，倍增维护 - P2564，裸的双指针 - P1169，棋盘染色，垂线法 - P3431，树状数组优化 dp - P5092，边带权并查集 - UVA12345，裸的带修莫队 - AT_code_festival_2017_qualb_c，分类讨论，推性质 - P2767，超级水的 dp 题 - P5305，P4211 的加强版，思考路径 +1 的本质 - P5676，不难想到 Tarjan，关键在建模 - AT_dp_v，换根 dp，但是要用前后缀维护乘积 - P4735，数据结构裸题，可持久化 + 动态开点 + 01trie ~~（我也不知道我自己写出来的是什么数据结构~~ - CF1285D，trie 上树形 dp - P3847，裸的区间 dp - P4381，基环树上直径，用单调队列优化 - P3961，按斜率排序，变成有依赖的树形背包，去掉根节点变成多条链，优化成 01 背包 - CF1795C，二分 + 前缀和 - P6011，二分 + 树状数组维护位置，线段树维护权值 - CF1796C，集合内的数按大小排序，相邻成倍数关系，要求元素最多，则倍数尽量取 $2$，$4\gt2^2$，所以不存在相邻 $4$ 倍及以上，$3^2 \gt 2^3$，最多存在 $1$ 个相邻 $3$ 倍 - CF888E，折半搜索，分类讨论 - AT_arc079_c，很明显的暴力题 - P3293，主席树裸题，注意细节 - P9117，裸题，对于行列打懒标记，记录修改时间 - P9119，水题，一个小套路 + 区间 dp - CF1251D，CF1201C 的加强，很好想 - P4095，维护前后缀 dp，查询时合并 - CF296B，裸的 dp - CF229D，dp + 二分，水 - CF223B，对前后缀模拟，用子序列的性质合并 - CF8C，状压毒瘤题，要优化 - P3413，数位裸题 - CF739C，差分不难想，主要在于如何维护 - P2470，区间 dp 好题 - P3761，暴力裸题，随便转换一下 - CF1092F，换根裸题 - CF700B，按边计算贡献 - P4316，期望入门 - CF1476F，$F_i$ 表示前 $i$ 个灯最长前缀，列出特殊情况，数据结构维护 - P2852，hash 强行压数据范围，建 SAM，在 parent 树上统计同 endpos 出现次数 - P9127，得到所有子区间和，对于每个 $i$，定然是让一个包含 $i$ 和一个不包含 $i$ 的区间和相等，按和排序，最优区间定然相邻，判一下就行 - P3377，P2713，P1456，模拟裸题 - P4536，找规律 - P1552，贪心，贡献之和人数有关，则优先放弃价格高的，可并堆向上合并解决 - P3261，比较恶心的题，不难想到在堆上打懒标记，主要于实现 - P3804，P2408，P4070，SAM 基础运用 - P5341，SAM + 差分 - P4248，建反串，然后跑 SAM，在 parent 树上统计 $lcp(T_i,T_j)$ - P1257，1429，P7883，随机旋转 - P6564，dp 转移需要满足 $j\lt i$，$A_j\lt A_i$，$A_j\ge A_i-i+j$，后两个柿子成立时第一个柿子成立，树状数组维护 - P2322，模拟裸题，卡一下空间 - P5041，贪心猜性质，双端队列维护 - P3065，trie + 拓扑排序 - P2757，线段树好题 - CF1746F，比较好想的，随机化 - P4782，P4171，P5782，模板 - P6378，前后缀思想优化建图 - P5297，大模拟 - P6965，前后缀 + trie 优化建图 - AT_arc158_b，人类智慧，取 $50$ 个极端值跑暴力 - P3360，P1270，树形 dp - P1663，暴力 - CF1077F，裸的单调队列优化 dp - CF543D，换根 dp + 逆元 / 前后缀 - CF703D，比较综合的水题，按 $r$ 离线 + 树状数组 - CF429D，P4423，人类智慧 - CF514D，双指针 + 单调队列维护最大值 - CF702E，倍增 - CF842D，建 01trie，异或即交换左右子树 - CF895C，状压 + 组合数优化 - CF1082E，贪心 - CF1030E，符合条件的区间应满足 `1` 的个数为偶数且个数最多的不超过总数一半。个数最多为 $64$，可做 - CF459E，非常有趣的 dp，按边权顺序 dp 而不是拓扑序 - CF786B，线段树优化建图，然后跑 dij - CF1764G，利用 $k=2$ 对数进行分组，二分 $1$ 的位置，列三元一次方程组求得 $\le mid$ 或 $\gt mid$ 的对数与剩下的（跨越 $mid$）对数，通过对数对长度的贡献查找 $1$ 与 $mid$ 的相对位置，排除 $n$ 的影响。当 $n$ 与 $1$ 共侧时不需要查询，各居两侧时查询相对位置。利用分类讨论省掉最后两次询问中的一个。 - P1539，用一个类似于轮廓线 dp 的状压，或者直接状压 - P3812，P3857，P4301，P4570，模板 - AT_abc223_h，以 $i$ 为优先级的线性基 - CF845G，P4151，性质：该路径一定能表示为若干环和一条 $1$ 到 $n$ 链的异或和 - P3201，链的启发式合并 - P7962，作差分数组，操作即交换差分数组元素，尽量使前面元素大，后面元素小，则差分数组应该是单谷，dp 计算 - P1527，P3332，整体二分模板题 - P4719，动态 DP 模板 - P4516，树形 dp，$F_{i,j,0/1,0/1}$ 表示以 $i$ 为子树选 $j$ 个点，选不选 $i$ 点，$i$ 点是否被监听方案数，乘法原理计数 - CF873D，简单构造题 - P3391，splay 维护数组顺序，左右翻转打懒标记 - SP2742，简单推一下柿子，矩阵乘法解决 - P1662，分块打表 - SP1487，可持久化裸题 - SP10707，树上莫队模板 - SP371，费用流模拟 - SP733，二分 + 广搜经典题 - SP57，这题能评紫？？？ - SP15569，手玩一下，hash + 二分暴力做 - CF1422D，有趣的图论建模 - CF97D，bitset 的暴力运用 - CF31E，比较裸的 dp - CF57E，暴力打表 - CF27D，观察不合法关系，二分图染色裸题 - P2619，恶心的二分，生成树 - CF1108F，取生成树，加入非树边，树剖 - P3979，分类讨论，对线段树非子树区间修改 - P4053，反悔贪心 - P8818，线段树裸题 - P1525，扩展域并查集 - P5787，线段树分治，按秩合并并查集 - P5227，线段树分治，对于每条边覆盖时间区间 - P2435，轮廓线 dp - AT_agc022_e，推性质 + dp，贪心地，消去三个 `0` 有 $3$ 的贡献，消去一个 `0` 和一个 `1` 和 `0/1`，贡献 $0$，最终 `1` 的个数大于 `0` 的个数即可，最多剩两个 `0`，所以保存最多两个 `1` 即可，dp - P8814，线段树维护几个 "极" 值，然后跑暴力即可 - P9190，简单 dp - P2223，网络流模拟 - P3684，计算出以每个点为中心的最大半径，令之为点权，kruskal 思想将相邻点对按较小点权从大到小排序，并查集维护联通，进行连边，得到森林，树剖跑一下路径最小值就行 - AT_abc277_e，图论建模 + 最短路 - P3792，线段树维护极值、平方和取模，hash 思想 - UVA11270，轮廓线 dp - P2403，Tarjan + 优化建图，行列开一个虚点连边 - P1713，插头 dp，裸的 - P4652，边双缩点 - P1401，二分 + 网络流 - P1442，动态开点线段树优化 dp，用个懒标记覆盖 - P5391，操作构成一棵树，利用树剖思想，重链开一个数组，最多同时使用 $log(q)$ 个数组，回收利用 - P2605，将两个代价分开算，对于每个村庄二分得到区间，没有选点则需 $W$，离线按右端点小到大排序，扫一遍过去，$F_i$ 表示当前已选最右点为 $i$ 的最小代价，放点即 $min+C$，区间以左加 $W$，线段树维护 $F$ - P3625，~~人类智慧~~ 分类讨论 - P2295，$F_{i,j,0/1}$ 表示经过向右/下到达 $(i,j)$ 的最小代价，dp - P6157，树剖，$x\ mod\ y=x$，$y\ mod\ x<x$（$x<y$），维护前四大值 - P7302，$j$ 到 $i$ 的转移条件：$2t_i-p_i\ge 2t_j-p_j$ 且 $2t_i+p_i\ge 2t_j+p_j$，排序 + 树状数组 - P5303，矩乘，~~手玩矩阵~~，按已分配 $1\times1$ 分层，随便做 - P5304，二进制优化建图，没见过的套路 - P5678，改乘为与，改加为或，满足矩阵快速幂性质 - P4344，线段树查区间和 + 二分，然后区间覆盖 0/1 - P3402，模板 - P1985，按层填，使上一层符合条件 - P2042，平衡树经典题 - P2710，P4146，P3850，SP4487，P6707，平衡树练手题 - P2161，集合内线段不会有交集，左右端点同时有序，平衡树维护 - P2219，跑两次单调队列 - P5217，状压维护字符出现信息 - P7514，双指针 - P8969，维护置换 $f$，懒标记 $f(popcount(x+A))+B$ - P2473，状压，倒推 - P4949，树剖裸题 - P3313，动态开点 + 树剖 - P3199，分数规划 + SPFA - P1712，双指针 + 动态开点 - P3275，差分约束 - P5658，水题 - AT_abc282_h，以最小值进行分治 - P6242，势能线段树和历史最值模板题 - P2221，P4340，水的 - P5693，KTT 模板题，大概就是如果当前子树加会影响决策就暴力下传直到不影响，然后向上更新决策 - P5073，按整体加和离线，然后 KTT，非常毒瘤 - P6792，势能线段树里用 KTT，复杂度好奇怪 - P5025，裸的 - P2400，UVA1630，转移时存一下方案 - P2418，线段树优化 dp，水 - P1642，分数规划 - P1514，暴力 bfs，然后每个点控制一区间否则无解 - AT_arc069_d，二分答案，线段树优化 2-SAT 建图，水题 - CF555E，边双缩点，然后随便做 - P5043，为了让子节点 hash 顺序 "有序"，我们按 hash 值大小依次 hash - CF875D，最大值分治 - P5524，水题，要用树状数组代替部分线段树优化常数（毒瘤 - P4398，枚举错位，然后 dp 最大正方形 - P2839，不错的题，离散化，在值域上建主席树，然后对于询问二分，就是 GSS5 - P8868，对 $r$ 进行扫描线，则维护操作 $X$ 覆盖、$Y$ 覆盖，区间 $S$ 加 $X\times Y$，[维护推荐这个](https://www.luogu.com.cn/blog/eulogized/solution-p8868) - P4314，规定加标记优于覆盖标记，注意当前节点加标记下传要讨论是否子节点有覆盖标记 - P1822，分块打表 - P5009，用类似 P8868 的线段树维护 - P9169，博弈论题， - P4103，虚树 + 树形 dp - P2495，虚树 + 倍增 + 树形 dp - CF613D，虚树 + 树形 dp - P3233，虚树 + 倍增 - P4426，并查集取出生成树，最多加上 $11$ 条非树边，令这些边的端点为特殊点，建虚树，预处理虚树边的转移系数，状压枚举特殊点方案，在虚树上树形 dp - P7078，结论题，不会变成最小蛇就吃，否则判吃完后继续下去不会变最小蛇的回合的奇偶性，双端队列维护 - P4819，显然优先选父节点，然后扫子节点，$k$ 为选节点数，概率为 $\frac{n-k}{n}$，注意排除法对答案的影响 - P4197，P7834，建 Kruskal，主席树维护 - CF833B，线段树优化 dp - P2831，状压刷表 - P7114，预处理后缀 $C$ 的 $F$，枚举前缀 $AB$ 的长度，然后枚举 $i$，hash 判字符串是否相同，树状数组维护 $AB$ 的所有前缀 $F$ 并统计答案 - P3388，P8435，P8436，模板重学 - CF912E，折半搜索，二分答案，双指针 check - P3225，去掉割点后讨论联通块相邻原割点数，注意救援出口可能坍塌 - P5058，圆方树，入门 - P4320，建圆方树，LCA，计算答案 - CF487E，建圆方树，树剖，方点维护 multiset 存子节点权值，LCA 若为方点则带上其父亲的贡献 - P2279，贪心，先覆盖较深的节点用较浅的节点 - P5307，以乘上多少大于 $n$ 作为 dp 维度，以 $\sqrt{n}$ 作为分界发现最多 $2⌈ \sqrt{n}⌉$ 种值 - P7516，性质题，Floyed + 优化 - P3469，圆方树 - P7961，dp 裸题 - P4262，插头裸题 - P1841，Floyed 同时维护两点最短路数量，乘法原理统计 - CF802I，SAM 水题 - P6640，对 $t$ 建 SAM，预处理 $s_{[1,i]}$ 与 $t$ 的 LCS 长度 $p_i$，则答案即 $max_{i=l}^r\{i-l+1,p_i\}$，二分答案 - SP8093，CF204E，广义 SAM + 线段树合并 - P5284，码量巨大题，建 SAM，倍增找 $[l,r]$ 对应的节点，对于单节点多字符串前后缀优化建图，Tarjan 判环，拓扑 dp 计算答案，记得开 long long - CF427D，CF452E，P4081，P3181，P5546，广义 SAM 直接做 - CF235C，CF1780G，SAM 模拟即可 - CF1037H，贪心好想，在自动机上已匹配长度 $len$，沿自动机走则存在于原串，下一个点 endpos 需有 $[l+len-1,r]$ 中保证其位置不超出 $[l,r]$，线段树合并处理 endpos 即可 - P5309，分块，循环节，卡常 - P1117，枚举 $A$ 的 $len$，隔着放点，SAM 求 LCP，LCS，差分计答案 - P4094，后缀树，二分答案，倍增跳，线段树合并得到是否有符合位置条件的 $endpos$ - SP687，结论：$endpos$ 最小差 $g$ 则答案为 $\lfloor \frac{len}{g}-1\rfloor$，线段树合并时维护即可 - P5631，暴力，然后发现线段树分治优化 - P1667，操作实际交换前缀和数组，贪心 - P2463，hash 压字符集范围，SAM 做即可 - P2466，区间 dp - P2465，树上状压 dp - P7409，CF1073G，建 SAM，树上问题，虚树优化 - P8820，P4719，P5024，树剖套矩乘，又名动态 dp - P7915，对第一步分类讨论，变成两个栈，模拟 - P5689，裸题 - P5022，基环树 = 生成树 + 非树边 $\times1$，dfs 然后比较答案 - P2123，交换邻项法得到 cmp - CF840D，主席树裸题 - CF1198F，随机化，打乱取前缀，重复数压掉 - P4768，Kruskal 模板 - P4559，贪心，主席树 - P2779，数据水，中间点向周围 dp 转移 - P3272，插头裸题 - P2597，对 DAG 拓扑同时建树求 LCA - CF757F，dijks 一下，然后建 DAG - CF455B，trie 上 dp，博弈做一下 - CF1254D，化简操作，然后重儿子子树更改，非重打懒标记 - P4587，主席树模拟，暴力 - P5838，SP11985，主席树 - P3976，树剖 - P3859，简单背包 - P7350，hack hash 题，随机化 - P3757，P4099，树形 dp + 组合数 - P3354，树形 dp - P5384，dsu on tree - P5679，暴力 - P1817，暴力打表 / 插头 dp - P5903，树剖跳外层，内层 dfs 连续直接跳 - CF1009F，长链剖分 - P5904，长链剖分优化 dp - P4292，分数规划 + 长链剖分 + 线段树 - P7735，对与轻重儿子连边分别维护，注意要维护两个到轻儿子连边 - P1397，十进制矩阵快速幂 - AT_abc293_g，SP32900，P4867，莫队裸题 - P5906，AT_joisc2014_c，SP20644，回滚莫队裸题 - P4689，树上转化为序列，前缀和拆询问变成普通莫队题，随机选根卡常 - P4887，P5047，二次离线莫队 - P4688，莫队套 bitset，将询问分为三部分处理省空间 - P5048，分块卡常，存数的位置，对零块扩展答案，最多扩展 $2\times L$ 次 - CF1039D，根号分治 - AT_agc001_d，画图性质题 - AT_agc001_f，逆数组，归并排序 - P5398，二次离线莫队，卡常丧心病狂，~~出题人听我说谢谢您~~ - P2147，P3690，P4312，LCT 模板 - P1501，LCT + 加/乘标记 - P5212，SAM，LCT 维护答案 - CF1109F，双指针 + LCT + 线段树 - P4172，P2387，LCT 维护最小生成树 - CF914E，点分治 + 状压 - P6329，P3241，点分树模板 - P5495，水题，循环展开卡过去 - P7492，分位操作 2，势能思想暴力改 - P4219，LCT 上每个节点记录其虚子树贡献 - P2542，离线为加边，树剖覆盖 - P4234，按边权从小到大排序，依次加边，若有环则舍弃其中最小权边 - CF1805E，抽屉原理，树剖 - SP2371，CDQ，转移放中间，树状数组 - CF1681F，对每种颜色边一起算贡献，每边贡献即删除该颜色后两端点联通块大小，LCT - SP16549，LCT 好题，化点为边，询问时去掉联通块最浅点导致多造成的贡献 - P2056，直径性质 + 线段树 - P3987，暴力，$x=1$ 不操作，$x=2$ 利用位运算 - P5236，建圆方树，前缀处理环上两点距离，LCA 求答案 - P9436，大分讨题 - CF1845E，DP 思维题 - CF1845D，思维题 - AT_arc163_c，考虑裂项 $\frac{1}{x}=\frac{1}{x+1}+\frac{1}{x(x+1)}$，set 维护未处理数，map 判断重复 - CF1017G，树剖 + 线段树思维题 - CF1428G，背包难题 - P3703，LCT，每一段重链表示一种颜色，操作 $1$ 即 access，到根节点路径权值可看作所经轻边数 +1, - P6292，SAM + LCT + 线段树 - CF827D，MST 性质 + 树剖 - AT_arc059_d，显然答案与 $S$ 无关，DP 方案数即可 - P4783，$A^{-1}A=I$ - P4035，高斯消元 - P2962，随机化暴力 - P4649，奇偶推性质，对子树进行状压，表示是否考虑，DP - CF1327F，分位计算贡献，DP 最后一次出现 $0$ 的位置，扫描线思想，前缀和优化，$R$ 表示被覆 $0$ 的右边界 - P6240，猫树模板题 - P3590，暴力 - AT_abc246_h，裸题，线段树维护矩乘 - P5336，区间 DP 难题 - P3604，莫队 - CF804D，直径性质 + 前缀和，根号分治，好题 - P5826，裸题，主席树维护 las - P9453，两次 KMP - P4479，二分答案，树状数组 - P5354，树剖裸题，略微卡常 - P5607，差分，线段树套线性基 - P1752，小根堆，二分，先将挑剔的人能取的放进堆中，然后优先取贵的 - P2511，二分 + DP - P3899，线段树合并 - CF1149C，括号树性质，线段树 - CF533F，分别对每个字符位置 hash - P9116，bfs 好题 - P3193，暴力 + 矩乘 - P3121，ACAM + 栈 - P4052，ACAM + DP - P2444，ACAM + dfs - P5319，取对数，分数规划，ACAM + DP，记录转移 - CF141E，MST - P2294，带权并查集 - P2446，最短路 + 拓扑排序 - P2966，Floyd - P3825，2-SAT，通过枚举非法强转两种情况 - P5012，并查集预处理 - P6192，斯坦纳树 - P6619，显然单峰函数，二分 + 树状数组优化 / 分块 - CF526G，包含 $2y-1$ 个叶节点的极小联通块，定然包含直径一端点，固定为根得到有根树，选 $2y-2$ 个叶节点到根的路径并边权和，长链剖分，最后考虑未包含 $x$ 节点，倍增向上跳，舍弃最小长链即可 - P1858，01 背包，归并优化 - CF1699D，区间 DP - P4127，固定数位和，计数 - P2481，找循环节，组合数 + DP - P2150，分解质因数，对小于 $22$ 的 $8$ 个质数状压，大于的排序到一段，一起 DP - P2396，CF327E，状压，lowbit 优化 - P5468，P6302，有向图上斜率优化 - P5325，Min_25 筛模板 - P3846，P4195，BSGS 模板 - P4454，P4028，P2485，BSGS 裸题 - SP4060，期望 + 博弈 - CF1849E，极值分治，st 表优化 - P4590，DP 套 DP，状压优化 - P2324，IDA* - P2467，DP 好题 - P4229，两次离散化，限制按权值排序，每个点只对最小限制有效，相同权值限制一起 DP 计数，好题，扫描线思想 - CF1511G，倍增好题 - P6371，数位 dp，$X$ 过大时暴力 - AT_agc056_c，差分约束，$0$ 个数减 $1$ 个数，保证字典序 - P4247，线段树 + 组合数学 - CF576E，线段树分治，离线 idea 好题，板题 - P8511，计算全局最优解，取不到的离线暴算 - AT_abc262_g，序列区间 dp + 值域区间 dp - CF983E，经典倍增，然后主席树计算最后一次的贡献 - CF1320D，水的推性质 + hash - P4755，最值分治 + 主席树 - P6247，随机化 - P6072，分为子树内贡献加上子树外，直接回滚莫队即可 - P3674，P5355，莫队 + bitset，根号分治 - P3224，P5064，建操作树 dfs，可撤销并查集 + 值域分块 - CF1526F，神仙交互题，随机化 - P8352，dp 套 dp，推转移性质强压状态 - P9499，贪心题 - P9478，离散化，容斥，扫描线 - P9481，树高较低，考虑以节点深度作为 Floyd dp 状态维度优化复杂度（~~考场想的：dfs 套 dfs，然后懒标记思想，回滚一下，废了~~ - P2086，根号分治，线段树暴力维护 + 卡常 - P2898，二分 + 并查集 - P6089，期望 + 树状数组 - P3336，恶心线性 dp 题 - P3333，hash，数据范围阅读题 - CF341E，奇怪的二进制辗转相除构造题 - P4169，P2093，P4148，P2479，K-D Tree - P9534，拓扑题 - P8955，时间轴上线段树，线段树上二分 - P6346，反悔贪心好题 - P3295，st 表 + 并查集好题 - P7843，倍增算答案，整体二分，可撤销并查集 - P5072，分块 + 根号分治 - P4460，状压 dp - CF825F，dp 水题 - CF24D，期望，精度允许误差，重复 dp 几次 - P5784，dp 水题 - P4117，分块 + 并查集好题 - AT_agc026_d，笛卡尔树 + 树形 dp - CF888G，建 trie，发现在 LCA 处贡献，dfs，再开一个 trie 算边权 - CF1149C，推性质 + 线段树 - AT_abc025_d，暴力状压水题 - CF653F，SAM + st 表，离线下来二分 - CF868F，决策单调性，下标分治 dp，保证了每层值域和一定 - CF23E，P1411，高精 + 树形 dp - CF163E，ACAM + BIT - CF587F，根号分治 + SAM + ACAM，离线，DS 好题 - CF718C，线段树 + 矩阵乘 + 光速幂 - CF581F，树形 dp - AT_apc001_f，推性质，状压 - CF963B，dfs 序反、正扫一下 - CF1491H，P7446，分块 + LCA - P1623，高精 + 树形 dp 水题 - CF340E，dp 题 - P3992，分块好题 - P4093，cdq - P5068，离线，BIT - P5665，dp - CF896B，交互好题 - CF1305G，推性质，MST，状压 dp 好题 - P3953，拓扑 + dp - P1084，倍增 + 二分 + 贪心 - AT_joisc2016_h，分块 + 小根堆妙题 - P5329，预处理排序时快速比较 - AT_arc147_e，反悔贪心好题 - CF961E，离线 + BIT - CF526F，CF997E，单调栈 + 线段树，离线，打标记 - CF1446D1，CF1446D2，推结论，根号分治，双指针好题 - P2664，两次 dfs 计数 - CF522D，扫描线然后线段树啊 - CF954G，二分，差分，贪心 - CF538F，数论分块 - CF1120D，dfs 序上前缀最小生成树并 - CF464E，主席树维护最短路 - CF1710D，任何时刻每个连通块都是区间，构造好题 - CF1152F1，dp 好题，值域上 dp，考虑插入元素到数组，易得方程 - CF1152F2，加个矩阵快速幂即可 - CF1368H1，最大流等于最小割，结论是分割线可以很平整，然后 dp - CF1368H2，加个动态 dp 即可 - P5664，容斥 dp - P3766，数学估算题 - CF1458D，把 0/1 看作上下跳，建图，求最小字典序欧拉回路，贪心 - P4480，P2917，网络流卡常裸题 - CF325E，神仙构造题，$i$ 与 $i+\lfloor\frac{n}{2}\rfloor$ 出边相同，并查集合并可得到环 - CF418E，水题，打表发现第三行之后交互出现，直接分块 - CF364E，平面分治，常数大 - CF627E，神仙题，不会 - CF1879E，超级有病的细节题 - P5891，sbh 写的哈希表吊打 stl %%% - CF543E，主席树卡空间做法 - P4755，极值分治 --- by wukaichen