CodeForces 451D Count Good Substrings

CodeForces 451D Count Good Substrings

題意：

一個只包含a和b的字符串 問 它有幾個長度為偶數和長度為奇數的“壓縮回文串” 壓縮的概念是 相鄰的相同字符壓縮成一個字符

思路：

串經過壓縮一定滿足如下形式 ……ababab…… 那麼這樣只要兩端的字符相同則中間一定是回文的 因此對於一個a它作為左端點形成的回文串個數就等於它右邊的a的個數 那麼長度是奇數還是偶數呢 可以這麼判斷 如果a在奇數位置上和它匹配的a也在奇數位置上 那麼形成的回文串就是奇數長度的 要不然就是偶數長度的 b同理 因此得到做法 統計一個字符的右邊和它相同的字符在奇數位置和偶數位置的有幾個 然後通過計算就可以得到結果

代碼：

#include
#include
#include
using namespace std;
typedef __int64 LL;
#define N 100010

char str[N];
int ch[N];
int sum[2][2][N];
int n;
LL ans[2];

int main()
{
    int i,len,wei;
    while(~scanf("%s",str))
    {
        len=strlen(str);
        for(i=0;i=0;i--)
        {
            sum[0][0][i]=sum[0][0][i+1];
            sum[0][1][i]=sum[0][1][i+1];
            sum[1][0][i]=sum[1][0][i+1];
            sum[1][1][i]=sum[1][1][i+1];
            sum[ch[i+1]][(i+1)%2][i]++;
        }
        for(i=0;i