当前位置:网站首页>(2022牛客多校五)G-KFC Crazy Thursday(二分+哈希)
(2022牛客多校五)G-KFC Crazy Thursday(二分+哈希)
2022-08-03 03:24:00 【AC__dream】
题目:
样例输入:
6
kfccfk
样例输出:
3 3 3
题意:给你一个n,以及一个长度为n的字符串,字符串由小写字母组成,然后问里面有多少个分别以k、f、c字母结尾的回文字符串。
这道题好像标解是回文自动机,但是我不太会,下面我说一下这道题二分+哈希的思路。
看这道题之前大家应该先会求解一个字符串中的最大回文子串,不会的小伙伴可以看这里:求最大回文子串长度_AC__dream的博客-CSDN博客
首先可以确定的一点是所有的回文串都会有中心字符,如果回文子串长度为奇数,那么就只有一个中心字符,否则就有两个中心字符,所以我们可以枚举以每个字符作为中心时的最长回文串,然后再从中找到以k、f、c结尾的回文串,方法就很简单了,就是说假如我们现在以字符x为中心的最长回文串长度是11,这个长度为11的回文串里面有8个f,那么显然就会有4个以f作为结尾的回文串,毕竟回文串是对称的,所以我们就是这个思路,枚举一下以每个字母作为中心的回文串,事先处理一下k、f、c的数目前缀和,这样可以O(1)判断区间[l,r]里面某个特殊字母出现的次数。注意还有偶数的情况,这个时候就需要枚举一下两个中心点中的一个,左边还是右边都可以,需要注意的就是不存在的情况,就是说两个中心点字母不相同的时候是不存在的情况,二分+哈希求解回文子串长度的方法我已经在之前博客中介绍过了,上面附有博客地址,具体细节见代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=5e5+10;
typedef unsigned long long ull;
ull p[N],sum1[N],sum2[N];
int sk[N],sf[N],sc[N];//sx[i]标记前i个位置有多少个字符x
char s[N];
ull get(int l,int r,int op)
{
if(op==1)
return sum1[r]-sum1[l-1]*p[r-l+1];
else
return sum2[l]-sum2[r+1]*p[r-l+1];
}
int main()
{
int n;
p[0]=1;
for(int i=1;i<N;i++)
p[i]=p[i-1]*131;
while(scanf("%d",&n)!=EOF)
{
scanf("%s",s+1);
for(int i=1;i<=n;i++)
{
sum1[i]=sum1[i-1]*131+s[i];
if(s[i]=='k') sk[i]=sk[i-1]+1;
else sk[i]=sk[i-1];
if(s[i]=='f') sf[i]=sf[i-1]+1;
else sf[i]=sf[i-1];
if(s[i]=='c') sc[i]=sc[i-1]+1;
else sc[i]=sc[i-1];
}
sum2[n+1]=0;
for(int i=n;i>=1;i--)
sum2[i]=sum2[i+1]*131+s[i];
long long ansk,ansf,ansc;
ansk=ansf=ansc=0;
for(int i=1;i<=n;i++)//枚举长度为奇数情况下第i个位置为中心点的回文子串数目
{
int l=0,r=min(n-i,i-1);
while(l<r)
{
int mid=l+r+1>>1;
if(get(i-mid,i+mid,1)==get(i-mid,i+mid,2)) l=mid;
else r=mid-1;
}
ansk+=sk[i+l]-sk[i-1];
ansf+=sf[i+l]-sf[i-1];
ansc+=sc[i+l]-sc[i-1];
}
for(int i=1;i<=n;i++)//枚举长度为偶数情况下第i个位置为两个中心点左边的那个中心点的回文子串数目
{
int l=0,r=min(n-i,i);
while(l<r)
{
int mid=l+r+1>>1;
if(get(i-mid+1,i+mid,1)==get(i-mid+1,i+mid,2)) l=mid;
else r=mid-1;
}
if(l==0) continue;
ansk+=(sk[i+l]-sk[i-l])/2;
ansf+=(sf[i+l]-sf[i-l])/2;
ansc+=(sc[i+l]-sc[i-l])/2;
}
printf("%lld %lld %lld\n",ansk,ansf,ansc);
}
return 0;
}
边栏推荐
猜你喜欢
随机推荐
Base64编码原理
如何画一张架构图(内含知识图谱)
IDEA如何创建同级工程
ClickHouse - Getting Started
Senior ClickHouse -
金仓数据库 Pro*C 迁移指南(3. KingbaseES Pr*oc 对 Oracle Pro*c 的兼容)
一文了解SAP IBP是什么?
leetcode:149. 直线上最多的点数
QT之鼠标和键盘事件重写
找不到符号@SuperBuilder,你以为真的是Lombok的问题?
Auto.js Pro 编写第一个脚本hello world
Pro * C Jin Cang database migration guide (4) KingbaseES Pro * C migration guide)
网工知识角|华为网络工程师,华为、华三、思科设备三层交换机如何使用三层接口?命令敲起来
Domino服务器SSL证书安装指南
PyTorch installation - error when building a virtual environment in conda before installing PyTorch
ROS2自学笔记:机器视觉基础
基于flowable的upp(统一流程平台)运行性能优化(3)
Dynamically modify the title of the navigation bar in uniapp
els 计分
Go新项目-编译项目的细节(4)