子串分值和 - 蓝桥云课 (lanqiao.cn)

题目描述

题目分析 

以下为50分方法（暴力枚举）

第一层循环枚举其长度，第二层循环枚举其左端点，k代表右端点，（将每一种子串一一枚举出来）算出从左端点到右端点的不同的字符，使用ans来记录最终的答案

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll ans;    
string s;
bool v[N];
ll sum(ll l, ll r)
{ll res = 0;for(ll i = l; i <= r; i ++)v[s[i] - '0'] = 0;for(ll i = l; i <= r; i ++){if(!v[s[i] - '0']){v[s[i] - '0'] = 1;res ++;}}
//    cout << res << '\n';return res;
}
int main()
{cin >> s;ll n = s.size();for(ll i = 1; i <= n; i ++){for(ll j = 0; j < n; j ++){ll k = j + i - 1;if(k < n){ans += sum(j, k);//    cout << j << ' ' << k << '\n';}}}cout << ans;return 0;
}

满分解法：（使用DP）

使用pre记录上一次字符出现的位置

计算当前字符对整个字符串的贡献：

如果当前字符串没出现过，就是对整个字符串都有贡献，不然就只对上一次出现之后的排列做了贡献

eg.i == 1第一次出现，sum += 1 * 后面的长度

     i == 6，在i == 3出现，sum += 3 * (6 - 3) [6 - 3为上一次出现之后的字符的长度（后面的长度）]

     等号后面的第一个3为上一次i出现的位置

如下：ababc中第1个b可以提供8点贡献，(2 - 0) * (5 - 2 + 1) = 8

第2个b可以提供4点贡献，(4 - 2) * (5 - 4 + 1) = 4

eg.

opababc

第二个a做出贡献的字符串为babc的排列，opa（在第二个a之前已经被第一个a做过了贡献）

注意开long long 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
string s;
ll sum, pre[N];
int main()
{cin >> s;ll n = s.size();s = '0' + s;for(ll i = 1; i <= n; i ++){sum += (i - pre[s[i] - 'a']) * (n - i + 1);pre[s[i] - 'a'] = i;}cout << sum << '\n';return 0;
}