「Adera 6」杯省选模拟赛 Adera6

OI - Official

From lydrainbowcat


小时

尚未报名

进程分配 16/37 From
出逃的小猫 3/23 From
网络升级 14/31 From

题解:

第一题,贪心+set

按照优先级从大到小排序,然后依次往CPU中放。对于一个进程,如果它是“急需处理”的,那么把它放到已有进程数<k的CPU核心中已有进程数最多的那个里(如果不存在<k的随便放就好了……);如果它是“可以稍后运行”的,那么把它放到还没有放满的CPU核心中已有进程数最多的那个里。

第一种放法是为了让某个CPU核心“尽快到达k”,这样后面就可以满足“可以稍后运行”的任务的要求了。第二种方法就是把前面的位置留给"急需处理"的任务。于是我们拿一个set维护就好了。

第二题,枚举+线段相交+排序+栈

这题我们首先2^10枚举一下哪些木桩被拔掉了,然后处理出来多边形和那条竖直线的每个交点上面第一个木桩是哪个。然后我们按照多边形读入的顺序处理每条边(看做一端开一端闭的线段),维护一个栈,如果这条边穿过了竖直线,那么检查一下栈顶是不是当前这个交点上面第一个木桩,是的话出栈,否则把这个木桩入栈。最后检查一下栈是否为空就是是不是被木桩挂住了。

第三题:求直径+树状动规

先两次bfs求出直径。然后我们找到直径的中点(如果有两个中点随便找一个就好),这个中点距离直径较远的一端的距离设为Dfar,距离较近的一端的距离为Dnear。

构造一个以这个中点为根(记为Root),【所有距中点Dfar或者Dnear的点   到中点的路径上的】点和边   构成的树。设在这棵树中,Root的直接子节点有s1,s2……sn。我们称某个以si为根的子树是“被砍断”的,当且仅当它所有的叶子节点均不和Root联通。处理"砍断"所需的最少价钱可以TreeDp。

如果Dfar=Dnear,那么s1~sn这些子节点所在的子树中至多只能有一个“不被砍断”。如果Dfar>Dnear,那么等于Dfar的肯定只有一个子树,我们要么把它“砍断”,要么"砍断"所有等于Dnear的子树。两种方案取min。