Bzoj 2434
题意：见上。
先介绍 Trie，Trie图，Fail树
将字符串插入 Trie 即可得到下图
将失配函数连上，得到Trie图
Trie图可以将字符串问题转化为图论问题，具体可以看Bzoj 2938
将原边删掉，失配边反向，得到Fail树
Fail树每个点的祖先节点都是这个点失配后可以走到的点。
对于AC自动机中的每一个节点，如果节点A的失配边指向节点B，就会发现B对应的字符串一定在A对应的字符串中出现，那么在Fail树上显然可以利用这一性质。
考虑暴力，即在Fail树上往上跳。
我们还可以离线，将$y$相等的并成一块，一起处理，能过$70$分。
逆向思维，我们考虑对于每个$x$去找$y$，那么标记一下$y$能跳到的点，求子树和即可。显然可以树状数组维护DFS序。
而这样还是不能通过。我们发现每次初始化$y$能跳到的点进树状数组时，时间开销非常大。我们考虑边加边统计。
我们在原Trie树上DFS，将当前点$u$根路径上的点标记为$1$，然后再Fail树上求每个$u$对应的询问的$x$的子树和即可。
bzoj 2938
题意：见上。
将AC自动机的Fail指针都连上，那么就形成了一个Trie图。在Trie图上找到一个不含危险点的环即有解，否则无解。
找环即用Tarjan的思想，模拟一个栈
知识点：
1、Trie图的运用
2、DFS找环
BZOJ 2559
题意：给一棵树，每条边有权。求一条简单路径，权值和等于 $K$，且边的数量最小。
点分治模板题，但是这里维护的是不可加信息，不能用容斥的方法，我们求每个点的值的时候按一定顺序遍历他的儿子，然后将前面的存起来供后面的合并(类似树直径DP)，然后就不用考虑容斥了，都是可行的合并。
Luogu 3674
题意：给你一个序列，长度为$n$，有$m$次操作，每次询问一个区间是否可以选出两个数它们的差为$x$，或者询问一个区间是否可以选出两个数它们的和为$x$，或者询问一个区间是否可以选出两个数它们的乘积为x ，这三个操作分别为操作$1,2,3$。选出的这两个数可以是同一个位置的数
无修改无强制在线，则离线即可。
给出了值域范围，那么就是让我们记录这些值
考虑如何记录。可以开桶来记录。但是这里我们并不需要知道某个数出现了几次，只需要知道有没有即可。对于这种01数组，我们可以想到bitset
设维护值域下的bitset为$\operatorname{bs}$
对于询问一个$x=a-b$，那么就相当于bs & (bs >> x)不为假。可以当做一个平移的感觉。
对于询问$x=a+b$，我们可以维护一个反的bitset，然后达到将其左移后能和原来正着的bitset有值的效果，具体可以模拟一下。
对于乘法，直接$\sqrt x$枚举即可。
知识点：
1、Bitset 左移右移 技巧
2、乘法复杂度分析
BZOJ 3410
题意：有一个长方体，有一些格子上有$1$，你可以进行$k$次操作，每次选择一个长方体区域$(x,y,z)$，代价为$\min(x,y,z)$，可以将这个区域所以$1$改为$0$，求最小的$k$使得整个长方体都为$0$
先是要发现代价为$\min(x,y,z)$其实就意思是，我们选择一个代价不为$1$的操作，都可以转化成若干代价为$1$的操作，并且答案不会更差。所以这题就是一个三维的poj 3041。
然而三维并不能三分图，那么我们发现题目给的数据范围$A\cdot B \cdot C \leq 5000$，那么必然有一个数小于$\sqrt[3]{5000} \approx 17$，所以我们假设$A$就是这个最小的数(不是的话可以交换坐标，几何意义就是将长方体换个方向)。那么暴力枚举每一层是否操作，然后再将另外两维做平面上最小点覆盖即可。
知识点
1、隐含小数据：乘积
BZOJ 1503
题意：见上。
发现是每个数加上某个数或者减掉某个数，可以想到用一个全局增量$\Delta$来维护。
刚开始想到后面的人不能增了然后就不会了…其实后面插进来的减掉当前的$\Delta$就行了。
查询就直接查，删数方法比较好，就是先插入一个$\operatorname{mind}-\Delta$，然后将$-INF$所在点转到根，再将加入的点转到$INF$的孩子，然后左子树直接打标记删除即可。然后再将加入的$\operatorname{mind}-\Delta$删掉。
知识点：
1、每个数加上某个数或者减掉某个数，可以想到用一个全局增量$\Delta$来维护
2、Splay 删子树方法
3、全局增量$\Delta$的应用
BZOJ 1854
题意：第 $i$ 天的股票买入价为每股 $AP_i$，第 $i$ 天的股票卖出价为每股 $BP_i$, 股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 $W$ 天, 在任何时间，一个人的手里的股票数不能超过 \text{MaxP}。在第 $1$ 天之前，有无限钱，但是没有任何股票，求 $T$ 天以后最大收益。
容易设$dp(i,j)$为前$i$天有$j$股票的最大收益
则分情况讨论
1、买入股票
$$
dp(i,j)=\max_{k \in [j-AS[i], j-1]}(dp(i,j), dp(i-w-1,k) + AP_i (k-j))
$$
2、卖出股票
$$
dp(i,j)=\max_{k \in [j+1,j+BS[i]]}(dp(i,j), dp(i-w-1,k) + BP_i (j-k))
$$
3、什么也不做
$$
dp(i,j)=\max(dp(i,j), dp(i-1,j))
$$
初值：
$$
dp(i,j)=-AP_i \cdot j
$$
其中$0 \leq j \leq AS_i$
其余均为$-∞$
然后考虑优化
我们将$i,j$看作定值，则将与$k$无关式子移到$\max$外面，发现这可以单调队列优化。
2219
题意：在$n \times m$的矩阵中找出一块$a \times b$的矩形，在这个矩形中找出一块$c \times d$的矩形(必须在内部)，得分为$a \times b$的矩形分数减去$c \times d$的矩形，求分数最大的$a \times b$的矩形，输出分数。
细节题
这题感觉类似Bzoj 1047，问法类似，并且都是压缩了一段区间然后边成序列问题。
这题可以考虑枚举每个$a \times b$的矩形，然后每次在矩形中找出一块分数最小的$c \times d$的矩形(注意必须在内部)，然后减掉即可。
1、 先预处理$n \times m$的矩阵的二维前缀和
2、 然后预处理每个$((x,y) | x+c \leq m, y+d \leq n)$为左上角的$c \times d$的矩形的分值和记为$S(x,y)$
3、 对于每个$((x,y) | x+c \leq m, y+d \leq n)$，记录
$$
C(x,y)=\min\limits_{1 \leq i \leq a - 2 -c +1}S(x+i-1,y)
$$
这个相当于把这个$a \times b$的矩形的一列决策点都压缩成一个元素
4、对于每行$(x | x+a-1 \leq m)$, 每列$(y|y \geq 2, y+d-1\leq n)$，单调队列记录
$$
\min\limits_{y \in [y-(b - 2 - d + 1 + 1), y]}C(x+1,k)
$$
然后得到了最小值，按上面方法计算即可
( 范围什么的还是自己算算吧，太杂乱了可能上面的公式会有错误
2219
题意：见上。
考虑错误的解法(没有考虑一个景点走一次)，即枚举主人的路线，然后枚举一个可行景点给狗走。
但是如果一个景点走一次，这个方法就是错误的，因为枚举的可行景点之前可能已经被走过了。
那么这样的话，意思是一个地方有多个选择，最多选一个，求所有地方选的最大值。
转化成图论，发现是个二分图，而这就是二分图最大匹配。输出方案就输出连边的方案即可。网络流做法即找有流量的地方
Codeforces 1117D
题意：一列魔石排成一排，一块魔石可以分裂成$m$块魔石，你可以选择任意魔石进行分裂，求最后$n$块魔石的方案数。$n \leq 10^{18}$
可以发现组合数公式，即选择出魔石出来分裂，但是并不能通过。
可以考虑DP($n \leq 10^{18}$也是可能DP的，小心，矩阵快速幂)，设$dp(i)$为$i$个未分裂魔石时的方案。则
$$
dp(i)=dp(i-1)+dp(i-m)
$$
那么就可以矩阵快速幂了。
Codeforces 1117E
题意：现在有一个长度 $\leq10000$ 的字符串和一个位置上的双射 $f$ ，使得字符串 $i$ 上的字符换到 $f(i)$ 上来。
交互题其实就是数字游戏……
把题目里的数字拿出来，即$3,26,10000$
考虑关系，则发现$26^2\leq 10000 \leq 26^3 $
就考虑如何一次交互如何扩大 $26$ 倍
以下转载自题解 CF1117E【Decypher the String】 - sysjuruo 的博客 - 洛谷博客
我们可以通过以下方式
第一次:
aaa...aaa(26∗26)bbb...bbb(26∗26)ccc...ccc(26∗26)...
我们称 $26 \times 26$ 个为一个大块
第二次:
aaa...aaa(26)bbb...bbb(26)ccc...ccc(26)...
第三次:
abcdefg...xyzabcdefg...xyz
这样，对于一个位置$i$，第一次我们可以知道 $f(i)$ 属于哪一个大块，第二次可以知道属于哪一个小块，第三次便可以知道属于哪里
我们称 $26$ 个为一个小块
知识点：
1、$n \leq 10^{18}$也是可能DP的，小心，矩阵快速幂