[刷题记录]POI2005 - jcvb

[刷题记录]POI2005

jcvb posted @ 2014年4月04日 20:54 , 2384 阅读

Cash Dispenser
对每一条记录,倒着扫一遍预处理出每一位之后最近的0~9的位置。然后暴力枚举0000~9999每个串进行O(1)检查是否匹配。
能够匹配n条记录的串自然就是答案。
*


Points
判断两个点集能否经过移动/旋转/翻转/相似变换能否变成重合。
重心显然也应该重合。于是把点集按照相对于重心的极角排序(共线不要忘记判)。求各点到重心的距离,以及极角序相邻两点的内积,把他们的gcd约掉(判伸缩)以后随便乱搞起来变成一个hash值。判hash值是否相等就可以了。
判翻转只要把x坐标取负即可。


Toy Cars
*贪心。当前要取出的那个玩具在序列中下一次出现的位置要尽量靠后。用堆维护。


Piggy Banks
i里的钥匙能开j则连边i->j,得到一个每个点入度为1的有向图。它由若干个不相交的基环+外向树,每一个基环+外向树可以通过打碎环上的某个罐子而全部打开。于是只要统计它的无向图版本有几个连通分量,并查集即可。


Knights
首先,两个向量(0,y1),(0,y2)可以合并为一个(0,gcd(y1,y2))。(显然)
不妨设存在某个向量A(x,y)满足x≠0(若不存在则直接如上处理)。设另外某个向量为B(x1,y1)。则可以利用辗转相除法将A和B改写为A'(x',y')和B'(0,y1')。
将除A外的向量都消成B'(0,y1')的形式,并将它们合并。最后得到的两个向量即为答案。
(*不知道怎么证明最后的数字能在靠谱的范围里。。)
(发现一个性质,用扩展GCD求ax+by=d=gcd(x,y)的解a,b满足abs(a)<=abs(y)/2+1,abs(b)<=abs(x)/2+1。但还是不知道怎么证。。)


A Journey to Mars
(+p[i]-d[i])自复制一遍接在后面,求前缀和。然后能用单调队列搞出每个点往右走的最远距离,>=n则可行。逆时针同理再做一遍。


Bank Notes
裸多重背包。经典的单调队列做法。


Fibonacci Sums
把两行的对应位置相加,于是会出现连续的1,或是出现2等不合法情形。假设左边是低位,右边是高位,容易发现110可以合并成001,0020可以合并成1001等,但是合并后又可能产生新的需要合并的地方。关键就在于怎样合并可以保证O(n)复杂度。

先考虑只有0和1,没有2的情况:
从右往左扫描,一旦发现有两个连续的1立即合并,即110?->001?。假如?=0,那么合并完就没事了;假如?=1的话,右边又会新产生连续的两个1需要合并,合并完后可能还要继续往右合并,比如1101010->0011010->0000110->00000010。可以证明这样的复杂度仍然是O(n)的:假设我们对原序列从右往左扫描,每遇到连续两个1就分一段,比如10011110110111110101001就被分为100,11,110,1101,11,110101001这几段。每一段内的合并显然是O(段长度)的,且合并完后至多往右边一段进一个1,但右边一段的最左边两位已经是00了,进上去变为10,不会产生新的合并。

于是我们只需考虑如何把原序列的2全部消灭掉:
根据题目的条件,可知2的两边都是0。从右往左扫描,直到发现020为止。往020的左边继续扫描,得到一个极长的020202020……020的串,设串首位的左边两位为xx,则xx的可能性有00,01,10,11,20。那么

0002020202…0202020->
0100010101…0101011

0102020202…0202020->
0200010101…0101011

1002020202…0202020->
1100010101…0101011

1102020202…0202020->
0110010101…0101011

2002020202…0202020->
1010010101…0101011

这样合并后仍然满足2的两边都是0的性质。继续往左进行下去,最后2会全部消失。


