4
28
2015
0

APIO

BZOJ1178: [Apio2009]CONVENTION会议中心

 

题意就是求区间图字典序最小的最大点独立集。n<=20W

区间图的最大点独立集只要按右端点排序之后从左往右能选就选。

但我们要求字典序最小的答案。字典序最小的方案的通用解法就是依次把1到n试图往解里面加,看看会不会使最优解变差,不会就加入,否则放弃。

如何看最优解是否变差呢?

不放认为我们当前可用区间为(l,r)完全包含(a[i].l,a[i].r)(如果不存在这样的(l,r)显然不能插入)

那么令函数calc(x,y)表示x-y最多选多少条线段。

只要有calc(l,a[i].l-1)+1+calc(a[i].r+1,r)=calc(l,r)那么我们就可以加入,因为最优解没有变差,仍然是calc(l,r)。

那么加入之后就把原来的(l,r)分割成了(l,a[i].x-1)和(a[i].y+1,r)这两个可用的区间。然后依次做下去即可。

找这些区间以及插入什么的可以用set来完成。

接下来考虑如何计算calc函数。

先将区间端点离散化是一定的。然后那么一个区间如果被另一个区间完全包含,那该区间一定比另一个区间优。

于是我们把完全包含其他区间的区间去掉,然后这样左端点和右端点都是不减的。

我们倍增预处理出f[i][j]表示在i位置要覆盖2^j条线段的话,右端点最近在哪里。

这样calc(x,y)就相当好算了,从大往小能跳就跳。正确性其实也非常显然,因为我们相当于加速了x=f[x][0]+1这个过程而已。

这种倍增预处理用于快速回答区间询问的方法真是赞~ 不过以后碰到类似的题目能不能想到这种方法就是另一说了

 

BZOJ1179: [Apio2009]Atm

 

这题好久以前就做过了。tarjan缩点之后拓扑序DP一下就好了。

 

BZOJ1177: [Apio2009]Oil

 

上午搞了两个小时,一直不懂为什么要这么做。心情十分郁闷中午回家补了两集DATEALIVE之后心情好多了

 

题解君

我们先把a[i][j]定义成以他为右下角的k*k的正方形的权值和,然后问题就变成了在一个(n-k+1)*(m-k+1)的格子里选择三个两两横纵左边的差的较小值大于k的权值和最大的点。

然后我还是不会做

但是枚举这6个真的完全计算出了符合条件的所有情况。

比如 上面两个和下面一个情况,我刚开始想下面那个也可以在中间啊,然后发现在中间的时候如果在两个的中间就变成了左中右的情况,如果是在某个的一边就变成了另一种左2右1或者左1右2。

我考场上反正想不出这种做法,放弃治疗。给APIO的题跪了。

这题TM有毒,搞了我一天我也不知道怎么想出来的。

 

UPD:这里的方法比较好理解,戳这里  Regina8023

 

BZOJ1912: [Apio2010]patrol 巡逻

 

K=1的话显然就是选择最长链,因为我们总可以构造出一种方案让他们少走最长链的长度。

K=2的话脑补一下我们发现就是选两条不相交的链使得长度和最大。求这个我们可以先找一遍直径,然后把直径上的边都赋成-1,再求一遍直径。

       为什么这样就是对的呢?加入第二条链与第一条不相交,显然选了两个最大的。否则如果相交的话我们正确的计算出了两条不相交链的长度和。

       并且这第二个长度越大越好。所以肯定是我们要的ans。

Category: APIO | Tags: | Read Count: 893

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com