2023-05-20 14:34:56 P6273 题解
原题链接 魔法
题目分析
题目的意思就是让我们求每个字母出现次数相同且不为空的子串的个数。
基本思路
然后我们能想到维护一个前缀和数组，然后判断区间是否满足条件只需要判断每个颜色是否出现次数都相同即可，可 \(O(n^2k)\) 实现。
但是由于我之前双指针打多了，然后想到用两个指针来维护每个颜色都出现了的区间（因为这个区间颜色全部出现是满足魔法子串的必要条件）。然后再用跳格的方式先找到第一个满足条件的 \(r\)，此时如果之后的从这个 \(l\) 为起点的区间为魔法子串，显然其 \(r\) 都得在第一个满足条件的魔法子串上加上 \(k\) 的正整数倍。
这仅仅只是基于暴力的一个小优化，显然复杂度还不够优，计算次数还是大于方案数。接下来考虑一点点转移，我们设 \(f[i]\) 为以 \(i\) 为终点的满足条件的子串个数，显然，当我区间 \(l,r\) 满足条件时，我的 \(f[r]=f[r]+f[l-1]+1\)。
这个复杂度不稳定，数据水基本上就可以过了（然而被卡了两个点）。
Code 1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
unordered_map<char,int>S;
int n,cnt,sum[56][100005];
string ss;
ll f[100005];
bool check_appear(int l,int r){//全部元素出现
for(int i=1;i<=cnt;i++){
if(!(sum[i][r]-sum[i][l-1]))return 0;
}
return 1;
}
bool check_num(int l,int r){//满足条件
for(int i=2;i<=cnt;i++){
if(!(sum[i][r]-sum[i][l-1]==sum[i-1][r]-sum[i-1][l-1]))return 0;
}
return 1;
}
int nex_num(int l,int r){//跳格
int maxx=0;
for(int i=1;i<=cnt;i++){
maxx=max(maxx,sum[i][r]-sum[i][l-1]);
}
int res=0;
for(int i=1;i<=cnt;i++){
res+=maxx-(sum[i][r]-sum[i][l-1]);
}
return r+res;
}
int main(){
cin>>n>>ss;
for(int i=0;i<n;i++){
if(!S[ss[i]])S[ss[i]]=++cnt;//用了个map存序号（小题大做）
sum[S[ss[i]]][i+1]+=1;
for(int j=1;j<=cnt;j++){
sum[j][i+1]+=sum[j][i];//前缀和
}
}
for(int l=1,r=1;r<=n;l++){
while(!check_appear(l,r)&&r<=n)r++;//必要条件
if(r>n)continue;
int R=r;
while(!check_num(l,R)&&R<=n)R=nex_num(l,R);//找第一个满足条件的区间
if(R>n)continue;
(f[R]+=f[l-1]+1)%=mod;//小小的转移
}
ll ans=0;
for(int i=1;i<=n;i++){
(ans+=f[i])%=mod;//累加
}
cout<<ans;
}
进一步优化
我们观察到我们的 \(r\) 的跳格的复杂度是不稳定的，以及这个双指针操作也是冗余的。
然后想起教练常谈多看部分分，通过观察第三个 \(k=2\) 的部分分，想到 \(sum_a [r]-sum_a[l-1]=sum_b[r]-sum_b[l-1]\)，即为区间满足的条件，左右交换，可以得到 \(sum_a [r]-sum_b[r]=sum_a[l-1]-sum_b[l-1]\)。
那发现只要对于一个区间，任意两个颜色都满足以上条件的话也能满足条件，然而直接转移常数太大，我们发现对于颜色 \(x\)，设字符串中存在字符 \(c\)，只要对于每个颜色都满足 \(sum_x[r]-sum_c[r]=sum_x[l-1]-sum_c[l-1]\) 都成立，我们就可以通过这个式子通过小学加减推广到全部的式子使其也满足对于任意两个颜色 \(x,y\) 也满足 \(sum_x [r]-sum_y[r]=sum_x[l-1]-sum_y[l-1]\)。
然后我们从后往前递推，用 \(nex\) 数组记录每个数最近的满足条件的 \(r\) 值，即可将每次查询第一个 \(r\) 优化到 \(O(1)\) 。
那怎么存呢？用万能的 unordered_map 和哈希表即可。
Code 2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod=1e9+7;
unordered_map<char,int>S;
unordered_map<ull,int>W;
int n,cnt,sum[56][100005],nex[100005];
string ss;
ll f[100005];
ull p[56];
ull gett(int x){
ull res=0;
for(int i=2;i<=cnt;i++){
if(sum[i][x]-sum[1][x]>0)res=res+p[i-2]*(ull)(sum[i][x]-sum[1][x]);
else res=res-p[i-2]*(ull)(sum[1][x]-sum[i][x]);
}//哈希值的转换（采用unsigned long long 自然溢出）
return res;
}
int main(){
cin>>n>>ss;
p[0]=1;
for(int i=1;i<=53;i++){
p[i]=p[i-1]*257;//存哈希乘值
}
for(int i=0;i<n;i++){
if(!S[ss[i]])S[ss[i]]=++cnt;
sum[S[ss[i]]][i+1]+=1;
for(int j=1;j<=cnt;j++){
sum[j][i+1]+=sum[j][i];
}
}
for(int i=n;~i;--i){
ull o=gett(i);
if(W[o])nex[i+1]=W[o];//注意这里i点满足应该转移到i+1
W[o]=i;
}
for(int l=1;l<=n;l++){
if(!nex[l])continue;
int R=nex[l];
(f[R]+=f[l-1]+1)%=mod;//超级精简稳定的转移
}
ll ans=0;
for(int i=1;i<=n;i++){
(ans+=f[i])%=mod;
}
cout<<ans;
}
感谢你看我这个蒟蒻写的文章，希望对你的理解有帮助！