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

· · 题解

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)，提交之后发现：终于过了。