daily acm training record
之前的东西太多了,没有记录
简单欧拉函数板子题,只要枚举因数进行计算即可。
通过定义生成格雷码就行了
开始学习基础树形dp
有依赖的背包类似P2015
入门级树形dp
树形dp水题
入门级树形dp
读题题
树形dp水题
achieve:昨天vp计算几何补题,7个入门树形dp
tomorrow plan:学习容斥原理和莫反,继续刷入门树形dp,有空的话vp一场cf
看了一天容斥原理,发现非常得难,开始了递归学习。
学习容斥原理和莫反,继续刷入门树形dp,有空的话vp一场cf
依旧是看了一天得容斥
vp了一场
莫反入门题
莫反入门题
莫反+容斥
换根dp
莫反入门题
区间dp
莫反+数论分块
积性函数+枚举素因子
循环矩阵的性质
fft板子
树形dp基础题
树形dp要点思维题
带权并查集板子
lucas板子
图上概率dp
前缀和简单题
简单dp
考虑每一层的数字,暴力更新
开始复健一下简单题
简单dp
简单bfs
简单dp
记录前驱的简单dp
打了cf1789
但是因为太久没有做题,C题读错题写了40分钟,然后D出了思路没时间写了。
VP2020济南
同时开始写一写稍微难一点点的题
二进制数位dp
考虑到某个数字加m如果不进位的话只能让后面的7位二进制发生变化,如果进位的话将产生进位,但也只有一次,记录连续的1的个数就可以计算出来进位的贡献了。 所以使用数位dp,dp到后7位时暴力计算方案,暴力计算方案的时候考虑是否产生进位。并分类讨论即可
黑白染色之后构造分类方式
读题之后发现,如果有某一位两个点都是0那么这两个点必定没有边,通过这个性质,对这个树进行黑白染色。 黑白染色之后,同色点之间必定没有边,那么使用两位二进制就可以把同色点全部分开。然后还剩下一些边为不相邻的黑白点之间的边,因为黑色点和白色点总和为n,那么必定有一种颜色的点的个数$< =\frac{1}{2}$对于点数较小的集合,按照标号依次分配二进制位为0。对于另一个颜色的集合,其在分配的二进制位中只有与其相邻的异色点对应编号的二进制位位1,其他均为0。
注意到上取整和下取整最多相差1,然后进行分类讨论。
如果上取整和下取整相同,那么
注意到只要没有1,除一下上取整30就很小了 但是犯病了,取min的时候没更新导致惨案
闵可夫斯基和板子