【PTA刷题整理】PAT 乙级 1040 有几个PAT

2020.07.08

1040 有几个PAT (25分)

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

这个题的关键是以组合为单位进行计数，这里我采用的是从后往前遍历，如果是T，则进行计数，如果遇到A，则和之前的T组合为AT，AT的数量等于这个A和后面的所有T的结合的数量，所以加上T的数量。同理，遇到P，则是PAT组合，PAT的数量等于这个P和后面所有的AT组合结合的数量。最后使用PAT的数量取模取余数结果即可
这题也可以不用字符串，逐位进行匹配，从头从尾开始都可以，可以减少代码量

#include<iostream>                  //输入输出流头文件
#include<stdio.h>                   //标准输入输出
#include<stdlib.h>
#include<math.h>                    //数学函数
#include<string.h>                  //C语言字符数组的字符串
#include<algorithm>                 //C++标准模板库的函数
#include<map>                       //map映射容器
#include<unordered_map>             //无序的map映射容器
#include<vector>                    //变长数组容器
#include<queue>                     //队列
#include<stack>                     //栈
#include<string>                    //C++string类
#include<set>                       //set集合
using namespace std;                //标准命名空间

                                    //可以加入全局变量或者其他函数

int main(){                         //主函数
#ifdef ONLINE_JUDGE                 //如果有oj系统（在线判定），则忽略文件读入，否则使用文件作为标准输入
#else
    freopen("1.txt", "r", stdin);   //从1.txt输入数据
#endif
	string str;
	long t=0, at=0, pat=0;
	cin >> str;
	int length = str.length();
	for(int i = length - 1 ; i >= 0 ; i--){
		if(str[i] == 'T'){
			t++;
		}else{
			if(str[i] == 'A'){
				at += t;
			}else{
				if(str[i] =='P'){
					pat += at;
				}
			}
		}
	}
	cout << pat % 1000000007 << endl;
    return 0;                       
}