A 辞树的QAQ水题

题目描述
蒟蒻的辞树又被吊打了嘤嘤嘤。留下了属于弱者的眼泪QAQAQAQAQAAQAAQA······ 现在我
们定义辞树的悲伤值 F 。F的值为主串中子序列为”QAQ”的个数。注意字母“QAQ”不一定是
连续的，但是字母的顺序应该是准确的。
输入
输入一个整数T（0 ≤ T ≤ 20）,代表有T组数据。每组数据会给出一个字符串S,长度为len，0 <
len ≤ 1000000
输出
根据每组的字符串，输出辞树的悲伤值F，每组数据换行。
输入样例
2
QAQAQYSYIOIWIN
QAQQ
输出样例
4
2

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAX = 1e6+10;
const int INF = 0x3fffffff;
char s[MAX];
int a[MAX];
int b[MAX];
struct node{
    int left;
    int right;
}p[MAX];
int main(){
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int t;
    scanf("%d",&t);
    while(t--){
        memset(s,0,sizeof(s));
        scanf("%s",s);
        getchar();
        int n = strlen(s);
        int num=0;
        int ans=0;
        for(int i=0;i<n;i++){
            if(s[i]=='Q')   num++;
            a[i]=num;
            if(s[i]=='A')   p[ans++].left=a[i];
        }
        int temp = ans;
        num=0;
        for(int i=n-1;i>=0;i--){
            if(s[i]=='Q')   num++;
            b[n-i-1]=num;
            if(s[i]=='A')   p[--temp].right=b[n-i-1];
        }
        LL final=0;
        for(int i=0;i<ans;i++)
            final += p[i].left*p[i].right;
        printf("%lldn",final);
    }
    return 0;
}

最后

以上就是魁梧往事最近收集整理的关于A 辞树的QAQ水题的全部内容，更多相关A内容请搜索靠谱客的其他文章。