G.Colorful String(The Preliminary Contest for ICPC Asia Xuzhou 2019)
2024-09-05 09:12:56
https://nanti.jisuanke.com/t/4
#include <bits/stdc++.h>
using namespace std;
const int N=6e5+,base =;
typedef unsigned long long ull;
char str[N];
ull hl[N],hr[N],p[N]; int mark[N][]; ull get(ull h[],int l,int r)
{
return h[r]-h[l-]*p[r-l+];
} int k=;
long long getval(int l,int r)
{
if(l==r&&str[r]=='z'+)
return ;
long long sum=;
if(str[l]=='z'+)
l++;
for(int i=;i<=;++i)
{
int temp=(mark[r][i]-l+)/;
if(temp<)
continue;
sum+=temp;
}
return sum;
}
int main()
{ cin>>(str+);
int n=strlen(str+); for(int i=n*;i>;i-=)//重点i-=2 模拟kmp添加一个字符
{
str[i]=str[i/];
str[i-]='z'+;
//中间插一个不需要的数
} n=*n;
p[]=;
for(int i=;i<=n;++i)
{
for(int j=;j<=;++j)
{
mark[i][j]=mark[i-][j];
if(str[i]!='z'+)
mark[i][str[i]-'a'+]=i;
}
}
for(int i=,j=n;i<=n;i++,j--)
{
hl[i]=hl[i-]*base+str[i]-'a'+;//正序的哈希值 ->
hr[i]=hr[i-]*base+str[j]-'a'+;//逆序的哈希值 -> 这个是必要的
p[i]=p[i-]*base;
} long long ans=;
for(int i=;i<=n;i++)//枚举每一个字符作为中点
{
int l=,r=min(i-,n-i);
while(l<r)
{
int mid=l+r+>>;//半径长度 //if(get(hl,i-mid,i-1) != get(hl,i+1,i+mid) )
//判读的确是左右区间的判断 但是 值却都是->方向的
//所以这个就是必须要有逆序的原因 if(get(hl,i-mid,i-) !=get(hr,n-(i+mid)+,n-(i+)+))
{
//如果不符合 肯定是缩小半径
r=mid-;
}
else l=mid;
}
ans+=getval(i-l,i);
}
printf("%lld\n",ans);
return ;
}
1389
解:
字符串hash二分跑回文串。
最新文章
- ASP.NET Web API 接口执行时间监控
- Android Log Tag含义
- win10下iis部署asp.net core rtm
- ACM/ICPC 之 双向链表_构造列表-模拟祖玛 (TSH OJ-Zuma(祖玛))
- linx 实用操作命令一
- linux系统进程的内存布局
- 下载youku视频(python3)
- 03C#基础(2)
- 汇编语言中PTR的含义(转载)
- jQuery基础应用
- Python之Metaclass详解,Python之元类
- MySQL8.0 原子DDL
- EF 6.x和EF Core实现返回dynamic类型
- Ubuntu gitlab安装文档及邮件通知提醒配置
- Kotlin的参考资料
- 01-Java基本语法
- mysql 常用的几个函数
- PTA——时间转换
- C艹 指针和const的关系和注意事项(非常有意思)
- Vue.js图片预览插件
热门文章
- 理解TCP三次握手和四次挥手
- Django基础之cookie
- 【转】Codeforces Round #406 (Div. 1) B. Legacy 线段树建图&;&;最短路
- 2016 ACM-ICPC NEERC F. Foreign Postcards (概率DP)
- vue 源码解析computed
- Leetcode题目200.岛屿数量(BFS+DFS+并查集-中等)
- VIM | vim操作大全
- Des加密类
- 003-tomcat配置文件-server、tomcat-users
- [hibernate]save()与persist()区别