题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
char str[N];
bool st[30];
long long ans;
int main()
{
scanf("%s", str + 1);
int n = strlen(str + 1);
long long ans = 0;
for(int i = 1; i <= n; i ++) {
memset(st, 0, sizeof st);
int t = str[i] - 'a';
st[t] = true;
int cnt = 1;
ans += cnt;
for(int j = i + 1; j <= n; j ++) {
int t = str[j] - 'a';
if(!st[t]) {//未出现过该字符, 分数+1
cnt ++;
st[t] = true;
}
ans += cnt;
}
}
printf("%lld", ans);
}
算法2
(dp) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
char str[N];
typedef long long LL;
int pos[26];//记录每个字符最后一次出现的位置
int f[N];
int main() {
scanf("%s", str + 1);
int n = strlen(str + 1);
LL ans = 0;
for(int i = 1; i <= n; ++i) {
int t = str[i] - 'a';
f[i] = f[i - 1] + i - pos[t];
pos[t] = i;
ans += f[i];
}
printf("%lld\n", ans);
return 0;
}