CF练习

19

[CF757D] 注意m不会超过20,以及最后一个求和的意义就是插版数目无限制,dp[i][S] 表示前i个数,在第i个数前插一个板,出现数的集合为S的方案数,枚举下一个点递推
[CF757E] 发现$f_0(n)=2^{p(n)}$ p(n)为n的质因子个数,发现$f_r(n)$积性,发现$f_2(p^n)=n^2$,发现其他$f_r(p^n)$是$f_2$的差分或前缀和,没了,这里哪有dp……
[CF696D] dp[u][l]表示经过l步走到ac自动机结点u的最大值,转移可以(+,max)矩乘倍增
[CF662C] 我是想来做点dp的……怎么做到了一道FWT…… Fast Walsh-Hadamard Transform
[CF467E] 每次加进去一个数贪心,判断方法是维护一个栈,加入的时候把到上次出现相同的数之间打上可行标记,来的时候判一下
[CF778C] 等会证复杂度了再来补题解 嗯……就是启发式合并啊…… dfs的过程中不断合并子节点,合并两颗trie的复杂度是min(sz),因而是O(nlogn*26)的
[CF600E] 一个挺有用的科技,会专门写一篇
[CF375D] 怎么讲……我越来越觉得这东西就是启发式合并了……dsu on tree
[CF715C] 原来树上启发式合并……也可以做点分治做的东西阿……这个dsu……和启发式合并差不多阿……
[CF494C] 区间之间有包含关系提醒我们可以见一棵树,然后显然区间中的最大值才有用。如果自顶向下发现难以dp。于是可以用dp[i][j]表示i的子树中最大值增长<=j的概率,考虑一下儿子们就可以转移了。想这种不满足加法的期望,往往要枚举取值计算概率来算期望。考虑某个东西恰好为k,或者<=k,转移转移……。
[CF28C] 水dp,dp[i][j][k]表示前i个房间进了j个人最大值为k的概率,枚举下一个房间人数转移
[CF300D] 应该注意到递归层数相同的n本质上是相同的,接着是四个东西的卷积的形式,k^2做一下,没了
[CF76F] 推一推式子可以得到两个个带绝对值的不等式,变换一下坐标系可以把角度变为直角,两个纬度就不相关了,求一个LIS,p.s.要让一个点一定出现在lis中,求一下它前后的dp值
[CF727F] 倒着dp,dp[i][j]表示i..n删除j个数所需最小前缀,回答的时候二分就好了
[CF235C] sam,把TT在sam里跑,像lcs一样记录一下当前最长能匹配多少,>=len的时候把答案算进去
[CF781C] 最近有点忙…… 随便做一棵生成树,dfs一下就没了
[CF781D] 倍增
[CF781E] 考虑到每个线段只生成两个点,使用数据结构维护l<=x<=r && h<=h'+s' 的点集,再考虑h单调递减,前面用vector套起来,再用一个线段树维护最小值以快速找到一个可行点,没了 [CF771E]n^2 dp很容易想到,考虑优化 对于一个确定的i找到最小的j使得dp[i][i]+1 = dp[i][j] 这个可以O(1)

在 “CF练习” 上有 1 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注