自动搬运

查看原文

来自洛谷，原作者为

	BEST_CAT **

搬运于2025-08-24 22:41:43，当前版本为作者最后更新于2023-02-26 11:34:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8715 [蓝桥杯 2020 省 AB2] 子串分值 题解

思路一

这题首先想到的是暴力：

1. 枚举区间左端点。
2. 枚举区间右端点。
3. 遍历当前所枚举的区间，累加仅出现一次的字母个数。

代码

时间复杂度为 $O(n^3)$，提交后就能 TLE 了。

思路二

我们不妨稍微优化一下，这里就不细说了，直接上代码。

代码

时间复杂度为 $O(n^2)$，提交后就又能 TLE 了。

思路三（正解）

用乘法原理做。

操作步骤：

1. 统计每个字母在只出现一次的情况下，能被多少子串所包含；
2. 用 $pre_i$ 记录第 $i$ 个字母上一次出现的位置，用 $nx_i$ 记录第 $i$ 个字母下一次出现的位置；
3. 那么往左最多能延伸到 $pre_i+1$，其到第 $i$ 个字母一共有 $i-pre_i$ 个字母；
4. 同理往右最多能延伸到 $nx_i-1$，其到第 $i$ 个字母一共有 $next_i-i$ 个字母；
5. 二者相乘，就是该字母被不同子串所包含的总次数；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010,M=150;
string s;
ll pre[N],nx[N],idx[M];
int main(){
    cin>>s;
    ll n=s.size();
    s=' '+s;
    for(int i=1;i<=n;i++){
        pre[i]=idx[s[i]];
        idx[s[i]]=i;
    }
    for(int i=97;i<=122;i++){
        idx[i]=n+1;
    }
    for(int i=n;i>=1;i--){
        nx[i]=idx[s[i]];
        idx[s[i]]=i;
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=(i-pre[i])*(nx[i]-i);
    }
    cout<<ans;
    return 0;
}

时间复杂度：$O(n)$，提交之后发现：终于过了。