文章

子串分值和(2020省赛)

子串分值和.png

1 暴力(会超时)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<char,ll>mp;
int main()
{
    ll ans=0,i,k,j;
    string s;
    cin>>s;
    ll n=s.length();
    for(i=1;i<=n;i++){//子串字符个数 
        for(j=0;j+i<=n;j++){//起始点 
            mp.clear();
            for(k=j;k<=j+i-1;k++){//每个子串 
                if(mp[s[k]]==0){
                    mp[s[k]]=1;
                    ans++;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
 }

2 正解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100];
int main()
{
    ll ans=0,sum=0,i;
    string s;
    cin>>s;
    ll n=s.length();
    for(i=0;i<n;i++){
        sum=sum-a[s[i]-'a']+i+1;
        a[s[i]-'a']=i+1;
        ans+=sum;
    }
    cout<<ans<<endl;
    return 0;
 } 

原题链接

https://www.lanqiao.cn/problems/1037/learning/

License:  CC BY 4.0