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

　　有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个位置开...

 　　在n*n的棋盘上面放k个国王，使得他们互相无法攻击，问有多少种摆法。 　　dp[i][j][x]表示前i行，状态为j，总共放了x个国王的方案总数。　　然后简单的转移一下即可。　　当然这样要炸。　　只需要在这之前把每行的合法情况筛选一下即可，这样的情况总数不到100。　　然后就可以了。 ...

 　　有一个n*n(n<=200)的01矩阵，问你是否可以通过交换整行和整列使得左上角到右下角的对角线上的数字都是1。 　　我们发现，题目模型可以转换。　　其实题目就是叫我们求是否存在一些1，这些1所在的行和列互不相同。　　我给一个小小的证明：　　假设我们选出了一个n个点的坐标。　　如果这n个...