Manthan, Codefest 16

2016年3月6日75013

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的前后缀最大/次大值讨论一下即可