3
17
2015
1

论逗逼的自我修养之POI2010

最近做了一些POI2010的题,但是因为有空的时候一直在推I wanna run the Terminal,所以也就没有和以前一样实时更新博客。今天正好两部分都完结了,就顺便来给博客除除草。最后还剩下两道题就坑掉吧。。。看了一下BZ上AC提交的代码长度,我还是果断弃疗了。

 

现在做了几题

16

【POI2010】Guilds 直接DFS染色就好了,注意要特判孤立点的情况。

【POI2010】Railway NOIP那道双栈排序的加强版,一定存在方案使得第[tex]i[/tex]个数会在第[tex]\max j(a_j \leq a_i)[/tex]个数入栈时出栈,然后可以把问题转化为判断二分图的问题。处理方法是先找到一个生成森林染色然后判断是否合法,我使用线段树套链表来找边的。

【POI2010】Beads 枚举串长然后用Hash表判重就好了,复杂度是[tex]O(n\log n)[/tex]

【POI2010】Divine Divisor 开始用pollard_rho硬上T成狗,正确做法应该是先用小于等于[tex]10^6[/tex]的质数去除,剩下的数最多只要两个质因子,然后两两GCD把可能的质因子找出来就好了,挺有趣的题目。

【POI2010】Intelligence Test 每一次用第二个数组在第一个数组上二分不断找后继就好了。

【POI2010】Antisymmetry manache稍微改一下直接上就好了。

【POI2010】Hamsters BZ上题面坑爹没有写串不会互相包含这个条件。既然不会互相包含那么一个串只能唯一的转移到下一个串,预处理两个串连接的最短长度,然后倍增就好了。

【POI2010】Blocks 开始只会带log的做法,看了题解才会姿势,果然自己是越来越弱了。。先把所有数都减去[tex]k[/tex]然后做出前缀和,如果第[tex]i[/tex]个位置要比第[tex]j(i < j)[/tex]优,那么它的左端点一定比[tex]j[/tex]靠左,维护一个栈用两个指针扫就好了。

【POI2010】Sheep 终于学会了极角排序的正确姿势。如果一条对角线把多边形分成了两个包含偶数点的块的话,在任何方案中它都是合法的,否则它都是不合法的。所以可以枚举一个端点极角排序来得到多有对角线是否合法,然后记忆搜即可。

【POI2010】Teleportation 神奇的题目,反正我是没有想明白,最后还是无脑抄了波兰人的公式。

【POI2010】Monotonicity2 令[tex]f_i[/tex]为以第[tex]i[/tex]个位置结束最长可以是多长,然后就可以分三种情况用树状数组转移了。虽然正确性不是很明显(我也不会证明),但是A了也就这样吧。

【POI2010】The Minima Game 傻逼DP,维护一个后缀最大值就好了。

【POI2010】Frog 对第[tex]k[/tex]近在左侧的所有点来说,显然第[tex]k[/tex]近和下标是单调的,在右侧的点也是一样,所以就可以用两个指针扫过去,二分判断当前指针相对第[tex]k[/tex]近点的位置关系,注意一下细节。处理出来之后直接倍增就好了。

【POI2010】Bridges 二分答案显然,然后问题就变成了判断混合图是否存在欧拉回路,经典网络流模型。

【POI2010】Pilots 同Blobks,所以也可以用两个指针来扫,维护两个单调栈来查询区间的最大值和最小值。

Category: 论逗逼的自我修养系列 | Tags: | Read Count: 1045
Avatar_small
gzz 说:
2017年3月02日 03:29

求网址...
求Teleportation的解法(公式也行。。)
我感觉网上的题解都不太对。。http://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=3813


登录 *


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

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com