THUSC2012

JOI2015 OPEN

__Shi posted @ Sun, 14 Jun 2015 20:43:54 +0800 in Other Contests with tags JOI2015 , 298 readers

STERILIZING

陈题,线段树上暴力修改即可。特判$K=1$。

ELECTION_CAMPAIGN

考虑$O(n^2)$ dp。$dp_{u,k}$表示以u为根的子树中当前k可达的最大获利。

可以简化为一维的状态。如果选择一条LCA为当前点p的路径u->v,只需要把p->u和p->v路径上的支路上的dp值求和。

树链剖分维护即可。

COLORED_TILES

Subtask1

随机获得18pt.

因为颜色只有3种,$H=7$,可以状压dp。但复杂度较高。在比赛结束前20分钟终于跑完了,但在输方案的时候segmentation fault了。。。然后就作废了。。。

Subtask2,3,4,5

直接贪心按行放,每次对每种颜色进行简单的估价,选择最优的一种颜色放。最后再一波随机就可以过了。

blog comments powered by Disqus