solution 有两种解法。 解法一：分组背包，相当于有3种物品，分别有个，重量分别是。问不能组成的最小的重量。 用表示这个重量能不能组成。 然后将分组背包拆成01背包做。 枚举一下重量，看是否能组成。 解法二：生成函数。用表示选择1能组成的方案。用表示选择2能组成的方案。用表示选择5能组成的方案。然后将他们相乘。最后找到最低的系数为0的项即可。 /* * @Author: wxyww * @Date: 2020-04-16 14:37:23 * @Last Modified time: 2020-04-16 15:23:07 */ #include<cstdio> #inclu...

solution 此题有两种解法。 第一种解法就是裸的完全背包。 就相当于有n种物品，第i种物品的重量是i。每种物品有无限多个，问恰好填满一个容量为n的背包的方案数。 第二种解法是生成函数。 用生成函数表示拆分出的的数量。用表示拆分出的的数量。剩下的同理。最终的系数就是答案。 code 解法1 /* * @Author: wxyww * @Date: 2020-04-16 14:18:39 * @Last Modified time: 2020-04-16 14:19:55 */ #include<cstdio> #include<iostream> #include&...

solution 其实就是要求一个最大的x使得。 显然当x增大时答案会变小，具有单调性，所以考虑二分答案。 二分一个x，检查答案是否大于等于K即可。 code /* * @Author: wxyww * @Date: 2020-04-16 11:12:25 * @Last Modified time: 2020-04-16 11:15:09 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #in...

solution 该博文刚写完，就不小心手残清空了，只好重写。 生成函数练手题 先写上这个式子 题目中描述了两种限制。  第一种限制：神石的块数必须是的倍数，那么他的生成函数就是。这就相当于用替换掉了上方式子中的。所以该生成函数就是 第二中限制：神石的数目不超过，那么他的生成函数就是。我们将其看作。第一个括号里的内容就是，第二个括号里就相当于将最上方的式子每项都乘以。所以第二个括号里的内容就是。所以该限制的生成函数就是  然后将所有的限制用生成函数描述出来，并相乘，所得多项式的第项就是答案。 这10个限制的生成函数相乘为 约分一下发现就是。 由广义二项式定理 所以第n项的系数就是 n比较大，用...

solution 枚举一个为0的位置，然后想办法统计该位置产生的贡献。显然，一个为0的位置产生的贡献就是它前面1的个数。 如果位置为0，那么他前面共有种可能的序列，每种序列都有个数字，那么总的数字数量就是。显然的，这些数字中0和1的数量应该是相等的。所以其中1的个数就是。然后考虑后面的位置共有种可能的序列，所以x位置产生的每个贡献都有中可能的排列。那么总的贡献就是 所以最终答案就是 code /* * @Author: wxyww * @Date: 2020-04-15 11:57:07 * @Last Modified time: 2020-04-15 13:54:57 */ #includ...

solution 枚举起点和终点的LCA，然后将他们两两组合即可。 具体的，设f[i][0/1]表示以i为根的子树中，与根节点i的距离为偶数(0)奇数(1)的点的数量。 转移显然就是。 然后考虑统计答案，以为的两个节点，肯定不能在的同一个儿子里，所以转移的过程中,表示已经当前已经计算过得儿子造成的贡献，对于一个新的儿子， code /* * @Author: wxyww * @Date: 2020-04-14 11:33:18 * @Last Modified time: 2020-04-14 11:39:50 */ #include<cstdio> #include<ios...

solution 计算区间异或和可以利用前缀异或和计算。因为n只有，所以只要在复杂度内解决就好了。 然后考虑如何保证区间不相交。枚举一个点。用表示右端点小于等于x的区间中异或和为的区间数量。然后枚举一下左端点大于x的区间，如果该区间的异或和为那么就将答案加上。 code /* * @Author: wxyww * @Date: 2020-04-13 16:06:54 * @Last Modified time: 2020-04-13 16:21:01 */ #include<cstdio> #include<iostream> #include<cstdlib&g...

solution 经典的的方式。 转化一下题意就是:选一个根，使得所有叶子节点到该节点路径上最小边权之和最大。 先考虑的做法 用表示以1为根时i这棵子树内的答案。那么就有。 所以枚举一下根，然后每次这样dfs一遍，就可以在时间内解决问题了。 考虑优化该算法 我们只要在以1为根做一遍上面自下而上的dp之后，在做一遍自上而下的dp就可以转移出以任何一个点为根时的答案。转移方程就是:，表示在自下而上的dp过程中，v对于u的贡献。 code /* * @Author: wxyww * @Date: 2020-04-12 20:30:52 * @Last Modified time: 2020-04-1...

迟到1h，险些掉分，呼~ A 数据范围很小，模拟签到题。 /* * @Author: wxyww * @Date: 2020-04-10 19:52:33 * @Last Modified time: 2020-04-10 20:02:50 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<a...

solution 首先单独考虑蓝色和红色的染色方式。 如果只染蓝色（红色）和绿色，我们枚举一个蓝色边的数量x,然后方案数就是。所以总的方案数就是。 然后容斥合并蓝色和红色的方案。枚举蓝色和红色边重复的数量x,那么答案就是。所以最终答案就是 注意到上面求单个的过程是的。预处理f数组的复杂度就是。所以考虑用更优秀的方法求f。 将f打表如下:   找规律或OEIS发现递推式:。然后就可以线性预处理了。 总复杂度 code /* * @Author: wxyww * @Date: 2020-04-09 15:26:44 * @Last Modified time: 2020-04-09 19:30:3...