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

【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，所以也可以用两个指针来扫，维护两个单调栈来查询区间的最大值和最小值。