硬币购物一共有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个...

 　　这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。　　输入：第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过3276...

 　　现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。　　答案对于31011取模。 　　先考虑错误的prim——　　这个是我的第一感，拿到题目，...

 　　求区间[A,B]中有多少数满足下面的条件。　　条件：该数相邻两位之差不小于2。 　　简单的数位dp。　　一个记忆化dfs就解决了。　　dp[i][j]表示剩余i位数，第i+1位为j的windy数总数。　　太简单了，不会的话自己看代码。1#include<cstring>2#incl...

　　有n个东西，k次扔出来。每次等概率扔出其中一个。　　你可以拿这个东西，但是有条件，得在拿到指定东西之后再拿，否则白拿。　　拿到一个东西，会获得其权值。可以是负数。 　　状压dp跑一发。　　一开始想写正着dp的，因为我觉得这样听挺容易想的。　　然而网上的大牛都说是倒着的。于是我倒着了。　　方程是这样的：　　...

 有n个人，每一个人有一个最恨的人。并且，每一个人有一个权值。一个人不可以和他最恨的人同时被选中。现在请你求出在这n个人中选出一些人，使得其权值和最大。（题解在“心塞史”后面）  注：蒟蒻第一次遇见这种基环树题QAQ。 先看样例。3102203301&nb...

 　　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i)0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么？（1<=N<=2,000,000,000...