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。
评论 (0)
