C/C++教程

hdu7055 /2021“MINIEYE杯”中国大学生算法设计超级联赛(7) 1012 Yiwen with Sqc

本文主要是介绍hdu7055 /2021“MINIEYE杯”中国大学生算法设计超级联赛(7) 1012 Yiwen with Sqc,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

https://acm.hdu.edu.cn/showproblem.php?pid=7055

 

给出一个只含有小写字母组成的串s

sqc(s,l,r,c)表示字符c在s的[i,j]内的出现次数

 

 

设f[i]表示以i结尾的子区间字符串的答案

考虑从f[i]推到f[i+1]

由i到i+1,假设s[i+1]=c,那么除了字母c之外的其他字母x,sqc(s,L,i,x)=sqc(s,L,i+1,x)

对于字母c

sqc(s,L,i+1,c)^2 = (sqc(s,L,i,c)+1)^2 = sqc(s,L,i,c)^2 + 1 + 2*sqc(s,L,i,c) , L∈[1,i]

sqc(s,L,i+1,c)^2 = 1  , L=i+1 

所以f[i+1]=f[i]+ ∑(1+2*sqc(s,L,i,c) ) + 1   ,L∈[1,i]

即 f[i+1]=f[i]+2*∑sqc(s,L,i,c)  +  i+1  L∈[1,i]

维护一下 ∑sqc(s,L,i,c) 即可

当从i变为i+1时, ∑sqc(s,L,i,c) 会加i,因为L∈[1,i]的每个[L,i+1]都会加上一个i+1位置的c

#include<bits/stdc++.h>

using namespace std;

#define N 100003

char s[N];
int f[N],sum[27];

const int mod=998244353; 

int main()
{
    int T,n,ans;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        for(int i=1;i<=26;++i) sum[i]=0;
        ans=0;
        for(int i=1;i<=n;++i)
        {
            f[i]=(f[i-1]+2*sum[s[i]-'a'+1]%mod+i)%mod;
            ans=(ans+f[i])%mod;
            sum[s[i]-'a'+1]=(sum[s[i]-'a'+1]+i)%mod;
        }
        printf("%d\n",ans);
    }
}

 

 

这篇关于hdu7055 /2021“MINIEYE杯”中国大学生算法设计超级联赛(7) 1012 Yiwen with Sqc的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!