HDU7015 Another String
Sol
考虑预处理 F[i][j] 表示以下标 i 为左端点的字符串和以下标 j 为左端点的字符串 , 在满足 k 匹配的条件下 , 最长能匹配 F[i][j] 的长度
也就是 S[i+L-1] 与 S[j+L-1] 满足 K 匹配 , 这个 L 是最大的 , 且两个串不相交
(还要满足 j+L-1 \leq n 且 i+L-1
利用双指针预处理 O(n^2)
for(int st=2;st<=n;++st){
int diff = 0 ,L = 0 ;//, p = st;
for(int q=1,p=st;q<=n;++q,++p){
while(q+L<p&&p+L<=n&&(diff<k||diff<=k&&s[q+L]==s[p+L])){
diff+=s[q+L]!=s[p+L];
L++;
}
f[q][p] = L;
diff-=s[q]!=s[p];
L--;
}
}
考虑我们要统计的答案是
\sum_{i=1}^{t-1}\sum_{j=t}^nF[i][j]
里面的式子就表示, t 状态下, 两个匹配串以 i,j 为左端点,有 F[i][j] 个串可以 k 匹配
现在要求快速统计这个式子.
然后考虑 t 将字符串 S , 分割为 A[1…t-1] 和 B[t…n] ( 2\leq t\leq n )
考虑 A 中的一个子串 s[i,j] 与 B 的一个子串 t[p,q] 匹配
显然当 j\leq t-1 且 t\leq p 时 ,这两个子串会一直处于匹配状态
也就是说当 t 递减时 , 对一对满足 k 匹配的 (s[i,j] ,t[p,q]) 串来说 ,
t 递减到 p 时 , 会开始对答案有贡献 ; t 递减到 j 时 , 就不再对答案有贡献了
然后我们考虑按照 t 递减的顺序计算答案
当 t \to t-1 时 , 看看答案发生了什么改变 :
① 要删去原本 A 串中以 t-1 为右端点和 B 串中以 [t,n] 中的点为左端点 k 匹配的贡献
② 要加上 A 串中 以[1,t-2] 为左端点 与 B 串中以 t 为左端点的子串的 k 匹配贡献
理解了这个 , 看官方题解即可
#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
char s[N];
int mx[N],f[N][N],k,n,T,cnt[N][N],ANS[N];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
scanf(" %s",s+1);
for(int st=2;st<=n;++st){
int diff = 0 ,L = 0 ;//, p = st;
for(int q=1,p=st;q<=n;++q,++p){
while(q+L<p&&p+L<=n&&(diff<k||diff<=k&&s[q+L]==s[p+L])){
diff+=s[q+L]!=s[p+L];
L++;
}
f[q][p] = L;
diff-=s[q]!=s[p];
L--;
}
}
for(int i=1;i<=n;++i){
mx[i] = n/2+1;
for(int j=1;j<=n;++j)
cnt[i][j]=0;
}
int ans = 0 ;
for(int t=n;t;--t){
for(int i=1;i+1<=t;++i){
while(mx[i]>t-i){
ans-=cnt[i][mx[i]];
cnt[i][mx[i]-1]+=cnt[i][mx[i]];
mx[i]--;
}
}
for(int i=1;i+1<=t;++i){
int g = f[i][t];
cnt[i][g]++;
ans+=g;
}
ANS[t]=ans;
if(mx[t-1]>0){
ans-=cnt[t-1][1];
mx[t-1]--;
}
}
for(int i=2;i<=n;++i)
printf("%d\n",ANS[i]);
}
return 0;
}
0 条评论