整体难度思想（以CF的Div.2难度进行比对）：
A.C题难度
B.A题难度
C.D题难度
D.D到E之间难度
E.B题难度
A.xgg的旅行
我们用SPFA预处理出两点间最短路，然后O（n）枚举中间点，然后找距离中间点最近的两个点就行了，注意三个点不能有相同的。
B.F神爱读书
水题。
C.蓝鲸巨打联盟
我们设定Dp【i】表示到时刻i能够打出的最高伤害，那么对于三个小技能有：
Dp【i】=Dp【i-x】+a
Dp【i】=Dp【i-y】+b
Dp【i】=Dp【i-z】+c
对于大招来讲，我们暴力做肯定是：Dp【i】=Dp【i-j】+Sum（这里Sum表示能够打出的伤害），j要在【L，R】合法范围内；
我们考虑到，每一次将i加1之后，能够转移的区间的价值变化是相同的，所以我们考虑用线段树加速优化即可，整体时间复杂度O（nlogn）；
状态转移方程改写为：Dp【i】=Query（合法范围内的部分）；
每一次转移之后，区间更改就行了。
D.233的转置
对于样例BABA
对A的位置构造一个多项式（x^(1)+x^(3)）
即当s[i]='A'时x^(i)的系数为1
对B的位置构造一个多项式（x^(0)+x^(-2)）
即当s[j]='B'时x^(-j)的系数为1
两个多项式相乘之后得到
x^(i)前面的系数就是“i-转置”的个数
这个多项式可以用FFT或者NTT求解
对A的位置构造一个多项式（x^(1)+x^(3)）
即当s[i]='A'时x^(i)的系数为1
对B的位置构造一个多项式（x^(0)+x^(-2)）
即当s[j]='B'时x^(-j)的系数为1
两个多项式相乘之后得到
x^(i)前面的系数就是“i-转置”的个数
这个多项式可以用FFT或者NTT求解
E.Yzi爱英语
凯撒加密，将题干每个字符都向上加3解密即可，其实就是让我们求N以内的素数的个数。
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
