题目描述

给定一个由大写字母构成的字符串 s
，请计算其中有多少个子序列 QAQ。

注意，子序列不需要连续。

样例

blablabla

算法1

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

直接暴力枚举 时间复杂度是O(n^3) 100100100 = 1e6;

时间复杂度

参考文献

C++ 代码

int main(){
    cin >> c;
    int l = strlen(c);
    int cnt = 0;
    for(int i = 0;i<=l-3;i++){
        for(int j = i+1;j<=l-2;j++){
            for(int k = j+1;k<=l-1;k++)
                if(c[i] == 'Q' && c[j] == 'A' && c[k] == 'Q') cnt++;
        }
    }
    cout << cnt <<endl;
    return 0;

}

算法2

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

先枚举找出，所有前i个字母中所有Q的数量，和所有A所在的位置，然后利用前缀和思想，
//枚举每一个A的位置，此时这个A前面有q[mark[i] - 1个Q，这个A后面有(q[l] - q[mark[i]-1])
//个Q，相乘累加即是所有的“QAQ”
//时间复杂度计算： 枚举计数O(n) 最后累加计算接近小于O(n) 总复杂度O(n)

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
char c[N];
int q[N],a[N];//分别表示在第 i个字母之前数组中 Q和A的数量 
int mark[N];//记录A所在的位置 
int main(){
    scanf("%s",c);
    int l = strlen(c);
    int idx = 0;
    for(int i = 0;i<l;i++){
        if(c[i] == 'A'){
            mark[idx++] = i+1;
            //a[i+1] = a[i] + 1; 
        }
        //else a[i+1] = a[i];
        if(c[i] == 'Q'){
            q[i+1] = q[i] +1;
        }
        else q[i+1] = q[i]; 
}
    int cnt = 0;
    for(int i = 0;mark[i] != 0;i++){
        cnt += q[mark[i]-1] * (q[l] - q[mark[i]-1]);
    }
    cout << cnt << endl;
    return 0;
}