首页 > 代码库 > Codeforces Round #258 D Count Good Substrings --计数

Codeforces Round #258 D Count Good Substrings --计数

2024-07-14 03:33:05   225人阅读

题意：由a和b构成的字符串，如果压缩后变成回文串就是Good字符串。问一个字符串有几个长度为偶数和奇数的Good字串。

分析：可知，因为只有a,b两个字母，所以压缩后肯定为..ababab..这种形式，所以是good substrings，那么首尾字符肯定相同，于是就好搞了。

用：odd[0],odd[1]分别记录奇数位置上出现的a和b的个数，even[0],even[1]分别记录偶数位置上的a,b个数。

那么到一个奇数点时，奇数长度的子串个数应该加上奇数位置的该字符的个数，偶数长度的应该加上偶数位置的该字符的个数，即两字符相等并且隔奇数个字符时，长度为奇数。 到一个偶数点时，就相反了，奇数长度子串应加上偶数位置该字符个数。偶数长度子串数加上奇数位置该字符数。

注意：

1.单个字符算奇数长度，要加起来。

2.要用long long 或 __int64类型

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define lll __int64#define ll long longusing namespace std;#define N 100007char ss[N];int main(){    int i;    lll Odd,Even;    lll odd[2],even[2];    while(scanf("%s",ss)!=EOF)    {        int len = strlen(ss);        odd[0] = odd[1] = even[0] = even[1] = 0;        Odd = Even = 0;        for(i=0;i<len;i++)        {            Odd++;   //单个字符            int ind = ss[i]-‘a‘;            if(i%2)  //奇数位置            {                Odd += odd[ind];                Even += even[ind];                odd[ind]++;            }            else    //偶数位置            {                Odd += even[ind];                Even += odd[ind];                even[ind]++;            }        }        printf("%I64d %I64d\n",Even,Odd);    }    return 0;}
View Code

 


联系
我们