洛谷 P4287 [SHOI2011]双倍回文题解
2024-09-07 01:54:01
前言
用了一种很奇怪的方法来解,即二分判断回文,再进行某些奇怪的优化。因为这个方法很奇怪,所以希望如果有问题能够 hack 一下。
题解
我们发现,这题中要求的是字符串 \(SS'SS'\),其中 \(S'\) 是 \(S\) 的反向,那么这个串长度必定为 \(4\) 的倍数。那么我们对于每个位置,寻找一组最大的 \(SS'\),然后找这前面是否有一个与他相同的 \(SS'\),如果有,那么这两组字符串组成一个双倍回文。但是问题在于对于某些情况,例如 bbbbbbbbbbb
,在第 \(3\) 和 \(4\) 个字符中间以及第 \(8\) 和 \(9\) 个字符中间,都能取到长度为 \(3\) 的回文 bbb
,但是他们共用了第 \(6\) 个字符,从而造成最大双倍回文子串长度为 \(3\) 的假象。为了避免这种假象的发生,同时保证答案长度的最大化,我们需要将共用的部分一分为二,各执一半。
仔细思考,我们可以发现,这一共用的部分只可能是一个字符集大小为 \(1\) 的字符串(语文不好不知道怎么表达)。因为我们知道,回文子串关于对称中心对称,即在该回文子串长度范围内与对称中心距离相同的两个字符相同,两个串共用的部分位于一个串 \(A\) 的末尾和另一个串 \(B\) 的开头,当我们把串 \(B\) 的开头映射到串 \(A\) 的开头(因为 \(A\) 串和 \(B\) 串相同)后,可以发现,只有符合字符集大小为 \(1\) ,才能符合上述性质。
因此,我们预处理时把每一段字符集大小为 \(1\) 的长度等信息做好标记,然后在计算完各位置为中心的最大回文子串长度后减去重复长度即可。
代码
#include<cstdio>
#include<map>
#include<algorithm>
typedef unsigned long long ull;
const int MAXN=500001+5;
std::map<ull,int>map;
char str[MAXN];int tail[MAXN],n,l,rs[MAXN],r,len[MAXN],bll[MAXN],now,cnt,mid;ull cc,hash1[MAXN],hash2[MAXN],pow[MAXN];
ull GetHash1(int l,int r)
{
if(l<1||l>n||r<1||r>n) return ++cc;
return hash1[r]-hash1[l-1]*pow[r-l+1];
}
ull GetHash2(int l,int r)
{
if(l<1||l>n||r<1||r>n) return ++cc;
return hash2[l]-hash2[r+1]*pow[r-l+1];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%c",&str[i]);
if(!(str[i]>='a'&&str[i]<='z')) i--;
}
for(int i=1;i<=n;i++)
{
if(str[i]!=str[i-1]) {tail[i-1]=1;now++;}
rs[i]=now;
bll[now]++;
}
for(int i=1;i<=n;i++)
hash1[i]=hash1[i-1]*31+str[i]-'a'+1;
for(int i=n;i>=1;i--)
hash2[i]=hash2[i+1]*31+str[i]-'a'+1;
pow[0]=1;
for(int i=1;i<=n;i++)
pow[i]=pow[i-1]*31;
int ans=0,answer,aans=0,last=0;
for(int i=1;i<=n;i++)
{
cnt=0;l=1;r=std::min(i-1,n-i+1);ans=0;answer=0;
while(l<=r)
{
cnt++;
if(cnt>30) break;
mid=(l+r)>>1;
if(GetHash1(i-mid,i-1)!=GetHash2(i,i+mid-1)) {r=mid-1;} else {l=mid+1;ans=std::max(ans,mid);}
}
if(tail[i+ans-1])
ans-=std::min(ans,bll[rs[i+ans-1]])/2;
len[i]=ans;
int result=map[GetHash1(i-ans,i+ans-1)];
if(GetHash1(i-ans,i+ans-1)==GetHash1(i+ans,i+ans*3-1))
{
aans=std::max(aans,ans*4);
}
}
printf("%d",aans);
return 0;
}
最新文章
- [osx] 设置crontab
- C#获取全部目录和文件
- C# Sql 触发器
- (hdu)2444 The Accomodation of Students 判断二分图+最大匹配数
- 如何在 Java 中正确使用 wait, notify 和 notifyAll – 以生产者消费者模型为例
- ListView之BaseAdapter
- 使用Marshal.Copy把Txt行数据转为Struct类型值
- php实现加好友功能
- jstorm简介(转)
- 肢体语言心理学+FBI阅人术(行为心理学) 用最短的时间了解一个人
- Split()特殊字符
- 【LR11】Error -27796: Failed to connect to server";server:port";: [10060] Connection timed out错误解决办法
- Openfire服务器和Spark客户端配置
- 第七周助教工作总结——NWNU李泓毅
- 任务调度及远端管理(基于Quartz.net)
- taro 组件的外部样式和全局样式
- 前端组件化Polymer入门教程(6)——监听属性值变化
- MySQL数据库的安装与基本操作
- 【转】SpringMVC Controller 介绍
- RSYNC在zabbix中的检查
热门文章
- pytorch资料
- web优化(一 前端)
- Idea 隐藏不必要的文件或文件夹 eg:(.idea,.gitignore,*.iml)
- 「JSOI2011」柠檬
- Python压缩文件/文件夹
- 深入理解 ajax系列第一篇(XHR 对象)
- Java基础知识笔记第一章:入门
- java事务/springboot事务/redis事务
- 【PAT甲级】1032 Sharing (25 分)
- 【PAT甲级】1016 Phone Bills (25 分)(结构体排序)