codeforces--1238 D. AB-string

题目链接：https://codeforces.com/problemset/problem/1238/D

大致题意：

给你一个数n，然后给你一个长度为n的字符串，这个字符串是只有A，B两个字母，问你这个字符串的子串（当然本身也是自己的子串）中有多少个回文串（单个字符不算回文串）。

思路：

本来我是往dp方向想的，考虑他的子串要想构成回文串，那么最小的回文串就只有这四中情况

• 1 AA
• 2 BB
• 3 ABA
• 4 BAB
  但是我发现这种方法还是有很多情况没有考虑到，比如：AABB有三个回文子串，AABBB有6个回文子串。发现情况还是很复杂。
  看了一下大佬们的题解博客，发现很多大佬都是用反方向来做的，就是先找到假设长度为n的字符串的子串全部符合，然后找到不符合条件的字符串子串，一减就剩下全部符合的字符串子串的数量了。
  那么不符合子串怎么求呢？
  你仔细找找就会发现，不符合回文子串的情况就只有四种（当然这只是字符串中只含有两个字符的情况，要是多个字符，那情况可多了去了。。。）
• 1.ABBBB…BBB
• 2.BAAAA…AAA
• 3.BBBBB…BBA
• 4.AAAAA…AAB
  就只有这四种情况，那么把这四种情况的数量弄清答案就出来了。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char s[300005];
int main()
{
    long long  n;
    scanf("%lld",&n);
    scanf("%s",s);
    long long ans=0;
    long long sum;
    sum=((n-1)*n)/2;
    int flog=0;
    for(int i=1;i<n;i++)
    {
        if(s[i]!=s[i-1])
        {
            if(flog==0)
            {
                ans++;
                flog=1;
            }
            else
            {
                ans++;
            }
        }
        else if(flog==1&&s[i]==s[i-1])
        {
            ans++;
        }
    }
    flog=0;
    for(int i=n-2;i>=0;i--)
    {
        if(s[i]!=s[i+1])
        {
            if(flog==0)
            {
                flog=1;
            }
        }
        else if(flog==1&&s[i]==s[i+1])
        {
            ans++;
        }
    }

    printf("%lld\n",sum-ans);
    return 0;
}