C(clang 3.9) 解法, 执行用时: 4ms, 内存消耗: 1252K, 提交时间: 2019-04-21 21:06:54

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
char a[1000005];
int main()
{
	int t,d;
	scanf("%d",&t);
	getchar();
	memset(a,0,sizeof(a));
	d=t;
	while(t--)
	{	
		if(d==t-1)
		getchar();
		gets(a);
		long long len=strlen(a),i,b,c,j,k;
		long long int sum=0;
		for(i=0;i<len;i++)
		{
			if(a[i]=='A')
			{
				b=0;
				for(j=0;j<i;j++)
				{
					if(a[j]=='Q')
					b++;
				}
				c=0;
				for(k=i+1;k<len;k++)
				{
					if(a[k]=='Q')
					c++;
				}
				sum+=(b*c);
			}
		}
		printf("%lld\n",sum);
	}
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 55ms, 内存消耗: 10180K, 提交时间: 2020-03-18 12:47:24

#include<bits/stdc++.h>
using namespace std;
long long int b[1000005];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		string s;
		cin>>s;
		int sum=0;
		int k=0;
		memset(b,0,sizeof(b));
		for(int i=0;i<s.length();i++)
		{
			if('Q'==s[i])
			sum++;
			else if('A'==s[i])
			b[++k]=sum;
		}
		long long ans=0;
		for(int i=1;i<=k;i++)
		{
			ans+=b[i]*(sum-b[i]);
		}
		printf("%lld\n",ans);
	}
}