锐客网

  1. 首页 > it技术 > >

2019 GDUT Winter Personal Training Contest III (Div. 2) A题 QAQ 题解

题解

2019 GDUT Winter Personal Training Contest III (Div. 2) A题 QAQ 题解 题目见 ：
http://codeforces.com/group/NVaJtLaLjS/contest/236618/problem/A
题目大意： 给出一串大写字符串s（长度小于等于100），求里面所有"QAQ"的个数（可以不相邻，即“Q…A…Q”）
思路： 观察发现，每个“QAQ”均以一个“A”为核心，那么我们只需要记录每个“A”左右各自的“Q”的数目相乘，再将结果加起来，就可以实现。
一次优化： 【2019 GDUT Winter Personal Training Contest III (Div. 2) A题 QAQ 题解】记录每个“A”左右的“Q”可以使用前缀数组 f[i] 表示从第 0 位到第 i 位总共有多少个“Q”，那么对于当前字符是A的第i位，(f[n-1]-f[i]) 就表示这个字符右边的Q个数，f[i]表示左边Q的个数。
实现：

#include #include #include using namespace std; int main() { int sum=0; int n,i,f[101]; char s[101]; scanf("%s",s); n=strlen(s); //~~~~~~~~~~~~~~~~~~~~~分割线下为处理部分~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ f[0]=(s[0]=='Q'); //把第一个位置特判 for (i=1; i<=n-1; i++) if (s[i]=='Q') f[i]=f[i-1]+1; //预处理前缀函数f else f[i]=f[i-1]; for (i=1; i<=n-1; i++) if (s[i]=='A') sum+=(f[n-1]-f[i])*f[i]; printf("%d\n",sum); return 0; }

    推荐阅读


    上一篇：打印出如下图案（菱形）

    下一篇：# 2019 GDUT Rating Contest #I G. Back and Forth