CodeForces 451D Count Good Substrings

本文主要是介绍CodeForces 451D Count Good Substrings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

一个只包含a和b的字符串  问  它有几个长度为偶数和长度为奇数的“压缩回文串”  压缩的概念是  相邻的相同字符压缩成一个字符

思路：

串经过压缩一定满足如下形式 ……ababab……  那么这样只要两端的字符相同则中间一定是回文的  因此对于一个a它作为左端点形成的回文串个数就等于它右边的a的个数  那么长度是奇数还是偶数呢  可以这么判断  如果a在奇数位置上和它匹配的a也在奇数位置上  那么形成的回文串就是奇数长度的  要不然就是偶数长度的  b同理  因此得到做法  统计一个字符的右边和它相同的字符在奇数位置和偶数位置的有几个  然后通过计算就可以得到结果

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 LL;
#define N 100010char 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<len;i++) ch[i]=str[i]-'a';memset(sum,0,sizeof(sum));ans[1]=len;ans[0]=0;for(i=len-2;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<len;i++){wei=i%2;ans[1]+=sum[ch[i]][wei][i];ans[0]+=sum[ch[i]][wei^1][i];}printf("%I64d %I64d\n",ans[0],ans[1]);}return 0;
}

这篇关于CodeForces 451D Count Good Substrings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---