给出一个有向图。求最小链覆盖。 　　首先说两个概念：　　　　链：一条链是一些点的集合，链上任意两个点x,y，满足要么x能到达y，要么y能到达x。　　　　反链：一条反链是一些点的集合，链上任意两个点x,y，满足x不能到达y，且y也不能到达x。　　这题就是求最长反链长度。　　有两个定理：　　最长反链长度=最小...

　　一棵树上，一开始所有的边权值为1，我们要支持两种操作：　　1.　修改某一条边的权值为0　　2.　询问根节点到某一节点的路径权值和 　　前置技能-dfs序相关　　然后差不多你就会了。　　dfs序+线段树搞定了。 #include<cstring>#include<algorith...

　　有一个有向图，每一个节点有一个权值，其中有一些结束点。　　现在，你要从S出发，到达任意一个结束点，使得经过的节点的权值和最大（可以重复经过某一个节点，但是权值只记入一次）。 　　小码农题。　　如果有强连通分量，那么之间的点是可以全部拿到的，傻子才不拿。　　所以先Tarjan强连通缩个点。　　然后就是一个D...

　　有m个题目，有n个解决方案；对于每一个题目，有两种解决方案可用。　　每种解决方案只能用一次，问最多可以通过最前面的几题？ 　　几乎是裸的二分图匹配。　　每个题目两条边，分别连向所对应的两种解决方案。　　然后跑匈牙利算法。具体可以看这里，往后翻就有匈牙利算法的解说。　　可怕的是，我之前以为是最多可以通过几道...

　　给出一堆串，然后求一个包含这些串的所有串的最短的中的字典序最小的。 　　先造一个AC自动机，多模匹配嘛。　　然后bfs在AC自动机上面走，两维状态，dis[i][j]表示已经走到过的串状态为i，在AC自动机上面的位置为j的最短距离。　　然后这题居然要卡空间！　　坑死了。　　然后用了short　　wa掉了。...

 　　把一个数m拆成很多数字。　　问至少拆成多少个数字，1~m中的所有数字才可以用这些数字的和表示。 　　这个让我马上想到了有限背包的一种做法。　　其实是很像的。　　算一算二进制位数就可以了。　　具体拆成哪些数：比如x在二进制位数下有y位，那么就拆成：2^0,2^1,2^2,...,2^(y-2),...

　　以距离为第一关键字，字典序为第二关键字，在所有的从S到T的路径中，选择不重复经过某一节点的第k条路径。 　　第k短路模板题。　　A*跑一跑就可以了。UPD(2018-08-24):　　这题是以前坑下的。就让他坑着吧。要做k短路的读者请移步BZOJ1975魔法猪学院 　　这后面的东西就不要看了吧&...

  给定n组整数对（Xi,Yi），当Xi<Xj且Yi>=Yj时，如果对于任意的Xk，有Xi<Xk<Xj，Yk严格小于Yj，则称Xi是Xi到Xj中最牛的点。例如4个整数对（2002，4920），（2003，5901），（2004，2832），（2005，3890）,则可以说&l...

　　硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。 　　一开始没看数据范围，觉得是类似状压的dp。　　然后看了看数据范围，懵逼了。　　然后发现可以写容斥！　　我们先当作完全背包，不考虑限制，把花费每...

　　有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。所有油漆刚好足够涂满所有木块，即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。 　　一开始想状压dp，压每种颜色的剩余数。　　发现要超时...

 　　有n只牛，有m个羡慕关系。　　羡慕关系具有传递性。　　如果A羡慕B，B羡慕C，那么我们认为A也羡慕C。　　问有多少牛被所有其他牛羡慕。 　　这次做这题我已经是第三遍了。　　USACO经典老题啊！（奶牛）　　POJ上面也有，叫popularcow。　　做法：　　先Tarjan强连通缩个点。　　然...

 　　给出n个模式串，问长度为m的串中有多少个至少含有这n个模式串中的任意一个。　　注意，所有的串仅由A~Z26个大写字母构成。 　　AC自动机好题。　　先构建一个AC自动机。　　然后在AC自动机上面跑dp。　　建议开滚动数组。　　dp[i][j]表示长度为i，在AC自动机上面走到了j的方案数。　　...

 　　扫雷。只有2行。第2行没有雷，第一行有雷。告诉你第二行显示的数组，问有几种摆放方式。 　　动态规划。　　用dp[i][0][0]表示当前位置为0，前一位置为0的方案总数，　　用dp[i][0][1]表示当前位置为1，前一位置为0的方案总数，　　用dp[i][1][0]表示当前位置为0，前一位置...

 　　（其实是复制的）　　给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。bcdcdcdcd可以压缩为b...

 　　折叠的定义如下：　　　　1.一个字符串可以看成它自身的折叠。记作S　　　　2.X(S)是X(X>1)个S连接在一起的串的折叠。　　n<=100.让你求折叠之后的最小长度。 　　（据说字符串的题有通用做法？——hash+乱搞？？）　　首先预处理出从第i个位置开...