文章目录题意题解好好的状压dp被搞成蜜汁贪心.题意给一些数,求能取出多少个非空子集使所有数相乘为完全平方数.n≤105,ai≤70n\leq 10^5,a_i\leq70n≤105,ai​≤70.题解707070以内的质数只有191919个,并且一个数的平方性可以用每一个质数的奇偶性判断,不妨用一个压缩状态来代表某个数的状态是否是奇数.我们对所有数取状态之后本题变为有多少个集合使状态的异或为0.列

文章目录题意dp状态寻求10月31日晚arc107真题先吐槽这一场的前四题竟然都是计数题,让我非常震惊.这是一道十分精巧的dp,对提高自身的dp实力有比较大的帮助,本人强烈推荐.题意求含有nnn个数,和为kkk,每个数都形如12i(i∈N)\frac{1}{2^i} (i\in N)2i1​(i∈N)的集合数量取模998244353998244353998244353.1≤k≤n≤30001\le

命运的选择题意神一般的过程及题解.本来有信仰用mapmapmap套setsetset跑过去的,结果调了一天都没调出来,时间还比暴力都慢.只好写线段树合并.题意给一棵树,每次用一种颜色覆盖树上一条路径.求每一个点覆盖次数最多的颜色,如果有多个颜色取编号最小的那个.给一棵树,每次用一种颜色覆盖树上一条路径.\newline求每一个点覆盖次数最多的颜色,如果有多个颜色取编号最小的那个.给一棵树,...

文章目录题意题解很有味道的一场比赛，BC两个题的想法都非常精彩。题目链接题意定义一个区间的贡献f(x)f(x)f(x)为该区间的长度乘上该区间所有数之和的符号。问将一个序列分成若干区间的贡献之和的最大值。题解首先可以写出显然的n2n^2n2动态规划做法。dpi=maxj=0i−1dpj+f(j+1,i)dp_i=max_{j=0}^{i-1}dp_j+f(j+1,i)dpi​=maxj=0i−1​