[BZOJ2342] [Shoi2011]双倍回文(manacher)
2024-08-30 00:16:33
manacher......
先跑一边manacher是必须的
然后枚举双倍回文串的对称轴x
把这个双倍回文串分成4段,w wR w wR
发现,只有当 y <= x + p[x] / 2 && y - p[y] <= x 时,y最大才是最优解
也就是y在第三段,并且以y为中心的回文串要扩展到x的或左边,并且y的回文串要被x的包在里面
那么 (y-x) * 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
{
int id, p;
}a[N]; inline bool cmp(node x, node y)
{
return x.p < y.p;
} inline void manacher()
{
int i;
s[0] = '$', s[n * 2 + 1] = '#';
for(i = n; i >= 1; i--) s[i * 2] = s[i], s[i * 2 - 1] = '#';
for(i = 1; i <= n * 2 + 1; i++)
{
p[i] = 1;
if(i <= maxright)
p[i] = min(p[pos * 2 - i], maxright - i + 1);
while(s[i - p[i]] == s[i + p[i]]) p[i]++;
if(maxright < i + p[i] - 1)
{
pos = i;
maxright = i + p[i] - 1;
}
}
for(i = 1; i <= n; i++) f[i] = (p[i * 2 - 1] - 1) / 2;
} int main()
{
int i, j;
scanf("%d", &n);
scanf("%s", s + 1);
manacher();
for(i = 1; i <= n; i++) a[i].id = i, a[i].p = i - f[i];
std::sort(a + 1, a + n + 1, cmp);
j = 1;
for(i = 1; i <= n; i++)
{
while(a[j].p <= i && j <= n)
S.insert(a[j].id), j++;
it = S.upper_bound(i + f[i] / 2);
if(it == S.begin()) continue;
it--;
ans = max(ans, (*it - i) * 4);
}
printf("%d\n", ans);
return 0;
}
最新文章
- while用法一例
- 分享 Ionic 开发 Hybrid App 中遇到的问题以及后期发布 iOS/Android 的方方面面
- php集成动态口令认证
- 在linux中减小和增大LV的过程与思考
- Hdu 1081 To The Max
- Java_解决java.security.cert.CertificateException: Certificates does not conform to algorithm constraints
- Ant -- Another Neat Tool
- selenium+python登录登出百度,等待页面加载,鼠标定位
- xampp环境安装swoole
- 【转】从框架看PHP的五种境界及各自的薪资待遇
- linux根据该文件夹的读取权限和权限运行差异
- 开始PYTHON之路
- JVM(一):方法区
- HotSpot 虚拟机对象揭秘【转载】
- .NET拾忆:FileSystemWatcher 文件监控
- NATS—协议详解(nats-protocol)
- bzoj 2753 [SCOI 2012] 滑雪与时间胶囊 - Prim
- 简单的java程序
- Grapher - Change how graphs look
- 移动端使用的WebKit私有属性(转)
热门文章
- php通过类名查找这个类所在的路径(即实际引用的是哪个类)
- vue.js与react.js相比较的优势
- 转载自infoq:MYSQL的集群方案
- Codeforces Round #290 (Div. 2) _B找矩形环的三种写法
- charles连接手机抓包--------最详细的步骤
- video 的使用
- Java MiniUi datagrid加载数据时,如果使用virtualScroll=";false";,数据多一点可能就会加载不出来
- Python基础篇 -- 列表
- 【dp 贪心】bzoj4391: [Usaco2015 dec]High Card Low Card
- 【curl】【php】curl报错,错误代码77,CURLE_SSL_CACERT_BADFILE (77)解决方法