【PAT-B】1030 有几个PAT（C++）

2024-03-09 21:18

文章标签 c++ 几个 pat 1030

本文主要是介绍【PAT-B】1030 有几个PAT（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

题目描述
字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。
现给定字符串，问一共可以形成多少个PAT？

输入描述:
输入只有一行，包含一个字符串，长度不超过105，只包含P、A、T三种字母。

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

输入例子:
APPAPT

输出例子:
2

解题思路

1. 类似于K序列求和问题。首先化简单点，看可以组成多少个PA，首先遍历一遍字符串，那么一个字母A前面P有多少个便可以组成多少个PA，抱着这个思想，遇到A则加上一次这个字母前P的个数，遍历完字符串之后，之前统计A的结果不就是可以组成多少个PA的结果么。在以这个想法去统计AT，也就会自然而然地得出PAT的结果。

代码设计

【任务】
统计给定字符串中可以组成PAT的个数
【说明】
字符串中，一个A能组成多少个PA由字母A前的P的个数决定，一个T能组成多少个AT由字母T前的A的个数决定，抱着这个思想，这题便很简单了。
【接口】
inline int fun(string ss)
输入：ss 题目给的字符串
输出：可以组成PAT的个数

//主要算法
//zhicheng
const int maxn=1000000007;
inline int fun(string ss)
{int p=0,a=0,t=0;for(int i=0;i<ss.length();i++){if(ss[i]=='P') p=(p+1)%maxn;if(p&&ss[i]=='A')a=(a+p)%maxn;if(a&&ss[i]=='T')t=(t+a)%maxn;}return t%maxn;
}