【弱省胡策】Round #9

ACM/ICPC - Official

From Th_Ki_De saffah wangyisong1996WuZuoFanmslstaorunz


小时

尚未报名

Train0 16/26 From
Train1 1/3 From
Train2 3/21 From
Train3 9/26 From
Train4 10/40 From

【弱省胡策】Round #9

大家记得在比赛中途吃饭,身体好才是真的好XD

本次比赛以尛焱轟为主题\\^o^//

老规矩:难度和顺序无关!

题解:

A

经典题目

容斥原理+Dp

细节看标程以及AC代码就够了

B

CC某原题

http://discuss.codechef.com/questions/2276/knghtmov-editorial

C

结论题

只要知道肯定所有妹子分到一个组里最优就行啦

记得特判掉样例=。=

D

代码裸题

看代码就懂了

事实是出题人挂机中

upd:后缀数组+主席树就能通过这道题啦!

E

构造题

此题是某CF(taorunz & saffah Round)被毙掉的题,题解等trz找出来

对于n=1答案是0,对于n=2答案是-1,对于 n>2 答案是 (n+2)/4。

我们把(1,n),(2,n-1),…两两配对,每一组的和都是n+1,这些组都必须被破坏,而每一次合并操作至多破坏两组,所以至少需要(n+2)/4次操作。

对于n mod 4 != 1的情况,我们直接把1和(n+2)/2合并,2和(n+2)/2-1合并以此类推就可以了;

对于n mod 4 == 1的情况,我们可以把(n/2 + 2)/2单独和n合并,再把2和n/2合并,3和n/2-1合并以此类推。

容易证明这样做正好需要(n+2)/4次并且不能再合并出n+1.