12
25
2014
1

论逗逼的自我修养之POI2011

最近无论是做BZ的题还是清华集训的题感觉都是自己好弱啊...什么都不会做...

或者还是做POI的题目感觉舒服一点?至少不会有报复社会的计算几何和人类智慧...

而且现在感觉一味做题感觉没有什么用的样子,反正都是不会做+看题解。可能还是应该抽点时间看看论文学点东西啥的?而且要会考了..文化课怎么办啊...QAQ

[12.31]完结撒花,总算没有拖到明年去。那道数据范围加大版本我以前的pascal程序T了。。也懒得再写一遍了。

现在做了几题

17

【POI2011】Tree Rotations 启发式合并搞就好了

【POI2011】Temperature 随着右端点的右移左端点单调不降,用个堆搞就好了

【POI2011】Meteors 整体二分经典题

【POI2011】Strongbox 把所有的的数都变成和[tex]n[/tex]的最大公约数,然后显然就是要求一个不是前[tex]k-1[/tex]个数的约数的最小的第[tex]k[/tex]个数的约数,这样就只需要从大到小枚举[tex]n[/tex]的约数然后用个map搞就好了。

【POI2011】Difference 从左到右扫维护前缀第[tex]i[/tex]个字符出现次数减去第[tex]j[/tex]个字符的最小值,枚举到第[tex]i[/tex]个字符的时候如果答案右端点是它,那么出现最多和最少的字符中必定有一个是这个字符。注意一定是要出现过的,所以还要维护次小值。

【POI2011】Sticks 枚举最长的一根,前面维护最长的三根不同颜色的就好了。

【POI2011】Lollipop 萝莉出队~\(≧▽≦)/~!我才不会告诉你们我是萝莉控呢。显然如果[tex]x[/tex]有解那么[tex]x-2[/tex]一定有解,维护最长的偶数和最长的奇数就好了。

【POI2011】Party 删掉没有连边的[tex]\frac{n}{3}[/tex]对节点就好了。

【POI2011】Inspection DP出最远点,和最远点不同子树的最远点和所有点到一个点的距离和,然后判断这个点连出去最大子树的大小来算到底是可以减去最大值还是次大值还是无解。不知道是哪里写错了还是细节有问题所有数据WA在一个数字上,然后就可耻的cheat了。

【POI2011】Shift 如果是[tex]n[/tex]偶数的话一个点可以移到任意位置,所以直接搞就好了。如果是奇数的话因为第一个操作和第二个都只能改变偶数的逆序对所以逆序对数目为奇数的时候无解。移动的时候如果[tex]i[/tex]可以恰好移动到[tex]i-1[/tex]后面第三个,那么直接用第二个操作跳到他后面,否则就用一个比[tex]i[/tex]大的数架到他们中间再跳。

【POI2011】Dynamite 二分答案显然,然后就可以贪,每一次肯定是对当前最深的叶子节点操作,如果这个上面没有炸弹就直接删,否则就在最远可以点燃它的祖先那儿点燃,然后对整棵范围染色,然后记录一下当前从这个点出发最多染了多远复杂度就靠谱了。

【POI2011】Polt 二分答案然后贪心。贪心的时候不能直接二分最远的位置,这样复杂度不靠谱,应该先倍增确定一个大概的范围然后再在这个范围里面二分复杂度就对了。

【POI2011】Periodicity 神奇的构造题,大致的思路就是考虑把原串前后缀集合从小到大排序,然后从满足前[tex]i[/tex]个元素的最小串推到满足前[tex]i+1[/tex]个元素,具体的证明和算法什么的可以看vfk的博客。

【POI2011】Garbage 可以证明如果有解,一定存在一种方案使得所有环没有公共边。所以一定只经过要变化的边。我的做法是对每一个联通块求一次欧拉回路然后再把这个欧拉回路拆成若干个简单环,这个用链表可以很方便的搞。

【POI2011】Programming Contest 修车的做法T了。考虑那样拆点的模型,如果一个人第做的第[tex]i[/tex]题这个点没流量那么第[tex]i+1[/tex]题这个点也一定没有流量。所以可以把点一个一个插进去然后用匈牙利算法来增广。

【POI2011】Lighting Conductor 看成一个DP问题,这是有决策单调性的,所以就可以用一个栈来搞。

【POI2011】Conspiracy 求总的方案数比较困难,可以先考虑构造一组方案,可以发现这是一个2-sat问题。而在构造出一组方案之后分类讨论一下就可以得到总的方案数了。(因为团中的点数变化不会超过1)

Category: 论逗逼的自我修养系列 | Tags: | Read Count: 3091
Avatar_small
POI 说:
2014年12月27日 04:12

感觉好可怕啊,又有大神来屠我了。


登录 *


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