[BZOJ2342] [Shoi2011]双倍回文（manacher）

传送门

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