首页 > 代码库 > 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 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<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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。