PTA 有几个ZUCC

大家好，欢迎来到IT知识分享网。

字符串 AAZBCZCUCIOCQWC 共包含6个 ZUCC。

例如，第3位(Z)，第8位(U)，第9位(C)，第12位(C)可以形成一个ZUCC;

第6位(Z)，第8位(U)，第12位(C)，第15位(C)也可以形成一个 ZUCC。

下面给定一个长度不超过 105 且仅包含大写 A-Z 字母的字符串。一共可以形成多少个 ZUCC？

输入格式:

输入只有一行，包含一个长度不超过 105 的字符串。

输出格式:

输出该字符串中包含的 ZUCC 个数。题目保证总数不超过 263−1。

输入样例:

AAZBCZCUCIOCQWC

输出样例:

6

代码实现：

#include<stdio.h> #include<string.h> char str[]; long long U[]={0}; int C[]={0}; void CountC(int l) {//计算每一个C字符后面有多少个C字符 int cnt=0; for(int i=l-1;i>=0;i--) { if(str[i]=='C') { C[i]=cnt++; } } //计算以i位开始考虑后面可以形成多少个后缀CC int pos=l; for(int i=l-1;i>=0;i--) { if(str[i]=='C') { C[i]+=C[pos]; pos=i; } } return; } void CountU(int l) { int pos=0; for(int i=0;i<l;i++) { if(str[i]=='U') { if(i<pos) { U[i]=C[pos]; } else { for(int j=i;j<l;j++) { if(str[j]=='C') { pos=j; U[i]=C[pos]; break; } } } } } //计算从i位开始有多少个UCC pos=l; for(int i=l-1;i>=0;i--) { if(str[i]=='U') { U[i]+=U[pos]; pos=i; } } return; } int main() { scanf("%s",&str); long long cnt=0; //注意使用合适的数据类型 int l=strlen(str); CountC(l); CountU(l); int pos=0; for(int i=0;i<l-3;i++) { if(str[i]=='Z') { if(i<pos)cnt+=U[pos]; else { for(int j=i+1;j<l;j++) { if(str[j]=='U') { cnt+=U[j]; pos=j; break; } } } } } printf("%ld\n",cnt); return 0; }