当前位置: 首页 > news >正文

赛前训练4 字符串哈希

A

显然长度具有单调性,于是二分长度+map存储哈希值判断即可。

实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define ull unsigned long long
#define int long long
using namespace std;const int N=2e4+5;
const ull BASE=13331;
int n,k;
int a[N];
ull P[N],H[N];
string s;
map<ull,int> mp;int get(int l,int r){return H[r]-P[r-l+1]*H[l-1];
}
bool check(int x){for(int i=1;i+x-1<=n;i++){int h=get(i,i+x-1);mp[h]++;if(mp[h]==k)return 1;}return 0;
}signed main(){ios::sync_with_stdio(0);//cin.tie(0);cin>>n>>k;P[0]=1;for(int i=1;i<=n;i++)cin>>a[i],H[i]=H[i-1]*BASE+a[i],P[i]=P[i-1]*BASE;int l=0,r=n+1;while(l+1<r){int mid=(l+r)>>1;//cout<<mid<<'\n';if(check(mid))l=mid;elser=mid;}cout<<l;return 0;
}

B

把所有回文子串预处理出来然后树状数组统计即可。

实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
using namespace std;const int N=2e3+5;
const ull BASE=13331;
int n,tot;
ull P[N],H1[N],H2[N];
pii p[N*N];
int tree[N];
string s;int geth1(int l,int r){return H1[r]-P[r-l+1]*H1[l-1];
}
int geth2(int l,int r){return H2[l]-P[r-l+1]*H2[r+1];
}
bool cmp(pii &x,pii &y){if(x.first==y.first)return x.second<y.second;return x.first<y.first;
}
int lowbit(int x){return x&-x;
}
void upd(int x,int y){for(;x<=n;x+=lowbit(x))tree[x]+=y;
}
int qry(int x){int res=0;for(;x;x-=lowbit(x))res+=tree[x];return res;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>s;n=s.size(),s='#'+s;P[0]=1;for(int i=1;i<=n;i++)P[i]=P[i-1]*BASE,H1[i]=H1[i-1]*BASE+s[i];for(int i=n;i>=1;i--)H2[i]=H2[i+1]*BASE+s[i];for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)if(geth1(i,j)==geth2(i,j))p[++tot]={i,j};sort(p+1,p+tot+1,cmp);int ans=0;for(int i=tot;i>=1;i--){ans+=qry(n)-qry(p[i].second);upd(p[i].first,1);}cout<<ans;return 0;
}

C

删掉本来就回文的前后缀,剩下的变成删除前缀/后缀的问题,可以枚举删掉的长度然后二分最长回文前后缀的长度用哈希判断即可。

实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
#define ull unsigned long long
using namespace std;const int N=5e5+5;
const ull BASE=13331;
int n;
ull P[N],H1[N],H2[N];
string s;int geth1(int l,int r){return H1[r]-P[r-l+1]*H1[l-1];
}
int geth2(int l,int r){return H2[l]-P[r-l+1]*H2[r+1];
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>s,n=s.size(),s='#'+s;P[0]=1;for(int i=1;i<=n;i++)P[i]=P[i-1]*BASE,H1[i]=H1[i-1]*BASE+s[i];for(int i=n;i>=1;i--)H2[i]=H2[i+1]*BASE+s[i];int l=1,r=n;while(l<r&&s[l]==s[r])l++,r--;int ans=l-1;if(l>=r){cout<<ans;return 0;}int extra=-1e18;for(int i=l;i<=r;i++){int lt=-1,rt=(r-i+1)/2+1;while(lt+1<rt){int mid=(lt+rt)>>1;if(geth1(i,i+mid-1)==geth2(r-mid+1,r))lt=mid;elsert=mid;}extra=max(extra,lt);}for(int i=r;i>=l;i--){int lt=-1,rt=(i-l+1)/2+1;while(lt+1<rt){int mid=(lt+rt)>>1;if(geth1(l,l+mid-1)==geth2(i-mid+1,i))lt=mid;elsert=mid;}extra=max(extra,lt);}cout<<ans+extra;return 0;
}

D

取反之后正反各做一遍哈希,然后注意到这个题的回文子串必定是偶数长度的,于是统计回文子串的数量即可。这是经典套路。(即枚举对称中心二分半径)

