首页 > 代码库 > 集训 0620

集训 0620

T1:

要求你在一颗树上做背包,并且遍历这棵树的每个节点,内存要求不能超过20M。

嗯...很坑,在写了分块之后,我发现被卡了,O2下1.2秒正好,非O2下3秒左右,时限1.7秒,哔了狗了。

能得60也是托了数据过水的洪福。

正解:这题本质是要求你确定一条树上的欧拉路径,并且使每次同时维护的未遍历的链接口最少。

初步观察发现,如果一条长路一条短路,先走短路比先走长路优,因为长路上并接很多链接口的可能性很大。

然后可以判断初步策略是每次走siz(dep也可以?)域最小的子树,经过一番调试,发现真的如此。然后就写出来了。

证明的话,应该可以像证明树链剖分那样证明.....吧。

T2:

线段树题目,批量升级的套路,我有个地方打残了,结果只混了暴力分,稍改两个地方就是正解的说....

没什么可说的,只需要注意线段树的标记维护即可。

T3:

题答。

简单暴力生成树随便跑了下贪心就过了94,唉...

 

不得不说数据过水了。

集训 0620