A.Little Red Riding Hood

B.Choosy in Food

•F[i]：从第I个点到终点的期望步数

•F[i] = (F[i + k] + k ) * P[k]

•F[ed] = 0

•高斯消元求解

•注意存在从起点不能到达终点的情况

C.Friends

•F[rt][len] ：节点rt的子孙里，距离rt的为len的节点个数

•ans[rt][len] : 整棵树上，距离rt为len的节点个数

•F值一次简单的深搜可以得到

•而ans[rt][len] = F[rt][len] + ans[fa(rt)][len – 1] – F[fa(rt)][len – 1]

D.GCD

E.One Stroke

•在每一个根到叶子结点的路径上用双指针即可求出一笔能画出的最多结点。

•双指针思路：枚举起点i，向右不断移动终点j，直到ij之间的和不大于k，复杂度O(nlogn)

•如果暴力优美也能过(T^T)，复杂度O(nlognlogn)

F.Escape from the Darkness

G.Sequence Number

•这是一道排序可以过的题，也可以rmq+二分

•最快的写法可以用单调栈做到O(n)

H.Mathematical Game 

I.Candies

•线段树中查询一个区间里，最长的连续B区间的长度

•区间合并时考虑左间的右部连续B加上右区间的左部连续B区间可能会更新这个区间的MAX_B值

•同时更新区间的左部连续B长度时，考虑左区间全部为B时，应加上右区间的左B长度

•更新区间的右部连续长度同理

•查询时，同样要根据更新的原理来更新查询的答案

J.Color Circle

• 搜索，DFS即可

K.Deadline

•这题只要想到思路还是很简单的，假设所有工程师每天都在修复bug，那么对天数记录bug的前缀和，O(n)得到答案max(pre[i]+i-1)/i)

L.Happiness

•求字符串中AB出现的次数

•遍历一次字符串即可

华中农业大学第五届程序设计大赛网络同步赛题解