Be responsible for yourself
2020.11.12
CF1016F Road Projects
巧妙思维题,考虑将1到n的链作为主链,剩下的点作为子树
可以证明对于任意询问,u,v都相同
若任意一棵子数上点数超过1,则可以从第二个点连向主串,不会对询问造成任何影响
若只存在大小为1的子树,考虑与另一子树连边或者与主链上最近的两个点连边,而两子树连边的状况考虑直接保留贡献最大的子树,O(n)更新
- 若不存在子树,则查询和最小的两条邻边
CF1082F Speed Dial
Trie上dp,考虑状态$f[u][j][k]$:以u为根的子树中,在u到根的子树上选取的最近的点的距离,字数内选择k个点的最大优化(dp数组存优化幅度,最后用答案减)
P1436 棋盘分割
状压,考虑竖直砖的上一半为1,其余状况均为0,可以表达所有状态
2020.11.13
CC-H Misha and Gym
平衡树维护翻转,bitset维护多重背包
CC-H Pruning Trees
预处理两点能否作为拆分后某一棵树的直径(注意总长度小于等$2d$不一定正确),然后dp,状态:$f[u][A]$表示以点u为根的子树内A为u所在拆分后树的最深点时的最小代价.考虑是否必须拆当前边进行转移
2020.11.14
CC-M I Hate Symbo-LIS-m
定义$len$为$lis$长度
对于一个点对$x,y$,当且仅当$x
CC-H Pizza Tossing
- 法1:手动高消
- 法2:结论
类似如下的问题有固定结论
简单描述为猴子打字,大概形式为在一个字符范围内随机增加字符,求最后$k$个字符为某一字符串时的期望打字数
结论:设$f[i]$表示当前已经打的字符串中后$i$个字符与目标串匹配时达到最终状态的打字期望数,$p$为字符集大小,$fail$的定义与$kmp$中的定义相同,均表示最大失配指针