PTA B1040 有几个PAT

1040 有几个PAT （25 分）
字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位§，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位§，第 4 位(A)，第 6 位(T)。

现给定字符串，问一共可以形成多少个 PAT？

输入格式：
输入只有一行，包含一个字符串，长度不超过10
​5
​​ ，只包含 P、A、T 三种字母。

输出格式：
在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 1000000007 取余数的结果。

输入样例：
APPAPT
输出样例：
2

算法分析：我刚开始一点思路都没有，感谢算法笔记给我思路。大致思想是这样比较快：（虽然我不知道暴力怎么写）
A前面的P的数量乘以A后面T的数量就是一个A能够组成的PAT的数量，这个我还是可以理解的，相信大家也容易理解。那么有几个A，就加几个就ok.
面向题解编程，自己写的代码：（虽然超时，但是自己看了思想自己写还是值得鼓励自己，哈哈哈）

#include<cstdio>
#include<iostream>
using namespace std;
const int N=100100;
string s;
char a[N]={0};
int main()
{
	
	int sum=0;
	cin>>s;
	int lens=s.length();
	int c=1;//c记录一共有多少个A 
	for(int i=0;i<lens;i++)
		if(s[i]=='A') a[c++]=i;//记录出现的A的位置
	//	printf("一共有%d个A\n",c-1); 
	for(int i=1;i<c;i++)
	{
		int p,t;
		p=t=0;
		for(int j=0;j<=a[i];j++)
		{
			if(s[j]=='P') p++;
		}
		for(int j=a[c];j<lens;j++)
		{
			if(s[j]=='T') t++;
		}
		sum=(sum+p*t)%1000000007;
     }
     printf("%d",sum);
}

上面的代码超时了，也有几组数据是错的，我也不知道为什么，(⊙o⊙)…
后来又看了书上的参考代码，发现自己上面的代码速度还是蛮，应该用哈希的思想，在第几个位置就记录这个位置的P的数量，然后倒着扫一遍计算T的数量，然后顺便就累乘和累加。
书上的参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100200;
const int MOD=1000000007;
int nump[N];//记录第i位左边的p的个数
char s[N];
int ans,numt; 
int main()
{
	scanf("%s",s);
	int lens=strlen(s);
	for(int i=0;i<lens;i++)
	{
		if(i>0) {
			nump[i]=nump[i-1];
		}
		if(s[i]=='P') nump[i]++;
	}
	for(int i=lens-1;i>=0;i--)
	{
		if(s[i]=='T') numt++;
		else if(s[i]=='A'){
			ans=(ans+nump[i]*numt)%MOD;
		}
	}
	printf("%d",ans);
	return 0;
}

好滴，这道题就这样，然后书上又说了一道题PAT B1045很类似，那我肯定要去看看，试一下啊。下一篇发自己的题解。