NOIP2024模拟赛13:拆开未来
C-重复
-
一句话题意:给定字符串 \(S\), 问 \(S\) 的所有子串共有多少种“好的拆分方案”。对于一个字符串 \(S\), 一个划分是好的当且仅当能把 \(S\) 划分成 6 个非空子串 \(a,b,c,d,e\), 满足 \(a=b=e, \ c=f\) (一个字符串可能有多种划分方式)
-
标签:前缀和,思维,散列表(哈希)
-
简化一下就是要满足 \(AABCAB\).
-
60分的暴力是对每一个区间枚举开头的 \(A\) 和结尾的 \(B\). (P.S.模数设 \(998244353\) 会被卡!!!)
const int N=5005; const ll P=131; ull h[N],p[N]; char s[N]; int n; ll ans=0; ull get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; } void solve(int l,int r){ int len=r-l+1; F(i,1,len/3) for(int j=1;j<=len/2 && 3*i+2*j<len;++j){ ull A=get(l,l+i-1),B=get(l+i,l+2*i-1),C=get(l+2*i,l+2*i+j-1),E=get(r-i-j+1,r-j),F=get(r-j+1,r); if(A == B && B == E && C == F) ++ans; } } signed main(){ freopen("c.in","r",stdin); freopen("c.out","w",stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>(s+1); n=strlen(s+1); p[0]=1; F(i,1,n) h[i]=h[i-1]*P+s[i]-'0',p[i]=p[i-1]*P; F(l,1,n) F(r,l+5,n) solve(l,r); cout<<ans; return 0; }
-
但正如邓老师所说,这种拆分方式是“不平衡的”,虽然我们可以用 \(O(1)\) 的时间去检查剩下的位置,但我们却需要花 \(O(N^2)\) 的时间枚举所有的首尾情况。
-
所以正解我们选择枚举 \(AB\). 枚举 \(A\) 的左端点 \(i\) 和 \(B\) 的右端点 \(j\).
-
对于 \(AA\), 在固定 \(i\) 的情况下可以用前缀和处理所有贡献。
-
对于 \(AB\) 和后面那个 \(AB\) 的匹配, 把所有已经扫到过的 \(AB\) 存进一个散列表并统计其个数(\(unorderedmap\) 会 T掉)
-
两者的贡献相乘即是单次的总贡献。
-
注意循环的初末条件,\(C\) 不为空(详见代码)
#include<bits/stdc++.h>
#define F(i,l,r) for(register int i(l);i<=r;++i)
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N=5005;
const ll P=131;
ull h[N],p[N];
char s[N];
int n; ll ans=0;
ull get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; }
void solve(int l,int r){
int len=r-l+1;
F(i,1,len/3) for(int j=1;j<=len/2 && 3*i+2*j<len;++j){
ull A=get(l,l+i-1),B=get(l+i,l+2*i-1),C=get(l+2*i,l+2*i+j-1),E=get(r-i-j+1,r-j),F=get(r-j+1,r);
if(A == B && B == E && C == F) ++ans;
}
}
signed main(){
freopen("c.in","r",stdin); freopen("c.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>(s+1); n=strlen(s+1); p[0]=1;
F(i,1,n) h[i]=h[i-1]*P+s[i]-'0',p[i]=p[i-1]*P;
F(l,1,n) F(r,l+5,n) solve(l,r);
cout<<ans;
return 0;
}
标签:13,AB,int,拆开,枚举,solve,NOIP2024
From: https://www.cnblogs.com/superl61/p/18262528