Dicing
二分上界。把对每条边建一个结点,连向其两个端点。然后就是很裸的网络流了。


Template
覆盖用的串不能超出原串边界,且又要完全覆盖。所以合法串必然是原串前缀且是原串后缀。
KMP后可以得到一棵fail-tree,那么n到根路径上的一个结点对应一个可能合法的串。考虑其中某个串,其长度为len,它在原串的所有出现位置(结束位置)即为以这个结点的为根的子树。如果这个串能够不遗漏地覆盖原串,则它的所有出现位置中相邻两个的距离不超过len。
于是我们要对n到根路径上的每个结点,统计其子树内元素中相邻的差的最大值。考虑沿根下降,则子树元素从{1,2,..,n}开始不断减少。用一个双向链表维护当前属于子树的值,删除的同时更新相邻元素差的最大值。
总复杂度O(n),常数稍大。
看到网上的题解里有用二分的,表示理解不能。


Hollows
首先必须得是个无环的二分图,所以1000W条边是吓唬人的。

然后画一画会发现每个连通分量满足这样的性质,把度数为1的点去掉后剩下的是一条链,这条链在两棵树之间来回,中间夹着那些度为1的点,这些点是可以任意排序的,要乘上它们的阶乘。然后这条链(长度大于1时)可以从上到下或从下到上,有两种情况;起点在哪棵树也有两种情况,乘以2。
然后各个连通分量是要被隔开来的,它们之间的顺序也是任意,要乘上阶乘。最后孤立点是可以任意选位置插的,


Special Forces Manoeuvres
题意:往平面上依次放n个圆,求:放到第几个时,圆的交集变为空。

XYZ告诉我一个判断n个圆是否有交集的做法:(假设所有内含或相离的情况已经判掉)选取一个圆Ci,计算其他n-1个圆与它相交而得的弧,检查这些弧有没有交集,就可以知道Ci是否有某段弧在这n个圆的交集的周界上。如果有则说明这n个圆存在交集;如果对所有1<=i<=n都没有则说明不存在交集。这样似乎每判一次是O(n^2logn)的,外面套一层二分就是O(n^2log^2n)。华丽地TLE=-=


然后去膜拜题解:
由于圆的周界不会是竖直线,也不是奇葩的锯齿状之类。。所以若干个圆的交集(如果有交集的话)的最右点是唯一的。
又由于平面是二维的,所以这个最右点可以由不超过两个圆确定(可能是某两个圆周的交点之一,也可能是某一个圆的最右点)。计算n个圆两两之间交集的最右点,这n(n-1)/2个点之中最左的一个即是这n个圆交集的最右点。那么只要验证这个点是否在每个圆内,就能知道这n个圆是否有交集。这样每加入一个圆需要O(n)次计算,总复杂度是O(n^2)。
 

好神。。

(2015.4.10 upd:发现这个做法被http://fanhq666.blog.163.com/blog/static/81943426201131691852787/艹出翔啦!)


Two Parties
这题中,每个人都是可以满足要求的(**CMG告诉我这叫Gallai Cycle-Cocycle Partition Theorem,不会证)。
给两个集合标号为0和1,令xi表示第i个人所在集合的标号,令i1,i2,…,ik表示i的k个邻接点。根据题意,
如果k为偶数,则xi1 ^ xi2 ^ … ^ xik = 0;
如果k为奇数,则xi1 ^ xi2 ^ … ^ xik ^ xi = 1。
解这个异或方程组即可。


Double-row
每个位置的颜色只有两种可能:交换或不交换。对于某个出现两次的数字,要把它们分割开来,则分情况讨论可以得到某两个位置是同色/不同色的信息。用并查集维护这些边。对每个联通分量,取数量的较少那种颜色对应的位置进行交换即是最优解。


The Bus
类似LIS的一个裸DP,离散化以后线段树/树状数组优化。

foreseeable 说:
2014年5月07日 07:49

Gallai Cycle-Cocycle Partition Theorem不难证的啊

Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee