Manthan, Codefest 16

2016年3月6日4,45614

A. Ebony and Ivory

给定a,b,c

求一组整数解x,y使得x * a + y * b = c

题解

数据范围很小暴力枚举x

B. A Trivial Problem

求n!有多少个0

题解

暴力求n!被多少个2和5整除

C. Spy Syndrome 2

给定长为(n <= 10000)的主串,给(m <= 100000)个长不超过1000的子串,总长不超过1000000

求一个主串由 子串的反串 拼出的解法

题解

求每个子串的哈希值,主串每位枚举串长 <= 1000,求出哈希值和子串进行匹配转移

D. Fibonacci-ish

给一个长为( n <= 1000 )的数列,数字 <= 10^9 问最多能选出多少个数组成广义斐波那契数列

题解

枚举选出两个作为斐波那契数列的开头,暴力递推,由于斐波那契数列的增长速度很快,几十项就会超过10 ^ 9

F. The Chocolate Spree

在树上选两条不相交的链,使链上的点权和最大

预处理

best[x]表示x子树内的最长链

down[x]表示子树内从x出发的最长链

up[x]表示从x出发,终点在x子树外的最长链

最终一定存在点,使得最优解的一条链 a 经过它,另一条链 b 在它的一个儿子的子树内且链 a 不经过这个儿子

枚举这个儿子y,答案就是best[y]加上链 a

链 a 有若干种情况,记录down的前后缀最大/次大值讨论一下即可

 

avatar
2 Comment threads
12 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
5 Comment authors
sjyhzwer大水车...黑 Recent comment authors
  Subscribe  
提醒
sjy
sjy

Orz

黑

黄学长,你发Saber的图干甚,脑子没坑啊!

...
...

请说话得体

岁月是朵两生花

图在哪里啊=-=
请注意您的用词啊=-=

大水车
大水车

起码人家有脑子,可惜你没有