首页 > 代码库 > codeforces 451D Count Good Substrings

codeforces 451D Count Good Substrings

2024-07-15 11:50:09   213人阅读

题意：给定一个字符串，求有多少个奇数子串和多少偶数子串为 “回文串”   这边回文串很特殊之含有  ab  两种字母  而且  相邻的字母相同则消去一个  一直到不存在相邻的相同。

思路：  在这种串中 ，消到最后 一定是   abababababa。。。   或者 bababababab。。。  那么 只要头尾一样 那么这个串 一定是 回文串。

那么 只需要 统计下 奇数位上 和 偶数位上a  b个数就能直接计算。  一个在奇数位一个在偶数为  长度位偶数，  两个都在  奇数位 或者偶数位 则长度为奇数。

 

#include <iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<cmath>#define LL long long#define f(x) ((x)*(x+1)/2)using namespace std;char s[100050];int main() {    LL odda,oddb,evena,evenb;    odda=oddb=evena=evenb=0;    scanf(" %s",s);    int len=strlen(s);    for(int i=0;i<len;++i)    {        if(s[i]==‘a‘)        {            if(i&1)                odda++;            else                evena++;        }        else        {            if(i&1)                oddb++;            else                evenb++;        }    }    LL ans1=odda*evena+oddb*evenb;    LL ans2=f(odda)+f(oddb)+f(evena)+f(evenb);    printf("%I64d %I64d\n",ans1,ans2);    return 0;}

 


联系
我们