乙级 1040 有几个PAT"/>
【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?
输入格式:
输入只有一行,包含一个字符串,长度不超过105,只包含 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系统(在线判定),则忽略文件读入,否则使用文件作为标准输入
#elsefreopen("1.txt", "r", stdin); //从1.txt输入数据
#endifstring 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;
}
更多推荐
【PTA刷题整理】PAT 乙级 1040 有几个PAT
发布评论