登录后台

还没有账号?注册一个吧(>ω・*)ノ

页面导航

本文编写于 201 天前,最后修改于 201 天前,其中某些信息可能已经过时。

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

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

已有 1 条评论