Problem A
比赛的时候没主要搞这个题(因为不怎么会)
其实就是类似做dij的一个过程,记录3个值:当前点编号,到当前点的代价,当前点的那条边的颜色。
然后遍历一遍就可以了。
Problem B
本来比赛的时候想到不同的字母之间的差值肯定不能作为循环节。
然后我就上了FFT,因为做过差不多的题。
但是WA了半场之后弃了。
其实我又想偏了,直接枚举循环节然后一个个判断过来,
时间复杂度是$O(nlogn)$的。
就是观察每个循环节的时候做到$O(1)$就行了。
具体细节的话就是循环节长度至少为$3$
A不能在倒数两个位置,C不能在前两个位置。
B不能在开头也不能在结尾。
出现过的必须满足ABC这样的顺序
然后符合上述条件的话就可以作为循环节。
然后更新答案就好了。
Problem C
Problem D
Problem E
Problem F
Problem G
Problem H
Problem I
环套树,环上用个树状数组搞搞。
其他的东西树链剖分。
这个如此简单的题我居然还有一个多小时的时候才看到
还没写出来
唉。
Problem J
比赛的时候不会LCT。其实就差一步了。
(另外我没做过弹飞绵羊,我只是听说过这个题)
Problem K
Problem L