Codeforces 620E New Year TreeCodeforces 121E Lucky Array我来安利一道题.Codeforces 620E New Year Tree给一棵树,每个点有个颜色,支持对子树进行覆盖,询问子树中含有多少种不同颜色.颜色最多60种.如果没有修改操作,可以使用莫队,但是这里有修改操作,不能使用莫队.那么还剩...

文章目录题意题解problem redive题意求字符串中每一个相等前后缀的长度以及其在全字符串中出现的次数.题解本题非常精妙.首先思考求长度.可以使用kmp和哈希算法,但是哈希不能求出出现次数,因此被消灭了.那考虑kmp解决第一个问题.kmp中的next数组表示的是全字符串的第i个前缀中前后缀的最大匹配长度.对于全串来说,长度为lenlenlen肯定是符合要求的,而next[len]next[l

题意不愧是神场,据传Div.2E做出了TC Div.1 1000的赶脚,而这题做到了.题意问有多少张符合下列条件的无向图:1.每个点的度都是固定的,为2或者3.2.每一个点到1号点的最短路有且只有一条.3.令i为1->n-1中的任意一个点,必须满足i到1的最短路小于或者等于i+1到1的最短路.你在路上如果真的能够遇到八九寺真宵,那你可能也是个怪人...

第一次做线段树优化dp.没想到div.2的D这么难,以后真的要退竞了.题意将一串数字分为k个连续区间,使得每一段中出现数字种数的总和最大.做法我们先来思考一下裸的dp.定义dp[i][j]为前i−1i−1i-1个数分割为jjj份的最大值.因此有代码dp[i][j]=max(dp[k=1 to i][j-1])+sum(k,n);/*此处的sum(k,n)是k ...

前言具体内容cctypedequestringalgorithmctimestringstream总结前言c++的奥秘无穷,和数学一样,永远值得我们去研究.我也只能略举一二,如果这对你没有什么用处,请点击右上角的那个×.×.\times.具体内容我先打个备注:如果你发现你的c++使用了这些函数以后CE报错,那可能是你没有开c++11.有一些...

文章目录题意题解好好的状压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​