T6 散落の字符：MANACHER算法、大模拟
题意说明
本次题目比较复杂，需要我们计算以下问题的答案。
1. 通过迷宫的最小花费 sumsumsum。
2. 转换 sumsumsum 并拼接到 sss 后面，转换 sss 为 01 字符串。
3. 计算转换为偶回文串最小花费 fff 的值。
4. 连接 ttt 和 sss，计算最长回文串 lll 的值。
走迷宫
这一部分采用任何搜索算法均可。期待大家给出出题组没做出来的 dp 的办法。以下是 dijkstra 的做法：
转换与拼接
这一部分直接采用模拟即可。一个字符的ASCII码值为偶数是 mod 2\bmod2mod2 的结果为 000，否则为 111。
计算 F 的值
在这一步中，我们需要推理一下。数据保证 sss 可以转化为偶回文串，说明 s+minas + min_as+mina 的结果是偶数或者拼接后的 sss 的中间值为 000。如果是第二种可能，就只需要保证其它部分是偶回文串即可。
因此无论如何，只要保证拼接后的 sss 是一个回文串即可保证是偶回文串。我们只需要从 i=0i=0i=0 一直到 i=∣s∣÷2i=|s|\div2i=∣s∣÷2 遍历一遍，找到改变成偶回文串的最小花费。对于每个第 iii 项，我们只需考虑是改变成 0 还是 1 的花费更小。
计算 L 的值
暴力做法：枚举每一段 l 中的子串。代码如下：
时间复杂度：O(∣l∣2)O(|l|^2)O(∣l∣2)
预计得分：50pts50pts50pts
我们可以使用 Manacher 算法来解决 lll 的计算。回文自动机的 Manacher 算法可以在 O(N)O(N)O(N) 时间中解决最长回文子串问题。
下面就是模板的 Manacher 算法了（这里使用 % 避免边界问题，若有想要深入学习的请见：这里）：
时间复杂度：O(∣l∣)O(|l|)O(∣l∣)
预计得分：200pts200pts200pts
正解
时间复杂度：O(n×m×logn×m))O(n\times m\times \log{n\times m}))O(n×m×logn×m))
预计得分：200pts200pts200pts
