题解 | #abb#

解题思路：

• 形式为“abb”，可以用$d{p}_{i}dp\_i$来表示第i个字母构成的最大个数，那么$d{p}_i=d{p}_{i-1}+count(cha{r}_{0,i-1}andcha{r}_i)(\mathrm{第}i\mathrm{个}\mathrm{字}\mathrm{符}\mathrm{和}\mathrm{其}\mathrm{前}\mathrm{面}\mathrm{字}\mathrm{符}\mathrm{构}\mathrm{成}\mathrm{的}\mathrm{“}abb\mathrm{”}\mathrm{样}\mathrm{式}\mathrm{的}\mathrm{个}\mathrm{数}\mathrm{）}dp\_i\backslash \; =\backslash \; dp\_\{i-1\}\backslash \; +\backslash \; count(char\_\{0,i-1\}\backslash \; and\backslash \; char\_i)(第i个字符和其前面字符构成的“abb”样式的个数）$。按照题目输入的规模为1E5，如果直接按照次计算去做那么时间复杂度是$O(n^2)O(n^2)$,会TLE，再次分析问题，其实我们只要记录上一次向同字母所产生的个数，然后继续累加从前一个以后开始的前缀部分已备下一个字母遇到进行计算。
• 如：在“abcbcbcbc”中，以c字母为例，第一个c之前的部分“ab”，继续往后记录非c字母，在遇到第二个c的时候使用掉第一部分的前缀，此时前缀应该更新为“ababb”，当遇到第三个字母c的时候前缀应计算为“ababb”，然后再继续更新为“ababbababbb”即，前一次计算出来的前缀会在下一次遇到相同字母继续使用。把这部分做记录而不需要每次从新计算是解题的关键。
• 上述计算应该对26个字母每一个字母进行计算统计。所以在每读入一个字母，对于非相同字母所有字母的前缀应该+1，对于遇到相同字母则进行个数计算。

#include<bits/stdc++.h>
using namespace std;
// long long solve_TLE(string &s, int n){//TLE代码,差别在于每一次都从0开始计算当前字母的前缀。
//     int i;
//     int dp = 0;
//     for(i = 2; i < n; ++i){
//         int sum = 0;
//       	int tmp = 0;
//         for(int j = 0; j < i; ++j){
//             if (s[j] != s[i]) sum++;
//             else{
//                 tmp += sum;
//             }
//         }
//         dp += tmp;
//     }
     
//     return dp[n-1];
    
// }
long long solve(string &s,int n){
    vector<vector<int>> prif_sum(26, vector<int>(2,0));//定义一个前缀和数组，[0]维表示当前要计算的前缀，[1]维表示下一次要计算的前缀
    long long dp = 0;
    for(int i = 0; i < n; ++i){
        int pos = s[i] -'a';//对于输入进来的每一个字母，相应字母做计算，不同字母做前缀累加。
        for(int j = 0; j < 26; ++j){
            if(j == pos){
                dp += prif_sum[j][0];//如果遇到相同字母则使用掉上一次前缀并且加上从第一个字母统计到当前位置的前缀已备下一次使用。
                prif_sum[j][0] += prif_sum[j][1];
            }
            else prif_sum[j][1]++;//对于每一个非相同字母都应该前缀加1.
        }
    }
    return dp;

}
int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    cout<<solve(s, n)<<endl;
    return 0;
}