子串分值和
對于一個字串 S，我們定義 S 的分值 f(S)為 S 中出現的不同的字符個數，
例如f(“aba”)=2，f(“abc”)=3，f(“aaa”)=1，
現在給定一個字串 S[0…n?1]（長度為 n），請你計算對于所有 SS 的非空子串S[i…j] (0≤i≤j<n)，f(S[i…j]) 的和是多少，
輸入格式
輸入一行包含一個由小寫字母組成的字串 SS，
輸出格式
輸出一個整數表示答案，
資料范圍
對于 20%20% 的評測用例，1≤n≤10；
對于 40%40% 的評測用例，1≤n≤100；
對于 50%50% 的評測用例，1≤n≤1000；
對于 60%60% 的評測用例，1≤n≤10000；
對于所有評測用例，1≤n≤100000，
輸入樣例：
ababc
輸出樣例：
28
解題思路
分析
該題如果暴力列舉則是一個 O ( n 2 ) O(n^2) O(n2)的復雜度
很顯然當n到10000時測評就很難通過
那么我們就要考慮一下有什么方法可以優化到 O ( n l o g n ) O(nlogn) O(nlogn), O ( n ) O(n) O(n)以內舉例
按樣例的列舉如下圖劃分，我們就可以將本題轉換成一個計算每個字符貢獻的情況
①先舉一個沒有重復的例子，他的每個字母出現的次數
s[i]:a b c d e
f[i]:5 8 9 8 5
有沒有看出什么，沒有？那我們再細分
1*5 2*4 3*3 4*2 5*1
是不是看出了些什么(#.#)
②再來看一個有重復了例子
s[i]:a b a b c
f[i]:5 8 6 4 5
如下圖所示第3個位置a出現了三段，與一段與第1個位置a發生了重復(舍去[ f[i] * 1/3 ])
如下圖所示第4個位置a出現了三段，與兩段與第2個位置a發生了重復(舍去[ f[i] * 2/4 ])
那么我么只需開一個陣列last[]記錄上一個字母s[i]出現的最后位置即可知道多少位置發生重復
重復a 3:(9-91/3)
重復b 4:(8-82/4)推公式
重復s[i]： f[i] - f[i] / i*last[s[i]]
樣例解釋
子串 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
代碼
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
char s[N];
ll f[N]; //預處理會爆int
int last[30];
int main(){
scanf("%s",s+1);
int n = strlen(s+1);
ll ans = 0;
//預處理沒有任何重復的情況；
for(int i=1;i<=n-i+1;i++)f[i] = f[n-i+1] = (n-i+1)*(ll)i; //注意乘的時候一定要轉long long
//統計總貢獻，并去重
for(int i = 1;i<=n;i++){
int t = s[i]-'a';
if(!last[t]){ //判斷有無重復部分
ans += f[i];
}else{
ans += f[i] - f[i]/i*last[t]; //減去重復部分；
}
last[t] = i; //記錄當前字母最后出現位置
}
printf("%lld",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/275036.html
標籤：其他
上一篇：2021曲阜師范大學校賽題解
下一篇：C++類中的六大默認成員函式