做题记录4

大概好久没写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)$。自己重新定义矩阵的“乘法”,即直接将两个数组乘起来$ret_k=\sum_{i+j=k}a_ib_j$,复杂度降为$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 :咦。。。还有好多没补,我要回寝睡觉。。。明天继续补