大概好久没写blog了，这么多天的一下补完吧。

BZOJ3991: [SDOI2015]寻宝游戏 可以发现最短路应该是按照有宝物的点的“轮廓”走，会发现其实dfs序就是按照“轮廓”走的。所以把全部点按照dfs序扔进set，直接维护即可。（我想要强行维护虚树是不是没救了…

BZOJ3990: [SDOI2015]排序 可以发现每种操作方案操作执行的顺序不一样也可以，而且每种顺序操作位置是唯一的，这样如果知道这类方案总步数为$s$，那么这类方案对答案的贡献为$s!$。对于两类不同的方案，是指都按照$1$到$N$顺序操作，存在某个操作两个方案执行的位置不同。既然每类操作顺序无关，可以从第$1$种操作考虑选不选，或者操作位置在哪。选择方式也很显然如果第$i$类操作后，把数组分成$2^i$段，每段是连续的即为合法操作。仔细分析后发现对于当前数组最多有2种操作位置（比如说”1 4 3 2”有两种方式），所以递归时最多有$2^N$种情况，每层递归需要扫描一遍数组。总复杂度$O(2^{2N})$。

BZOJ3992: [SDOI2015]序列统计 神题！最裸的dp显然可用$f_{i,j}$表示选择了$i$个数字模$M$时乘积为$j$的方案数，复杂度$O(nm)$。转移可以用矩阵做，快速幂加速，复杂度$O(m^3\log n)$。自己重新定义矩阵的“乘法”，即直接将两个数组乘起来$retk=\sum{i+j=k}a_i*bj$，复杂度降为$O(m^2logn)$。最厉害的是分别把下标用$G^k \mod M$表示，其中$G$为$M$的原根，$G^k$构成了简化剩余系。这样$ret{G^k}=\sum{i+j=k}a{G^i}*b_{G^j}$，直接用指数来替换原来的下标，这个时候是卷积的形式，FFT加速，总复杂度为$O(m\log^2n)$

BZOJ3676: [Apio2014]回文串 嗯，直接用回文树来做吧，回文树讲解。恩…我不太会构造奇偶串的情况，就直接加分隔符，统计的时候注意下是不是分隔符。我不太理解用hash怎么统计出现次数。

BZOJ4003: [JLOI2015]城池攻占 树链剖分然后在线段树上倍增，还是T掉了，本地造数据似乎只慢了2~3倍的样子，也不知道是不是哪里虚掉了。还有一种做法是离线，接着每个节点维护一个可以攻占到这个节点的将军的堆。选取此时战斗力最小的测试是否会被干掉。每个节点的堆可有由儿子节点合并而来，注意每次向上走一步对于堆内全部节点的战斗力影响是一定的，所以可以打lazy标记。学习了左偏树（想起了大叔的话：左偏树应该是最好写的数据结构了吧

BZOJ4002: [JLOI2015]有意义的字符串 欺负我没有上过高二…

2015-6-3 21:53:24 ：咦。。。还有好多没补，我要回寝睡觉。。。明天继续补