試題 H: 子串分值和
時間限制: 1.0s 記憶體限制: 256.0MB 本題總分：20 分
【問題描述】
對于一個字串 S，我們定義 S 的分值 f(S ) 為 S 中出現的不同的字符個
數，例如 f(”aba”) = 2，f(”abc”) = 3, f(”aaa”) = 1，
現在給定一個字串 S [0..n 1]（長度為 n），請你計算對于所有 S 的非空
子串 S [i.. j](0 ≤ i ≤ j < n)，f(S [i.. j]) 的和是多少，
【輸入格式】
輸入一行包含一個由小寫字母組成的字串 S，
【輸出格式】
輸出一個整數表示答案，
【樣例輸入】
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
【評測用例規模與約定】
對于 20% 的評測用例，1 ≤ n ≤ 10；
對于 40% 的評測用例，1 ≤ n ≤ 100；
對于 50% 的評測用例，1 ≤ n ≤ 1000；
對于 60% 的評測用例，1 ≤ n ≤ 10000；
對于所有評測用例，1 ≤ n ≤ 100000，
思路:
以ababc為例
定義一個陣列存放每個字母出現的次數,len表示不是0的字母的個數
第一次for回圈從左往右
那么每訪問一個字符,次數++
| 當前串 | 狀態 |
|---|---|
| a | len = 1 ,a = 1 |
| ab | len = 2 ,a = 1, b = 1 |
| aba | len = 2 , a = 2, b = 1 |
| abab | len = 2 ,a = 2, b = 2 |
| ababc | len = 3 , a = 2, b = 2, c = 1 |
接下來,for回圈從左到右,但是洗掉字串最左邊的值
| 當前串 | 狀態 |
|---|---|
| babc | a-- , len = 3 a = 1, b = 2, c = 1 |
| abc | b-- , len = 3 a = 1, b = 1, c = 1 |
| bc | a-- , len = 2 a = 0, b = 1, c = 1 |
| c | b-- ,len = 1 a = 0, b = 0, c = 1 |
由此可見,兩次回圈下去只用O(2N)的時間求出來大量的需要累加的字串
但是ababc中間的子串bab以及以此為基礎的字串都沒有被考慮到,所以此時,只需要在外層新加一層回圈,l=0,r = str.length() ,只要l<r,就回圈,然后l++,r- -,最后就能考慮到所有的情況
代碼:
由于今天剛考完擔心被查重系統誤判,故放下圖片,不放原始碼,同理,不保證代碼正確:
補充一下,我嘗試生成了一個長度為10的4 次方的資料運行代碼,可以1s內出現答案,但是換成10的5次方的資料就不行了,而正常的暴力解法則對于10的3次方就是極限,10的四次方長度的字串則運行不出結果.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/181750.html
標籤：其他
上一篇：2020-10-18周總結