題目描述

1 ≤ n ≤ 100000。

仔細讀題，當(dāng)字符串為“ababc”,具體實現(xiàn)題意為：

子串 f
a 1
ab 2
aba 1
abab 0
ababc 1
b 1
ba 2
bab 1
babc 2
a 1
ab 2
abc 3
b 1
bc 2
c 1

首先可以想到利用暴力解法，雙重循環(huán)枚舉字符串起始于終止位置，之后再對這個子串進行判斷，復(fù)雜度O(n^2)。n最大為1e6。計算機一秒運算1e8-1e9次，題目限制時間復(fù)雜度1s，所以明顯超時，有些數(shù)據(jù)點過不了。
可以觀察列表，觀察每個字符的作用域，即對f的值貢獻1。每個字符的作用域為前一個字符到后一個字符之間。每個字符的作用域即前一個相同字符到該字符的距離乘以該字符到后一個相同字符的距離。樣例中a,b,a,b,c貢獻值分別為2 4 6 4 5。

代碼如下

#include<bits/stdc++.h> using namespace std; int pre[100000+5]; int last[100000+5]; string s; int ans=0; int main() {cin>>s;int mast[30];//記錄最近的一個memset(mast,-1,sizeof mast); //記錄前一個最進的位置for(int i=0;i<s.length();i++){int m=s[i]-'a';//字符對應(yīng)的唯一映射數(shù)值pre[i]=mast[m]; mast[m]=i;//記錄最新的位置，下次相同字符的最近的即為mast[m],下同}for(int i=0;i<=26;i++)mast[i]=s.length(); //記錄該字符后一個最近的位置for(int i=s.length()-1;i>=0;i--){int m=s[i]-'a';last[i]=mast[m];mast[m]=i;}for(int i=0;i<s.length();i++){ans+=((i-pre[i])*(last[i]-i));}cout<<ans<<endl;return 0; }

算法參考
https://blog.csdn.net/qq_56173569/article/details/114907825

總結(jié)

以上是生活随笔為你收集整理的【蓝桥杯】子串分值---笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。