樣例輸入：
ababc
樣例輸出：
28
樣例說明：
子串 f值
a 1
ab 2
aba 2
abab 2
ababc 3
b 1
ba 2
bab 2
babc 3
a 1
ab 2
abc 3
b 1
bc 2
c 1
評測用例規(guī)模與約定
對于20%的評測用例，1<=n<=10骚灸；
對于40%的評測用例辅甥，1<=n<=100洗做；
對于50%的評測用例，1<=n<=1000址芯；
對于60%的評測用例灾茁，1<=n<=10000；
對于所有評測用例谷炸，1<=n<=100000北专。
閑話
先暴力一下試試，過了四個旬陡。
#include <stdio.h>
#include <string.h>
#include <set>
using namespace std;
char s[100010];
int sum = 0;
int f(int a, int b) {
int temp = 0;
set<char> p;
for(int i = a; i < b; i++) {
p.insert(s[i]);
if(p.size() == 26) {
return 26;
}
}
return p.size();
}
int main() {
scanf("%s", s);
int len = strlen(s);
for(int i = 0; i < len; i++) {
for(int j = i + 1; j <= len; j++) {
sum += f(i, j);
}
}
printf("%d", sum);
return 0;
}
不過看起來后面測試點結果應該是超過10^9了拓颓，該用長整型了。
ac思路：
字符分值(豎著看)：
5 8 9 8 5
有貢獻分值：
5 8 6 4 5
a
a b
a b a
a b a b
a b a b c
b
b a
b a b
b a b c
a
a b
a b c
b
b c
c
先看這個描孟，這是所有子串的集合驶睦。
如果我們豎著看，這個問題就可以理解為：遍歷每一個字符串s的字符匿醒，判斷它是否為我們的答案做出了貢獻场航。
先看0號字符，它的值是a廉羔。它前面沒有什么字符溉痢，于是也沒有什么字符和它相同，所以它的貢獻就是這一豎排的長度。
1號字符b也是一樣的道理孩饼，貢獻數就是這一豎排的長度（i+1)×(l-i)髓削。
這里i代表下標，l代表s的總長度镀娶。
但是我們看到2號字符a的時候立膛，結果就不太一樣了。
0號字符的值也是a汽畴，于是2號字符對于結果的貢獻就不是從它開始的字符串長度了旧巾，我們需要減去一些東西。
由于重復的是無效的忍些，于是我們要讓之前的字符沒有a鲁猩，通過觀察筹麸，我們發(fā)現每往下走一組皂甘，前面的字符就少一個，那我們就一直往下走到前面沒有相同的字符不就可以了婴削？
我們記i號字符的值上一次出現的位置為pre[i]嘁酿，那么我們就可以往下走pre[i]+1個組就可以了隙券。
那么最終的貢獻值就是(i+1)×(l-i)-(pre[i]+1)×(l-i)=(i-pre[i])×(l-i)。
然后闹司，為了讓我們的公式更具普遍性娱仔，我們做如下規(guī)定：如果i對應的值在前面從未出現過，那pre[i]=-1游桩。
下面的問題也就僅僅是計算pre[i]了牲迫，這點比較容易，我就不寫了借卧。
附上AC代碼：
AC：
#include<stdio.h>
#include<string.h>
const int N = 100010;
typedef long long ll;
ll pre[N];
char s[N];
ll last[26];//這里用0~25來代替每個字母盹憎，代表對應的字母上一次出現的下標
ll sum=0;
int main()
{
scanf("%s", s);
ll l=strlen(s);
for(ll i = 0; i < 26; i++) {
last[i] = -1;
}
for(ll i = 0; i < l; i++) {
ll k = s[i] - 'a';
pre[i] = last[k];
last[k] = i;
}
for(ll i = 0; i < l; i++) {
sum += (l-i) * (i-pre[i]);
}
printf("%lld",sum);
return 0;
}
