刷题太慢了（

50/50

1030: [JSOI2007]文本生成器

包含单词字符串数=总数-不含单词字符串数

后者可以建完AC自动机后直接DP出来（设当前在自动机上走几步走到哪个点）

2330: [SCOI2011]糖果

差分约束

要求最小方案，所以跑最长路

SPFA貌似跑负环复杂度会$O(n^2)$，所以我换了个判定方法，即当前点的最短路的长度大于 n 时则判定有负环

2005: [NOI2010]能量采集

数论

也就求个gcd前缀和，n不大，用莫比乌斯初步优化一下就可以出来了

1500: [NOI2005]维修数列

Splay模板题

学会了双旋写法

1070: [SCOI2007]修车

网络流

设$nm$个点，表示第i个维修工是否进行倒数第j次的维修，然后再设$n$个点，表示各车

最后费用设一下，求费用流

1061: [NOI2008]志愿者招募

网络流

将题目条件写成 n 个约束条件，增加松弛变量使得约束条件变成等式，变形式子使得每个变量只出现两次且一正一负

设有 m 个式子，那么建立 m 个点和源汇，每个变量作为一条流，通过约束条件建图，正为入流负为出流

然后去跑费用流

3211: 花神游历各国

暴力下传标记暴力修改，当一段区间内的所有数都小于2时不用下移标记修改

1432: [ZJOI2009]Function

当n为1时$ans=1$，否则第k层为$2*min(k,n+1-k)$

2434: [NOI2011]阿狸的打字机

建立AC自动机，求出FailTree的dfs序，遍历AC自动机，当访问到某询问的左端点时，查询右端点在FailTree中有多少标记点为其祖父

2875: [NOI2012]随机数生成器

快速幂+快速乘

1565: [NOI2009]植物大战僵尸

最大权闭合图，被保护点连至保护点，tarjan缩环后连至tarjan的点全部无效，然后跑网络流

2006: [NOI2010]超级钢琴

建堆，用堆维护$(a,l,r)$表示左端点为a且右端点范围为$[l,r]$的最大值。枚举左端点全部扔到堆里，然后选取最大值，并将右端点范围分裂成两块，通过ST表求得最大值后扔进堆里，循环K次

4413: [Usaco2016 Feb]Milk Pails.txt

随便记忆化搜索一下

1143: [CTSC2008]祭祀river

最长反链=最小链覆盖=最少可相交链覆盖，然后传递闭包一下就可以变成最少不可相交链覆盖

2435: [NOI2011]道路修建

树DP

3670: [NOI2014]动物园

ExKMP

3143: [HNOI2013]游走

高斯消元求出每个点的期望经过次数，推出每条边的期望经过次数，贪心编号

1415: [NOI2005]聪聪和可可

最短路得移动方向，然后记忆化搜索一发

2879: [NOI2012]美食节

网络流

同“修车”，但是一开始不要把所有边都建立起来，当厨师做好第K个人的菜的时候才加入第K+1个点

1491: [NOI2007]社交网络

Flody求最短路数量

2208: [JSOI2010]连通数

缩环后$O(n^2)$暴力找

1076: [SCOI2008]奖励关

记忆化搜索，设$F[i,S]$表示 i 轮过后拿到的奖品的集合状态为 S 时的期望最优值

3668: [NOI2014]起床困难综合症

分位考虑

1499: [NOI2005]瑰丽华尔兹

DP+单调性优化

1797: [AHOI2009]Mincut 最小割

在残余网络上跑 tarjan 求出所有 SCC，记$id[u]$为点 u 所在 SCC 的编号，显然有$id[s] \ne id[t]$

①对于任意一条满流边$(u,v)$能够出现在某个最小割集中，当且仅当$id[u] \ne id[v]$

②对于任意一条满流边$(u,v)$必定出现在最小割集中，当且仅当$id[u]=id[s]$且$id[v]=id[t]$

1977: [BeiJing2010组队]次小生成树 Tree

MST建出来后倍增维护树上路径最大值和次大值

1017: [JSOI2008]魔兽地图DotR

DP套背包，$F[i,j,k]$表示以 i 为根的子树+向上传送 j 个物品+花费 k 的最大攻击力

3224: Tyvj 1728 普通平衡树

Treap

3223: Tyvj 1729 文艺平衡树

Splay

2120: 数颜色

用树状数组套主席树维护$next[]$，$next[i]$表示右边最接近的和i同色的下标

1251: 序列终结者

Splay

2818: Gcd

欧拉函数

2588: Spoj 10628. Count on a tree

树上遍历套主席树，同“BZOJ3123：森林”

2152: 聪聪可可

一遍树DP

2179: FFT快速傅立叶

这是道模版题

3110: [ZJOI2013]K大数查询

权值线段树套区间线段树

1901: Zju2112 Dynamic Rankings

树状数组套主席树

3196: Tyvj 1730 二逼平衡树

上题再加个 Splay

3289: Mato的文件管理

莫队，用树状数组维护区间逆序对个数

2049: [SDOI2008]Cave 洞穴勘测

LCT 模版题

2631: tree

LCT+Splay

3669: [NOI2014]魔法森林

LCT 动态维护 MST

先把所有边按 a 为第一关键字从小到大排序，对于一段相同的 a 查询 1 点到 n 点在 MST 上的瓶颈边

2594: [WC2006]水管局长数据加强版

也是 LCT 动态维护 MST

离线逆序操作，就变成加边维护MST

1507: [NOI2003]Editor

Splay

1269: [AHOI2006]文本编辑器editor

Splay

3676: [APIO2014]回文串

回文树乱搞

3555: [CTSC2014]企鹅QQ

Hash 一边就完事

1566: [NOI2009]管道取珠

要求$\sum a_S^2$，我们可以看成是 A B 两个玩家分别完成游戏后获得的字符串相同的方案数

设$F[o][i][j]$为当前取了 o 颗，A 在一管取了 i 颗，B 在一管取了 j 颗，且两人所得到字符串相同的方案数

3139: [HNOI2013]比赛

记忆化搜索，Hash去重（去重的状态：有i个人互相都没安排的时候剩余未安排分数）

3931: [CQOI2015]网络吞吐量

最短路后直接网络流