2019暑期金华集训 Day7 动态规划
自闭集训 Day7
动态规划
LOJ6395
首先发现这个树的形态没啥用,只需要保证度数之和是\(2n-2\)且度数大于0即可。
然后设\(dp_{i,j}\)表示前\(i\)个点用了\(j\)个度数的最小值,然后就获得了\(O(n^3)\)的DP。
不妨每个点的度数都减1,那么总度数就变成\(n-2\)了。
考虑原来\(i\)的作用是什么:要限制选的点数不能超过\(n\)。
此时我们总度数小于\(n\),所以只要度数不为0的点的总度数不超过n-2那么就肯定有点数不超过n。所以我们可以先认为所有点贡献的都是\(f(1)\),然后如果选的是\(k,k\ne 1\)那么就把贡献设为\(f(k)-f(1)\)。
于是就可以直接设\(f_i\)表示当前度数之和为\(i\)的最大贡献,然后做一个完全背包即可。
LOJ2552
设\(f_{i,j}\)表示\(i\)当前还剩\(j\)血的概率,那么锁定技能就相当于一次转移。
那么最后的询问就没了,非常简单。
那么每一次询问呢?我们关注的只是第\(i\)个人存活的概率,设为\(p_i\)。
那么每个人被命中的概率呢?设\(g_j\)表示除了自己以外还有\(j\)个人存活的概率,发现就是个背包,直接硬上分治FFT可以得到70分。
当然,我们可以先把一整个背包算出来再退掉当前物品,就\(O(Cn^2)\)了。
CF53E
容斥,求至少\(k\)个叶子的方案数。
枚举叶子集合,用剩下的点组生成树,然后把叶子挂回去,复杂度\(O(2^nn^3)\)。
然后用FMT优化容斥,没了。
UOJ129
发现满足\(x^2\le 500\)的质数只有8个。
于是每个数只会有这几个质数和另一个大质数作为因子。
把所有数按大质数排序,然后连续一段就必须放在同一个集合(或者不选)。
然后设\(f_{i,S,T}\)表示前\(i\)个,\(S,T\)里面分别有哪些质数,乱DP即可。
某题
选一些位置,使得这些位置不相邻。相邻定义为八连通。
题解是插头DP。
(没怎么听清题,但大概不难)
UOJ266
发现删掉一条链之后必然会变成几个子树,于是可以设\(f_x\)表示\(x\)子树的sg函数值,然后暴力枚举删子树内哪个点,就获得了多项式时间的算法,应该是\(O(n^2)\)的。
如何优化?
设\(g_x\)表示\(x\)以及自己儿子的\(f\)的异或值,然后发现删掉一条链就是这条链的\(g\)的异或值再异或掉根的。(大概意思就是这个,可能表述得不是很清晰)
于是对子树内维护一个字典树支持插入、全局异或、求mex、合并,就没了。
NTF随手切掉了清华集训题目,NTF进清华了,NTFAKIOI!!!!
某题
平面上\(2n\)个球(球的位置两两不同),有\(2n\)个机器人位于\((0,i),(i,0)\),每次激活一个机器人拿走它坐标轴垂直方向上最近的球,问有多少个方法拿走所有球。
把每一行、每一列视作一个点,一个球作为一条边,边权为\(x+y\),那么激活第\(i\)行的点的时候就会取走与他连在一起的边权最小的边,列同理。
所以可以知道每个连通块点数等于边数,也就是一个基环二向树。每个点要恰好选一条边,并且选边的方法受上面的限制,然后求这样选边的顺序的个数。
树上每个点选的边是确定的(自己到父亲的那条边),但环上有两种情况,所以先枚举是哪种情况,然后每个点要选的边就确定了。
在树上,看儿子要选的边与自己要选的边的边权大小关系,如果比自己的小那么就必须先选,这样一路DP上去。
在环上,看自己左右两条边的大小关系,如果自己要选的边权更大那么就必须另一个点比自己先选,就形成了一些小于号的关系,也用组合数算一下就没了。
AGC007D
设\(dp_{i}\)表示喂完前\(i\)个熊,并且当前位置在第\(i\)个熊那里,的最短时间。
然后枚举上一次,有两种情况:直接走回去走回来或是要在那里等一下。
显然可以单调队列优化,就没了。
bzoj2216
决策单调性,大家都会。
四边形不等式
如果对于任意\(i_1\le i_2\le j_1\le j_2\),都有
\[
w(i_1,j_2)+w(i_2,j_1)\ge w(i_1,j_1)+w(i_2,j_2)
\]
那么就满足决策单调性。
LOJ566
枚举中位数\(w\),把一条边拆成两条:\(w-a_i,a_i-w\)(分别是白黑边),再两个都加上\(w\),就变成了\(2w-a_i,a_i\),然后就是要求一棵恰好\(n/2\)条白边的最大生成树。
这个直接wqs二分可以得到,于是得到了\(O(m^2\log^2 m)\)的做法。
然后有一个结论:对于最优的\(w\),这个生成树只包含\(a_i\ge w\)的黑边和\(a_i\le w\)的白边。(???)
考虑wqs二分的过程,是要把\(2w-a_i\)变成\(2w+k-a_i\),发现这样一来我们可以不枚举\(w\)而直接二分\(2w+k\),然后就没了。
(???)
咕了
LOJ565
我们发现进位一次1的个数就少1。
于是题目就转化为求最后1的个数的期望。
于是操作的顺序与答案无关。
对于每一位,求它的贡献。
从后往前DP,记\(dp_{i,j}\)表示第\(i\)位算上进位叠了\(j\)个1的概率。
转移有两个。一个是由上一位进位而来,是\(dp_{i-1,j}\rightarrow dp_{i,j/2}\);一个是在这个位置的操作,相当于乘\(px+1-x\)的多项式。
直接暴力DP是\(O(n^2)\)的。
发现乘多项式可以分治FFT,而一个位置如果加了\(w\)那么只能往前进位\(\log_2 w\)个位置,于是每个位置可以只处理有值的最大地方,然后就可以证出复杂度是\(O(n\log^2 n)\)了。
最新文章
- css009 装饰网站的导航
- Hibernate个人学习笔记(1)
- linux命令:cp
- 【WEB】原理 之 线程池
- 看文档要看仔细,英语要加强啊... cocos2d-x 的 API 和 对应版本的 cocos2d-js 的 API 没有完全对应
- plsql编程中游标的使用
- 基于visual Studio2013解决算法导论之030二叉查找树
- VBS基础篇 - 杂项 - Sendkeys
- 3.1. 修改托管对象模型(Core Data 应用程序实践指南)
- LVS集群TUN模式实例(5)
- C++基础——类封装简单示例
- Activi相关表归纳
- python中执行py文件出错(提示File “<;stdin>;”,line 1,SyntaxError:invalid syntax)
- C# 自定义异常的方法源码演示及说明
- python技巧 一等函数
- 027 Spark的优化总结
- 关于ubuntu下看视频中文字幕乱码的问题
- el 表达式 强制类型转换
- c# 简单日志记录
- 解压zip,解决中文乱码