实现
//
//  C.cpp
//
//
//  Created by _XOFqwq on 2024/10/23.
//#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;const int N=5e5+5;
const int BASE=13331;
int n,ans;
ull hs1[N],hs2[N],p[N];
string s;void init_hs(){p[0]=1;for (int i=1; i<=n; i++) {hs1[i]=hs1[i-1]*BASE+s[i];p[i]=p[i-1]*BASE;}for (int i=n; i>=1; i--) {hs2[i]=hs2[i+1]*BASE+(s[i]=='0'?'1':'0');}
}
ull get_hs1(int l,int r){return hs1[r]-hs1[l-1]*p[r-l+1];
}
ull get_hs2(int l,int r){return hs2[l]-hs2[r+1]*p[r-l+1];
}
bool check(int pos,int x){int l=pos-x+1,r=pos+x;return get_hs1(l,r)==get_hs2(l,r);
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>s,s='#'+s;init_hs();for (int i=1; i<n; i++) {int l=0,r=min(i,n-i)+1;while (l+1<r) {int mid=(l+r)>>1;if (check(i,mid)) {l=mid;} else {r=mid;}}ans+=l;}cout<<ans;return 0;
}

总结:

  • 二分长度+哈希

  • 枚举中心点+二分长度统计回文子串数量。

http://www.hskmm.com/?act=detail&tid=23086

相关文章:

  • 英语
  • 处处吻
  • ThreadLocal原理与使用详解
  • WinCC监控框架实战解析:打通物联网网关的关键步骤
  • 2025国庆Day1
  • 2025 年包装印刷厂家 TOP 企业品牌推荐排行榜,西安,陕西,咸阳包装印刷,礼盒,定制,设计,优质,品质,环保,生产包装印刷公司推荐!
  • 2025 绝对式编码器厂家 TOP 企业品牌推荐排行榜,增量绝对式编码器,多圈绝对式编码器,二进制绝对式编码器 /ssi 绝对式编码器,拉线绝对式编码器公司推荐!
  • 2025 编码器厂家 TOP 企业品牌推荐排行榜,无磁,光学,脉冲,绝对型,伺服,机械多圈,工业,二进制,拉线编码器公司推荐
  • 2025 年玻璃钢水箱厂家 TOP 企业品牌推荐排行榜,30 吨,订做,消防,专业,方形,拼装式,屋顶,大型玻璃钢水箱推荐这十家公司!
  • 禁止DataGridView自动根据数据源的结构生成列
  • 2025 年压球机厂家 TOP 企业品牌推荐排行榜,新型,高压,节能,双螺旋干粉,对辊,煤粉,超低压压球机公司推荐!
  • 2025 年磨粉机厂家 TOP 企业品牌推荐排行榜,新型磨粉机,超细磨粉机,立式双动力磨粉机,节能磨粉机公司推荐!
  • 2025 年等离子清洗机厂家 TOP 企业品牌推荐排行榜,大气,真空,宽幅,微波,自动化,常压,低温,大腔体,射频,DBD,介质阻挡放电等离子清洗机公司推荐!
  • 完整教程:如何优雅的布局,height: 100% 的使用和 flex-grow: 1 的 min-height 陷阱
  • MyBatis缓存架构深度拆解:从PerpetualCache的LRU陷阱到Redis分布式二级缓存防穿透实战 - 详解
  • 2025柔版印刷机厂家 TOP 企业品牌推荐排行榜,塑编袋,编织袋,阀口袋,重包膜,机组式,卫星式,不换版,FFS 重载膜,水泥袋柔版印刷机公司推荐!
  • 9 30 -
  • Spring 基础核心 - SpringMVC 入门与请求流程
  • (数据结构)链表OJ——刷题练习 - 实践
  • 阿尔法开发板移植ov5640时候一个小的注意事项
  • 使用kraken2 命令对重测序数据进行物种分类
  • 2025/10/2
  • 重测序数据fastp数据质控及fastQC质量评估
  • 8. Spring AI tools/function-call - 教程
  • electron 安装失败
  • 2025担保合同律师事务所推荐,专业团队高效解决法律难题!
  • 10.1 CSP模拟26 改题记录
  • Spring 核心 - AOP 面向切面编程入门, 通俗易懂
  • 2025年筒袋磁力泵实力厂家推荐榜:高效耐用与创新技术深度解
  • 2025电源适配器权威推荐榜:高效稳定、安全耐用的优质品牌之