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

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

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

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

　　给一棵树，你可以匹配有边相连的两个点，问你这棵树的最大匹配时多少，并且计算出有多少种最大匹配。　　输入格式：　　　　第一行一个数N，表示有多少个结点。　　　　接下来N行，每行第一个数，表示要描述的那个结点。然后一个数m，表示这个结点有m个儿子，接下来m个数，表示它的m个儿子的编号。　　　【数据规模】　　　　N&le...

 　　有一棵树，每一个节点都有一个权值w[i]。下面说的x,y都是该树中的节点。　　对于点对(x,y)，x,y，保证x和y距离为2，那么他们就可以联合，会产生w[x]*w[y]的联合权值。　　注意：点对(x,y)和(y,x)是不同的。　　现在要回答两个问题：　　1.所有可以联合的点对的最大联合权值。　　2.对...

【问题描述】有两个仅包含小写英文字母的字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串，然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串，请问有多少种方案可以使得这个新串与字符串B相等？注意：子串取出的位置不同也认为是不同的方案。【输入格式】输入文件名为substring.in。第一...

 写在开头的话　　转眼之间，又是一年。2016年是个忙碌的一年，这一年身边发生了很多事，我多么希望能够像事务（Transaction）一样，执行完成之后能够保持一致性与持久性，可惜事与愿违，现实总是很残酷。虽然发生了很多事，想表达的也很多，但是等到自己想去写的时候却发现好像也没什么可写的，自己那点伪文青气息仿...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ440.html菜鸡选手到省选了才做联赛题。首先我们分析一下性质：1.假如一个格子是0，那么它的右上角一定是0。2.假如一个格子的左边和上面两个格子一样，那么从这个格子到终点的任何两条路径相同。不难发现，对于第3个斜列，我们发现这个斜列至少有一...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ129.html　　考虑把大于等于$sqrtn$的质数和小于$sqrt n$的分开考虑：　　1.小于等于$sqrtn$的质数最多只有8个。　　2.一个小于等于n的正整数最多包含1个大于$sqrtn$的质因子，所以不同的这种质因子可以分...