2020-CCPC-秦皇岛站 -(F,K)题解(10.18)

发布于:2021-09-28 11:56:51

F.题: 给定n个人,给定m个朋友关系,然后选x个人,如果x个人中,有k个朋友关系那么+k分,每出现一个人减1分,总价值 k-x

题意很清晰啊,思路就也很清晰了。把一个人看成一个节点,一个朋友关系就是一条边。选择x个人,也就选中了x个节点,这些节点的所有边就是k。总价值 k-x。
那么怎么让k-x尽量大呢。随手画个草图就知道了。


结果非常的amazing啊。 孤立的点,或者树形结构价值都是-1。简单来说就是连通块中的边数小于点数,价值显然为负。而只要连通块中有环!价值就大于等于0。


也就是说,只要找到一个环,那么这个连通块的就全选。可以简单证明以下,如果存在环,说明这个环的价值为0。那么其他所有和这个环连通的点,就算只有一条边,价值也是+1-1 = 0,不会减小其整体价值,如果有大于一条边连接这个环,那么就可以增加这个环的价值。所有有环的连通块,全选!反之,全不选。总价值,就是选中的 边数-点数。


K.题:给定一颗树,跟节点上有无数个军队。军队所向披靡,每到一个节点就可以占领一个结点。但是国王每天只能命令 一只军队,行进一个单位距离。问,多少天可以占领所有的节点。

思路:
对于一颗给定的树,先求他所有子链长度,如果某个子节点也有m棵子树,那么取这个子节点最长的子树。并且对所有子链长度排序。什么意思呢。


如下图:
节点旁边就是他的所有子链的长度。

然后就可以愉快的计算答案了。


对于每一个节点,要走完所有的子节点,就有一个问题,因为根节点有无数个军队。也就是说,某个军队可以走完一条路之后就不动了,从根节点再派一支军队过来。或者让某一支军队从上一次的地方回来,再继续走下一条支链。这就有两种选择,要么回收上一次的军队,也就是让他走到回到当前节点,或者直接从根节点派一个军队到当前节点,结论显而易见,谁更短选谁嘛。这段话啥意思呢。见下图:


显然先派一支军队走到2然后走到3,然后顺着最短的支链走到底。也就是最左边的支链。这时,3号节点还剩下三条支链,改怎么走呢。刚刚的结论,如果上一条支链的长度小于当前节点到根节点的距离,就把上一次的军队回收回来嘛。代价为1,然后去走第二条支链。剩下两条。走第三条支链的时候,不管是回收还是从根节点派代价相同。走最后一条支链的时候,就要考虑了,从上一条支链回收军队的话代价为3,而根节点的距离为2,那么显然选择从根节点派军队啊。于是这颗树的总代价应该为:1+1+1+(1+2)+(2+3)+(2+4)

再来看看样例给的树:

显然遍历4号节点的两条支链时,回收第一条支链的军队,代价为 1+1+1+1+(1+1) = 6

相关推荐

最新更新

猜你喜欢