PAT-A-1093 Count PAT’s (25)

题目

题目链接 计算有多少个PAT 字符串APPAPT包括两个PAT作为子字符串。第一个由第2个,第4个,第6个字符组成,第二个由第3个,第4个,第6个字符组成。

现给出一个字符串,求这个字符串包含的PAT的数量。 ## 输入 每个输入文件包括一个测试用例,在一行中给出不超过105 个字符的字符串,仅包括P、A和T。 ## 输出 对于每个测试用例,在一行中输出字符串中包括的PAT的数量。由于结果可能是一个巨大的数字,只需要输出其对1000000007取模的结果。 # 解题 ## 思路分析 使用乘法原理去做。核心思想是:对于字符串中的每个“A”,计算其前面有多少个“P”,计算其后有多少个“T”。然后将这两个数相乘,然后相加。 1. 首先计算这个字符串有多少个“T”。 2. 从字符串开始,计算遇到多少个个“P”,表示“A”前面的“P”的个数,每遇到一个“T”,就从(1)中的计数值中减1,这个数是“A”之后“T”的个数。 3. 当遇到一个“A”时,将其前面遇到的“P”的个数与其之后“T”的个数相乘,然后累加。结果即为所求。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<string>
#pragma warning(disable:4996)
using namespace std;

string str;
long int res = 0;
int P = 0, A = 0, T = 0; //计数这个字符串中有多少个PAT
void solution()
{
cin >> str;
for (int i = 0; i < str.size(); i++)
{
if (str[i] == 'T') T++;
}
for (int i = 0; i < str.size(); i++)
{
if (str[i] == 'P') P++;
if (str[i] == 'T') T--;
if (str[i] == 'A')res += P*T;
}
cout << res % 1000000007;
}

int main()
{
freopen("1.txt", "r", stdin);
solution();
system("pause");
return 0;
}

测试数据

1
2
3
4
5
6
Sample Input:

APPAPT
Sample Output:

2