Posted on 2012-05-12 21:41
Mato_No1 阅读(2895)
评论(6) 编辑 收藏 引用 所属分类:
APIO
【dispatching】
(这题国内数据极弱,暴力能80,下面的解法1,平衡树即使用Splay Tree实现都能AC)
枚举管理者所在的结点,然后在这个结点及其所有后代中找到权值前K小的,使得它们的权值和不超过限制,要求求出K的最大值。
解法1:将每个结点及其所有后代的权值存在一个平衡树里,然后,对于每个结点,若不是叶结点,就将其所有的子树中,找到最大的那棵子树,它所表示的平衡树不动,将其它的子树表示的平衡树上的所有结点强行拆开,并插入到这个子树表示的平衡树中(这叫启发式合并),别忘了将该结点本身也合并到这棵平衡树里。合并好了以后,通过每个点记录的sum(下面说明),用类似于求结点排名的方法,就可以求出K的最大值了。
容易证明,这样合并的话,在整个过程中插入的次数是O(NlogN)的,加上平衡树插入本身的O(logN),总的时间复杂度为O(Nlog
2N)。
具体实现起来有一些技巧:
(1)可以发现,在合并过程中,各个点本身并没有变,而只是它们之间的关系发生了变化(从不在同一棵树上变成在同一棵树上了),因此为了节省空间,可以预先将所有的结点建好,每个结点除了自身权值以外还记录mul(初始为1)、sz(初始为1)、sz0(初始为1)、sum(初始等于权值)等信息,其中mul为重复次数,sz为考虑mul情况下的树的大小,sz0为不考虑mul的情况下的树的大小(也就是实际结点个数),sum表示树上所有结点的总权值(这个当然要考虑mul了)。之所以维护sz0,是因为每次可以通过找到sz0最大的子树不动来加速。插入的操作是void ins(int r, int No),表示将结点No(是结点不是值)插入到以r为根的子树里,注意这个结点No的mul可能大于1,因此在插入后维护的时候需要注意;
(2)由于在过程中会同时有多棵平衡树存在,因此每个点还需要记录一个额外的域rf,rf=-1表示该结点不是任何一棵平衡树的根结点,rf>=0表示该结点是原树中编号为rf的结点表示的平衡树的根结点,同时记录root[i]表示结点i表示的平衡树的根结点编号,这样就可以很方便地实现树内外的对接(注意这两个值的维护,尤其是将结点i本身合并到平衡树里的时候,别忘了把root[i]改掉)。
解法2(正解):合并的时候使用可并堆(用左偏树或斜堆实现),时间复杂度O(NlogN)。
【guard】
(这题其实很容易想到网络流的话说……不过仔细研究一下就可以发现,由于报告上来的只是某一个区间内有木有人,而不是有几个人,因此无法用网络流的流量平衡来表示)
首先,某些区间报告木有人,这些区间内的点肯定不符合要求了,可以将它们删掉,然后对于剩下的(可能是若干段)区间,合并起来,对结点从左到右重新编号(这一步可以用线段树,也可以排序后直接扫描,见
这里,本沙茶比赛时为了省事直接上线段树了),然后就只需要考虑那些报告有人的区间了囧……当然,这些区间的端点也是要对应地重新编号的,编号完了以后,将所有包含别的区间的区间删去(因为它们的存在木有意义),方法:对于所有重编号后的区间,将其按照先左端点递增,后右端点递减排序,然后设置一个栈,保证栈中的区间左右端点均严格递增,按照排序之后的顺序扫描每个区间,每次一个新区间入栈时,栈顶所有右端点大于等于这个新区间右端点的区间出栈,再将新区间入栈,这样最后栈中的区间就是保留下来的区间了囧……而且已经排序……
然后,如果问题是求至少要多少个人的话,就是一个经典的贪心模型了,扫描排序后的区间,如果一个区间内还木有任何人,就在它的右端点处放一个人。显然,除了这些放了人的区间的右端点之外,其余的点肯定都不是必须放人的(因为现在已经有一个方案使它们不放人了)。现在的问题是,这些右端点处是否必须放人。
设F[i]为第i个区间及其之后的区间当中,若要每个区间内都有人,至少要几个人。若第i个区间的右端点不小于最后一个区间的左端点,则F[i]=1(在第i个区间右端点放一个人即可),否则,找到最小的j,使得第i个区间的右端点小于第j个区间的左端点(这个显然可以二分查找得到),则F[i]=F[j]+1。这样从后到前推一遍即可。然后,再从前到后,按照上面的贪心算法的流程扫一遍,如果遇到第i个区间的右端点需要放人:若第i个区间的长度为1,显然这里必须放人,否则尝试在第i个区间的倒数第2个位置(即右端点之前的那个位置)放人,而右端点不放人(可以证明,不会后来又把这个右端点这里放上人的),类似用二分查找的方式找到这个j,然后看一下(_F + F[j] + 1)(_F为第i个区间前面放人个数)是否大于K,若大于K,则第i个区间的右端点必须放人,否则不必须放人。
此外还有两种特殊情况,一是M=0的时候在去包含的时候要特判一下(其实这时可以直接特判,若N=K,则所有的地方都必须放人,否则就是-1);二是,如果去掉那些肯定木有人的点后,剩下的点的个数刚好等于K(不可能小于K的,因为肯定有解),则不用贪心了,剩下所有的地方肯定都必须放人。
总时间复杂度O(NlogN + MlogM);
这里千万要注意的一点是,应该先将所有区间重编号再去包含,而不应该先去包含再重编号!!!因为可能有两个区间本来是不包含的,但重编号以后,包含了。(本沙茶比赛的时候就是这里木有注意到,跪了3个点,杯具了)【kunai】
40分的暴力做法:枚举两个动点,求出它们是否会相撞以及相撞的时间,然后将所有相撞事件按照时间排序,扫描排序后的每个事件,如果相撞的两个动点都还在,就将它们消去,然后可以求出每个动点移动的距离,求一下并集(线段树)即可;(本沙茶当时主要是实在木有时间写这题了,因此连暴力都木有写)
AC做法:很明显,一个动点一旦被消去,就不会再次出现了,因此对于每一个点,只需要找到最先和这个点相撞的点即可。显然能够相撞的两个点必然位于同一行/列/对角线上且方向满足一定限制(其实一共只有6种情况:同一行一种,同一列一种,同一左上右下对角线两种,同一右上左下对角线两种)。因此,枚举这6种情况,直接用扫描法得到最先与它相撞的动点,取相撞时间最小的那个即可,如果都找不到,这个点就是永存的。这样相撞事件的总数就减少到了O(N)级别,总时间复杂度就是O(NlogN)。
注意:有可能在同一时间有多个动点在同一位置相撞,因此,对于同时发生的相撞事件,应该将它们一起处理,涉及到的点一起消去。