emmm...

暴力打得好，Rating少不了！

T1：一个贪心。只要清楚 $Sum(i,j)>Sum(i+1,j)$ 并且会使用结构体优先队列就好了。

T2：树形dp。设 $dp[i][j]$ 表示节点 $i$ 上的数为 $j$ 时的方案数。那么显然有： $dp[i][j]=\Pi_{v=son(i)}(\sum_{k=1}^{j-k}dp[v][k]+\sum_{j+k}^{m}dp[v][k])$ ，注意 $k=0$ 时特判一下。这样我们就有 $40%$ 的分数了。（好了以下没写出来参照题解）我们又发现对于一个节点，它的 $dp$ 值与 $k$ 有关， $k$ 有多大，一开始就会有多少不一样的，而后面的式子是对称的，所以是相同的。那么最大只有 $(n-1)*k$ 个不同的，时间复杂度 $O(n^2+k)$ ，空间也不会爆，过掉。

T3：毒瘤题，只会暴力。据说是一道 DP+二分+二维RMQ+卡常 的毒瘤题。贴一篇大佬的题解

后记

$100+40+15=155$ 这种垃圾分数都能Rating+19...建议退役果然大佬们都太强了不屑于和屑Crab一起打比赛/kk...

版权属于：Crab_Dave

转载时须注明出处及本声明