题目描述

给定一个由大写字母构成的字符串 s，请计算其中有多少个子序列 QAQ。
注意，子序列不需要连续。
提示：本题数据范围较小，可以直接三重循环枚举三个字母的位置。
输入格式
一行，一个由大写字母构成的字符串 s。
输出格式
一个整数，表示 s 中子序列 QAQ 的个数。
数据范围
所有测试点满足 1≤|s|≤100。

样例

输入
QAQAQYSYIOIWIN
输出
4

(暴力枚举) $O(n^2)$

一个一个扫过来

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string a;
int s;
int main()
{
    cin >> a;
    for(int i=0;i<a.size();i++){
        for (int j = i+1; j < a.size(); j ++ ){
            for(int k=j+1;k<a.size();k++){
                if(a[i]=='Q'&&a[j]=='A'&&a[k]=='Q')s++;
            }
        }
    }
    cout<<s;
}