传送门
manacher......
先跑一边manacher是必须的
然后枚举双倍回文串的对称轴x
把这个双倍回文串分成4段，w wR w wR
发现，只有当 y <= x + p[x] / 2 && y p[y] <= x 时，y最大才是最优解
也就是y在第三段，并且以y为中心的回文串要扩展到x的或左边，并且y的回文串要被x的包在里面
那么 (yx) * 4 中最大的就是答案
我们不妨按照 y p[y] 排序y，枚举x，依次添加y进入set，从set中找最大的 y <= x + p[x] / 2
边界讨论恶心至极
#include <set> #include <cstdio> #include <algorithm> #define min(x, y) ((x) < (y) ? (x) : (y)) #define max(x, y) ((x) > (y) ? (x) : (y)) #define N 1100000 int n, pos, maxright, ans; int p[N], f[N]; char s[N]; std::set <int> S; std::set <int> :: iterator it; struct node a[N]; inline bool cmp(node x, node y) inline void manacher() } for(i = 1; i <= n; i++) f[i] = (p[i * 2 1] 1) / 2; } int main() printf("%d\n", ans); return 0; }
上一篇：[luoguP1783] 海滩防御（二分 || 最短路 || 最小生成树）
下一篇：[luoguP2886] [USACO07NOV]牛继电器Cow Relays（矩阵）
Manacher
