[刷题记录]POI2000 - jcvb

[刷题记录]POI2000

jcvb posted @ 2013年12月27日 21:02 in 未分类 , 2404 阅读

终于能完整刷完一届POI好高兴= =(其实还剩一道交互题。。)

Where to Build a Brewery?
假设1~n顺时针排列。记选择的地址为x,x+1~p的城市逆时针走,p+1~x-1的城市顺时针走。
首先算x=1时的p值以及答案,再逐步推得x=2,3,…时的答案(需预处理需求与距离的前缀和)。x顺时针移动的过程中p也会顺时针移动,恰好移动一圈,所以复杂度线性。
(从n绕到1的时候细节有些坑要注意)


Skiers
网络流裸题。拆点求最大流。
(标解似乎是贪心,尽可能选择靠右的路线。。因为它是个平面图而且还给定了左右顺序)


Stripes
每放置一条带子就把整条纸带分为左右独立的两个子游戏。
直接递推求出SG函数即可。


Viruses
所有串读进来建成AC自动机(DZY告诉我这其实叫做Trie图),把不允许到达的结点(串末尾字符,或者能fail到串末尾字符)作上标记。然后DFS检查是否有不经过标记的环。


Signatures
从每个commander开始DFS。复杂度O(n)*O(n)=O(n^2)。


Automorphisms
将置换分解成k个轮换。
首先分析同一个轮换内的点之间的连边情况:
考虑某一个轮换,假设其为a_1->a_2->…->a_p。则在所求的图中,边(a_1,a_2),(a_2,a_3),……(a_p-1,a_p),(a_p,a_1)同向,边(a_1,a_3),(a_2,a_4),……,(a_p,a_2)也同向,……。可以发现p必须为奇数,否则能得出(a_p,a_p/2)与(a_p/2,a_p)同向,矛盾。当p为奇数时,按照上面的方法可以把所有这C(p,2)条边分成(p-1)/2组,每组内的边同向,于是有2^((p-1)/2)种方案。
再来分析不同轮换的点之间的连边:
假设两个轮换分别是a_1->a_2->…->a_p,b_1->b_2->…b_q。则边(a_1,b_1),(a_2,b_2),…同向。容易知道所有这p*q条边可分成gcd(p,q)组,每组内的边同向。方案数即为2^gcd(p,q)。
接下来关键在于统计[tex]\sum_{1\leq i < j \leq k}\text{gcd}(p[i],p[j])[/tex]。暴力只有65分。
O(nlogn)统计x[j]表示满足j|x[i]的i的数量。
然后令y[j]=C(x[j],2),即为满足j|gcd(p,q)的无序对(p,q)的数量。
倒过来容斥,O(nlogn)得到z[j],表示j==gcd(p,q)的无序对(p,q)数量。全部加起来即可。


Triple-Arm Crane
令p<=q。
设i是从左到右第一个未被占据的格子,如果此时i+p未被占据,则填上i,i+p,i+p+q(为方便叙述记为“对i进行p操作");否则填上i,i+q,i+p+q("对i进行q操作")。
为证明这个贪心操作可以一直进行下去,只需证明不存在i+p,i+q同时已被占据的情况:
如果是这样,注意到此时i未被占据,则可以证明i+q必是由于对i-p进行了q操作而被填上的。但根据我们的摆放策略,i-p+p=i未被占据时本应该优先进行p操作,出现了矛盾。


Code
首先预处理出Catalan数C[i]。
若确定根结点为某个字母x,则其左右子树大小分别为x-1,n-x,此时的方案数即为C[x-1]*C[n-x]。
由于根是字典序最优先者,于是可以根据K的大小确定根结点的字母x,以及所要求方案在根节点为x的所有方案中的排名K'。
按字典序,左子树是第二优先,右子树是第三优先,所以左子树应该取第K'/C[x-1],右子树应该取第K'%C[x-1],递归处理即可。


The Labyrinth of Wells
题意有点绕,其实就是说颜色相同且三个出口分别对应相同(注意有可能是合并后才相同)两个结点是相同的,可以合并,求最后合并完后剩下几个结点。
题目说明保证了拓扑序,所以可以按拓扑排序逆序枚举结点i,检查i能否与i-1,i-2,…合并,合并时只需对被吞并的结点打一个标记即可。这样复杂度是O(n^2),在main上被卡了。。。
于是把检查的过程改为hash表(用map就行),直接就能找到哪些结点需要合并。注意i和j合并后,需要将其他指向j的结点改为指向i,会导致这些结点hash值的改变。
(低端做法求不鄙视=-=)


Lollobrigida
(突然联想到今年NOIPDAY2第二题。。好吧还是挺不一样的。。)
容易想到一大一小交替放置。容易发现无解总是由于相同的元素不得不相邻摆放而导致的。
将a[1..n]排序。
若n为偶数,按a[n/2+1],a[1],a[n/2+2],a[2],a[n/2+3],a[3],…,a[n],a[n/2]排列。若这个序列不合法,则必然存在a[n/2+i]==a[i],从而有a[i]==a[i+1]==a[i+2]==…=a[n/2+i],即有n/2+1个数相同,此时可由抽屉原理证明必然无解。
n为奇数时也可类似构造,但需要特判前(n+1)/2或后(n+1)/2个数相同的情况。


P-Broken-Line
把所有出现过的X坐标离散化。注意x=-∞和x=+∞也要放入。注意若排序后x0,x1相邻,且x1-x0>=2,则要在x0,x1间加一个点;若x1-x0==1则不用。
Y坐标也一样离散化。然后形成了一个XLEN*YLEN的网格,其中XLEN,YLEN的大小都是O(n)的。把线段占据的位置标为障碍。
为了求得最小转弯次数,BFS即可,对u扩展就是从u向四周伸展的一个十字形(遇到障碍则break),扩展得到的新结点加入队列,转弯次数=u的转弯次数+1。
O(n^2)个结点,每次扩展O(n),总复杂度O(n^3)可过。


Agents
令状态为(v1,v2),表示此时a,b分别处于v1,v2两个点上。状态数O(n^2),于是答案为O(n^2)级别。
BFS,每次转移需要考虑v1的出边和v2的出边,复杂度为O(deg[v1]*deg[v2])=O(n^2)。总复杂度O(n^2)*O(n^2)=O(n^4),TLE。
考虑优化,把一次转移拆成两次转移,a先走一步,b后走一步。把状态表示为(v1,v2,bo),bo=true/false表示下一步轮到a/b走。这样状态数仍然是O(n^2),但每次转移只需考虑其中一个点的出边,O(n)。总复杂度O(n^2)*O(n)=O(n^3)可过。


Repetitions
后缀数组求height以后二分。(数据范围太弱似乎可以暴力)


Promotion
需要支持插入单个元素,查询并删除最大值,查询并删除最小值。
用set能在bzoj上水过,但在main上被卡成80分。改成手写treap依然80。
改用一个小根堆和一个大根堆同时维护这一堆数,数值相同的仅记录出现次数。同时对次数不为零的数值记录其对应结点在堆中的位置,方便删除。
这样在main上是94分,加上fread就能100。(标解应该没那么无耻吧。。也许是某种神奇优化)


 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee