AC自动机 + 变进制状压DP
看题目的 discuss 都说会卡数据，但我还是 1500ms A了。虽然变进制的思路并不是我的……
最近有点懒得写博客了呀
题意：
还是基因碱基对背景。
给你几个模式串，再给你一个匹配串，允许你对匹配串重新排列，要求重新排列后跟模式串匹配的最大数量。
思路：
如果再加个权值，那就是DP套DP了，（误……
本质上还是一个计数DP，考虑状压，但是给定的匹配串长度上限为 40 ，如果开一个状态+节点的 5维数组，会炸内存。
考虑到将节点的 4 维压缩，因为 40 的实际状态数最多是 4 个碱基数量相同的时候。
也就是( 10 \times 10 \times 10 \times 10 )，内存与复杂度均可以承受。
AC Code
#include
训练赛的DP套DP，关于DP套DP，以前记得好像做过一道。题目本身十分巧妙，但貌似不是很多。可能不是很好出题吧。
所谓DP套DP，就是我DP所需的状态也需要额外的DP求出来。简单说，就是我需要DP两次，在第一次的DP结果上再DP一次。
题意：
给你一个DNA序列，再给你一个固定长度，问你在这个长度下的所有序列中，与给定的DNA序列的LCS分别为( [0,len(DNA)] )的序列数量。
思路：
因为数据很小，我们可以考虑用状压做。
对于当前长度的一个最优状态，如果增加一个字符，它的下一个状态就需要加上当前状态的序列数量。
这是一个非常常见的计数DP。
但是已知当前状态，无法直接得出下一个状态，而这个就是我们需要嵌套在内的DP了。
我们枚举每一个状态，在枚举每一个字符，使其插入当前状态，再转移它的LCS，最后再统计一下就可以了。
而统计方法是如果当前位置的LCS与前一位置的LCS不同，则说明这个位置与LCS的DNA序列匹配。
虽然我说的很简洁，但是我当时也是想了好长时间……
AC Code
#include
CLS的状压DP系列……
然而实际上也算是一道简单题，但是我并没有立刻写出来。
不知道为什么，每次我尝试这用已知最优状态去推其他状态都是错的……
然而用当前状态之前的状态来推当前状态却是对的。
顺便学习了一个，二进制子集的枚举方法。for ( int sta = state ; sta ; sta = (sta - 1) & state )
学了这么久状压居然连这个都知道真是醉了……
题意：
给你一个字符串，每次只能取走一个回文串，问最少取几次。
思路：
先预处理出所有状态是否为回文串，并使得 这个状态取值为 1 。
枚举每个状态，再枚举它的所有子集。
状态转移方程 为 dp[sta] = min(dp[sta], dp[sta ^ s] + dp[s] )
AC Code
#include
LCA 好题！ 这道题我暂时只知道用Tarjan的解法。 Tarjan解法完美地运用了Tarjan的核心原理与性质： 深度优先搜索时的向下局部性。自己乱取得，蛤蛤蛤 题意： 给你一棵树，每个节点有一个权值。给你很多个询问，每个询问两个点。要你在给定点的树链上找到有序的最大差值。 思路： 首先考虑分治。设树链 u -> lca -> v 答案无非只有三种情况： 1. u -> lca 的最大差值 2. lca -> v 的最大差值 3. lca -> v 的最大值 – u -> lca 的最小值 考虑dp维护这四个值。 因为运用Tarjan算法的时候，基于dfs，在你的眼里，当前节点就是向下整棵树的根节点，你完全不会去考虑往上的节点。 所以你现在使用的四个值，刚好是你当前节点的孩子节点的最优值。 基于这个事实，…
K短路裸题。 这里的K短路是基于每个点只能访问一次，也就是说这个K短路必须是一条链。 再换句话说，这个K短路的K是有限制的，如果超过了这个限制，就输出 -1 。 这是和之前多校的次短路不一样的地方。 简单说一下K短路的解决思路： 首先我们应该认识到，最最简单的最短路算法是基于 bfs 改进而来，我们用 bfs 的思路继续拓展，在第一次到达终点后并不停止，而是继续 bfs 搜索，直到第K次到达终点，就是我们要求的答案。 当然，单纯的 bfs 是瞎 jb 搜，堆优化的spfa效率良好，但我们可以更进一步优化。 K短路于此之上还用了 A* 优化，先对反图 最短路遍历一遍，在正图遍历的时候，除了对起点 src 到当前距离 堆优化以外，还对当前距离进行答案估计，并将其优先级先于距离。 仔细想一想，其实很显然，不过为什么最短路不用 A* 优化呢？ 因为有处理估值函数的时间，最短路都已经求完了。…
树上的选择性DP…… 不是很懂其他人的做法，偶然间看到有人用ruby A了，我也就用ruby敲了一蛤 速度有点玄…… 题意： 给你一棵树，每个节点都有权值，要你求每个节点到根节点所形成的树链 gcd。 其中每条树链都可以选择一个节点使得权值变为 0 。 思路： 感觉这就是裸题…… 只不过就是把数组改成树上了而已。 用一个栈或者队列去遍历这棵树，对于每个节点是否变0都考虑一下就好了…… AC Code #!/usr/bin/env ruby # encoding: utf-8 n = gets.to_i a = gets.split.map(&:to_i) g = Array.new(n) {[]} (n-1).times do u, v = gets.split.map(&:to_i)…
后缀数组之重复次数最多的连续重复子串 这道题真的是做的我脑壳疼…… 口误，根本不能算是做，死嗑论文怎么也嗑不出来…… 好难，这应该是我现在做过的后缀数组里最难的一题了…… 这里放上我理解之后的思路： 首先枚举长度 l ，如果存在两个长度为 l 的连续重复子串，那么在 ( str[ 0 ] , str[ l ] , str[ l \times 2 ] ) …… 中必然会存在两个相邻的位置他们值相同（加上这个优化，速度可以大幅度提升），我们对这两个位置的后缀求最长公共前缀 lcp ，那么显然，由这两个位置得出的子串重复次数为 ( lcp \div l + 1 )。 但是这个答案并不一定是正确的，因为我们只能确保 ( str[ 0 ] , str [ l ] , str[ l \times 2 ] ) …… 中会出现重复值，但是这几个是边界。 由kuangbin大佬给出一个想法是考虑 ( lcp % l ) 的含义。( lcp…
后缀数组之可重叠 k 次最长重复子串。
数据好水……他的 “ 字符 ” 范围为 ( [ 0 , 1e6 ] )
按我最开始的想法，求后缀数组的时候，在字符最大值超过 char 我就打算用 sort 代替基数排序了。
然而……直接取最大值用基数排序居然过了，还是 63 ms ……
下面是可重叠 k 次最长重复子串的求法：
解法与不可重叠最长重复子串的做法基本一致。
二分答案，将排序后的后缀按照二分值分成若干组，如果某一组的数量大于等于 k ，那么这个二分值是可行值。
题意：
可重叠 k 次最长重复子串。
思路：
见上。
AC Code
#include