AC自动机+状压DP的入门题 虽然不是很好意思，但我的确是先看了kuangbin的代码再敲的。 从AC自动机构建矩阵开始起的出现的那个结点状态，在之后做题中越來越显著。 因为AC自动机本身也没多少地方可以改了，这是一个成熟的算法。而考研我们的运用就只能在理解熟悉它的状态，并运用它的状态。 关于状态应用最明显的就是DP了。 这题之后尽量不看题解…… 说了一堆废话，下面放题解。 题意： 有一个长度为 n 的密码，给你一个 m 个字符串的集合。告诉你这个密码必定会包含这集合中的 k 个。 问密码的种数。 思路： 这道题应该是给出一个状态就很好理解了。 开一个三维数组，记 ( dp\left[ i \right] \left[ j \right] \left[ k \right] ) 为长度为 ( i ) ，在第( j ) 个结点，含有字符串数量的状态为 ( k ) 的可构字符串数量。 每次在AC自动机上跑的时候更新一下状态，最后再将包含字符串数量大于等于 k…
昨天晚上从Yasola那里偷来的一道题…… 为什么Yasola这么优秀啊！！！！！ 求求你别学了，我已经完全跟不上了…… 因为看着题目并不是很难我也就写了一蛤，然后自以为是无脑题就疯狂WA…… emmmm…… 其实仔细想想还是挺简单的。 题意： 给你一张无向图，要你找出最小环。 点数 ( n \leq 100 ) 思路： 对 floyd 进行简单增加一点代码。 floyd 算法剖解开来就是不断找到一个中间结点使得路径更短。而我们可以在这个中间结点加入最短路之前，将其固定为环上的一个点，这点必定不会被所有最短路夹在中间。 有一个非常显然的问题就是，当我固定一个中间结点的时候，我无法保证我所用的最短路为全局最短路。这个问题显著存在于floyd初期。 比如说 存在一个 ABCA 的环与一个 BCDB，其中 ( BD + DC < BC , AB + AC < BC )，而当我使 A 为固定结点，而我的 D 还不曾成为固定结点，也就不会被加入 BC 的最短路。 然而实际上并不要担心，…
昨天的多校有一道需要树Hash的基础，于是就找到了这题。这题应该算得上是树Hash的裸题了。 树Hash的方法其实十分简单。有兴趣的看一下我的这篇 博文 然而上面那片博文是定根结点的，如果根节点固定，对于树的形态进行Hash，实际上是非常简单的。 再次简单说一下树Hash的原理，对于有根树，我们Hash的是树的形态，而树的形态则有每一层的结点个数与结点所连接的相同父亲结点所决定。 因此我们对于同一层的并且是同一个父亲的结点作一个相同的Hash，那么就得到了我们要得答案。 不过也有一个简单也正确的写法，就是将同一层并且具有相同孩子结点数量作同一个Hash，也可得到我们想要的结果。 但上述方法是针对有根树而言，如果不定根，则不好判断。 这是我们可以对小数据选择枚举所有结点，对较大数据选择寻找树的重心(不会超过两个)。 下面放上题解。 2017-8-14更新： 该理论用于有根树已经被推翻，对于无根树，也就是这道题，莫名适用，也许是数据水…… 题意： 给你( n ) 棵树，每棵树用给定每个结点的父亲予以表示。问对于每一棵树，与它同构的并且序号最小的是哪一棵。…
做的第一道AC自动机非模板题，感觉真的是神了。 一些AC自动机的性质自己完全不知道…… 废话不多说，直接上题解。 题意： 给你( n )种病毒，要你求出长度为 ( m ) 的不含这 ( n ) 中病毒的数量。 思路： 这道题可以转化成图论解决，当然只能是思路而已 对于AC自动机上的每一个结点，他都可以看成是一个字符串的一部分前缀，也可以认为是一个字符串的一部分后缀。 作为一部分后缀，如果我们在一直不含病毒串的同时，长度达到了要求，我们就可以将其认为是一种可行方案。 解题关键 : 离散数学上的矩阵阶乘定理 构建一个矩阵，矩阵值 ( Mat\left[ i , j \right] ) 代表的是 ( i ) 到 ( j ) 的边数。对其求 k 次幂，所得新矩阵为 ( Mat\left[ i , j \right] ) 代表的是 ( i ) 到…
其实是道板子题………… 但是AC自动机已经学会很长时间了，当学会之后一看发现高阶的应用都得和DP相结合，还有矩阵加速呀什么什么的……就没再去碰过了 结果昨天的多校的一道中等题就是AC自动机+状压…… 有点崩溃，至今的我还是基本上只会板子……所以今天在状压写累的时候开始写一下AC自动机。 顺便小小的总结一下AC自动机模板的用法和需要注意的地方。 1. 数组大小的上限与Trie相关，上限为插入字符总数 一开始我还以为是查询字符长度 2. 如果数组下标从0开始，end对数组标记需初始化为 -1 ，一般建议全初始化为 -1 3. 格外小心字符范围，一般字母26，可见字符128，而这题的范围就是 256 因为 (2^8 ) 题意： 还是有点老套的题意。简单说就是让你找出一个网站上的病毒数量，这跟之前很多模板题是一样的…… 略有不同的是这些病毒都是经过加密的，再简单说，这个加密方式只是确定的进制转化，原本是8进制的密码，现在给你6进制形式。 思路： 只要把病毒给解码出来，就是一个模板题。 当然方法各有不同，我感觉我写的略有麻烦，建议去看kuangbin的转…
昨天写状压DP被煞笔天海和死肥宅带鱼嘲笑了 Damn！ 然而事实也是一些状压DP的经典问题我还不会…… 更烦人的是今天的多校是DP专场，AC自动机+DP 这个倒是常见的套路 树形DP ，反背包DP，树上匹配+DP，各种姿势的DP…… 老实说，我的DP是很弱的……连背包问题上的我个人觉得都不是很熟练…… 这里写一下状压DP入门的三道题，三道题其实差不了多少，但在难度上基本上是循序渐进的。 POJ 3254 Corn Fields 题意： 给你一个矩阵，让你种一些玉米，要求只能在给定的格子上种，并且相邻的格子不能同时存在玉米。 问方案数。 思路： 首先在输入的时候记录一下每一行不可种植的格子，将它压缩为二进制。 再是筛选出在同一行满足条件的所有状态，因为不能存在相邻格子，也就是 ( i & ( i << 1 ) = 0 ) 枚举每一行满足条件的所有状态，进而枚举下一行满足条件的所有状态，当 ( state[i] & state[j] ==0 )时，就表示上下状态的玉米不会相邻，这两行是满足题意的，所以只要将当前状态的数量加到下一行的状态中。…
OK，被逼得去学单调队列优化的dp 单调队列可以优化的DP有一大类就是多重背包。 因为本人是个DP弱菜，建议还是看其他人的博文…… 推荐博文 点这里 Coins 是 楼教主的男人八题中可以说是最简单的一道了。 简单说就是可行性多重背包，背包九讲中有关于可行性多重背包 ( O \left( VN \right) )算法的说明，虽然点到了单调队列优化，但也只是一笔带过。 题意： 有很多个硬币，各有价值a[i]与数量c[i]，问你能构成的价值种数有多少。 思路： 这里简单说一下我对单调队列优化的理解吧 其实这里根本算不上单调队列，只能说是队列，其实就是问题被简化了。 对于每一个价值，都可以被转化成 ( d + n \times a[i] ) ， 其中 ( d \in \left[ 0 , a[i] \right) ) 简单说就同余关系啦 那么对于一个价值 k ，若…
第一次听说用单调队列来优化DP…… 只能说见得少了…… 单调队列的限制很多，我已经几百年没用它了…… 但是有一些dp问题的子问题，的确可以转化成典型的单调队列问题，用单调队列优化之，可以将复杂度下降一个数量级。 题意： 有个人看穿了股市所有行情，现在他的本金无限，问可以赚多少钱。 这里的股市限制炒鸡多。 有限制： 1. 最大所持股票数量 2. 每天最大购买量 3. 每条最大卖出量 4. 当天购买的股票必须至少 n 天后才能卖出 最后给你看穿天数，每天收购与卖出价格。 思路： 可以说是单调队列优化DP的入门题了…… 设 dp [ i ][ j ] 为第 i 天持有 j 股的收益。 则状态转移的规则就是 取 1. 不买不卖 dp [ i – 1][ j ] 2. 买入 限制下的 股数 的最收益…