題目原文

題目描述

咕咕東很聰明，但他最近不幸被來自宇宙的宇宙射線擊中，遭到了降智打擊，他的英語水平被歸零了！這一切的始作俑者宇宙狗卻毫不知情！
此時(shí)咕咕東碰到了一個(gè)好心人——TT，TT在吸貓之余教咕咕東學(xué)英語。今天TT打算教咕咕東字母A和字母B，TT給了咕咕東一個(gè)只有大寫A、B組成的序列，讓咕咕東分辨這些字母。
但是咕咕東的其他學(xué)科水平都還在，敏銳的咕咕東想出一個(gè)問題考考TT：咕咕東問TT這個(gè)字符串有多少個(gè)子串是Delicious的。
TT雖然會(huì)做這個(gè)問題，但是他吸完貓發(fā)現(xiàn)輝夜大小姐更新了，不想回答這個(gè)問題，并拋給了你，你能幫他解決這個(gè)問題嗎？
Delicious定義：對(duì)于一個(gè)字符串，我們認(rèn)為它是Delicious的當(dāng)且僅當(dāng)它的每一個(gè)字符都屬于一個(gè)大于1的回文子串中。

輸入描述

輸入第一行一個(gè)正整數(shù)n，表示字符串長度
接下來一行，一個(gè)長度為n只由大寫字母A、B構(gòu)成的字符串。

輸出描述

輸出僅一行，表示符合題目要求的子串的個(gè)數(shù)。

樣例輸入

5
AABBB

樣例輸出

6

樣例解釋

對(duì)于該樣例，符合條件的六個(gè)子串分別是：
s1-s2,s1-s4,s1-s5,s3-s5,s4-s5

數(shù)據(jù)組成

解題思路

直接找Delicious子串比較麻煩，所以查找所有非Delicious子串，用總子串?dāng)?shù)減去求取結(jié)果。
由于測(cè)試的數(shù)據(jù)數(shù)量很多，所以無法檢測(cè)完所有的子串，需要找規(guī)律找出非Delicious子串；
只有單獨(dú)一個(gè)字母開頭或結(jié)尾的子串才是非Delicious子串，所以我們把整個(gè)字符串分段，每段是所有連續(xù)的同一個(gè)字符，可以通過總段數(shù)得到最終答案。

實(shí)現(xiàn)代碼

#include<iostream>
using namespace std;

const int maxn=3*1e5;
long long sum[maxn];
int main() {
    long long n;
    cin>>n;
    string s;
    cin>>s;
    int cnt=1;
    sum[1]=1;
    for(int i=1;i<n;i++){
        if(s[i]!=s[i-1]){
            cnt++;
        }
        sum[cnt]++;
    } 
    long long ans=n*(n-1)/2;
    if(cnt==1){
        cout<<ans<<endl;
    }
    else{
        ans=n*(n-1)/2;
    //  cout<<sum[1]<<"||"<<sum[2]<<endl;
         
        long long ans0=sum[1]+sum[cnt];
        for(int j=2;j<cnt;j++)
        {
            ans0+=2*sum[j];
        }
        
        ans=ans-ans0+(cnt-1);
        cout<<ans<<endl;
    }


    return 0;
}

小結(jié)

遇到難以直接求取的值，可以先求取總數(shù)減去對(duì)立條件下的值。對(duì)立條件即當(dāng)前A或B及其后邊連續(xù)的另一字符，如ABBBB、AAABB...