251116 模拟赛

T1

给你一个有向图，每条边有一个小写字母边权，可能存在重边自环。问有多少个有序二元组 \((x,y),~(x\ne y)\) 满足存在一条 \(x\to y\) 的回文路径。

\(n,m\le 5000\)

从回文中心向两侧暴力扩展，显然就是对的，时间复杂度 \(O(n^2+m^2)\)。实现不要太劣要不然会变成 \(O(n^2\Sigma)\) 然后被卡常。

T2

dp 板子

T3

倍增板子

T4

由于原串中每个字符最多出现一次，因此暴力枚举第二个串的循环移位然后找到开头位置暴力向后匹配就是对的。