Leaf Partition
好题,考虑树形$DP$,我们要划分叶子,所以可以记录以$i$为根的子树被几个叶子延伸,可以分成 $0/1/>=2$ 三种情况考虑。
卡牌
好题,给出的数是质数,可以想到筛法,
本题的正解需要从暴力开始考虑,直接根号分治。
还有另一个解法需要用到 FWT ,可以自行学习。
跑步
简单题,而且做法很多。
根号分治,分为两部分用不同的 $DP$ 解决,最后用乘法原理组合。
其它做法看题解。
树
简单题,有一点偏数学。
本题条件是恰好,我们用容斥原理解决(准确点是子集反演),$DP$ 状态变为属于。
一直在你身旁
简单题,显然购买电线可以看作决策,那就是区间 $DP$,
考虑优化,很明显决策点具有单调性,直接上单调队列即可。
本题有点卡常,可以先枚举右端点,再倒叙枚举左端点来 $DP$。
不难发现区间值为两小区间中较大的加上决策点的值,我们用单调队列维护最小值即可。
注意及时踢出不合法解。
Centroid Probabilities
组合数学题,具体过程 ,
小 N 的独立集
本题$k$很小,考虑$dp$套$dp$,
首先最大独立集是一个经典问题,本题再套一层$DP$来计数,
然后就是一个树上背包,$O(n^4k^4)$,考虑优化,由于我们的状态枚举了 $v1, v2$,
然而 $v1, v2$ 的差值不会超过 $k$,所以可以状态优化,加判$0$跑得飞快。
Svjetlo
很有意思的一道题,本题是经典的以树上路径为状态,求的是最短序列,还能往返走。
不过可以将往返走用讨论的方式简化,不需要担心后效性。
然后呢,我们发现想要在$DP$中将两颗子树的贡献合并很困难,可能出现多个端点的情况,
由于一个路径最多只有两个端点,所以我们按照路径有几个端点在子树中的情况设三个状态机即可。
数列
计数$DP$,由于本题可以进位,所以从低位开始$DP$,
显然$dp$状态中要有$S$从低到高的前$i$,已经确认了$j$个序列$a$中的元素,$S$从低到高确立了几个$k$,要进几位一。
转移的时候从最后一步出发,注意系数带组合数,需要预处理。
由于本题状态数很多,初始状态的细节较多,而且所以更适合用刷表法。
注意最后还要将0~k
和p=0~n>>1
的答案都累计进去。
这么水我都要想这么久,还需要努力呀。
恨7不成妻
发现本题要输出具体的数,而且还要平方和。
感觉直接平方不好想,于是先考虑整数和。
由于数位$DP$的本质是在不同深度的数($10^{pos}$)上跑$DP$然后再$DP$(我通常用记忆化搜索),
感觉算具体的数也是有可能的,去维护$3$个指数的答案就行,
整数和可以递推,合并信息就$× i^{pos-1}$,平方和也可以用已知信息递推出来。