POI 2010 Stage I 题解

Guilds
傻叉题,首先如果有一个孤立点显然不行。其次把图看成树(忽略多余边),奇数层染K,偶数层染S就可以了。。
Railway
见洲妹的博客>_<
Beads
首先注意到如果枚举每个K。。那么实际上要考虑的项链总个数为N/1+N/2+…=O(NLogN)
那么枚举K的话。如果能快速计算出所有项链的Hash值来判重,还是doable的。。
那么Hash用倍增算,判重的话要考虑翻转,用两个集合搞,一个集合保存对称的串,一个保存非对称的。。
遇到对称串,放入集合,遇到非对称的就把它和它的反转一起放入集合。。
然后结果就是|对称集合|+|非对称集合|/2
Divine divisor
很容易想到因式分解之后瞎搞。。但是我用rho+miller-rabin搞了很久还是只有89分>_<。。
看了标程之后才明白,因为所有数小于10^18,那么首先用所有小于10^6的素数去除。。
那么接下来的数如果有3个质因数pqr,就矛盾了。所以只可能是p,pq,p^2这样的形式。。
然后考虑它们之间两两的最大公约数。由于所有数最多只有2个素因子,那么如果该最大公约数是某数的真因子。就肯定是素数。。
然后考虑某数可能是p^2的情况。。根号一下就可以了。。
然后剩下来的数要么是pq,要么是p。。而且两两之间要么相等要么互质。。所以可以直接拿pq去除所有数。。结果算两份就可以了。。
然后用miller-rabin判断是否是素数。。OK了。
傻叉题,对于每个数储存一个数组表示在原序列中的位置集合。。
然后一个个往下找,每次找当前位置后的第一个询问序列的当前数。。
找不到就挂了。。

7 thoughts on “POI 2010 Stage I 题解

  1. 回复WJBZBMR:Orz。。。Sevenkplus(715770607) 1:09:48 顾昱洲(715770607) 1:03:19 从下向上扫描 顾昱洲(715770607) 1:03:33 如果这个操作是save就无视 没看到号码,以为是两个人…

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>