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