PAT乙级1040 || 有几个PAT（详解，C/C++示例，测试点分析）

Posted on In

有几个PAT

题目描述

字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位(P)，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位(P)，第 4 位(A)，第 6 位(T)。

现给定字符串，问一共可以形成多少个 PAT？

输入格式

输入只有一行，包含一个字符串，长度不超过$10^5$，只包含 P、A、T 三种字母。

输出格式

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

输入样例

1
APPAPT

输出样例

1
2

问题解决

解题思想

此题可按从前往后遍历或者从后往前遍历分下面两种解法：
方法一：从前往后遍历（代码1）
从前往后遍历整个字符串，遇到字符P就统计其个数，遇到字符A就统计其之前所有的P的个数，遇到字符T就统计其之前所有的PA的个数，每次循环统计后判断总PAT的数量是否超过1000000007个，若超过则取对1000000007的余数，这样就不必将coun定义为long long型。
方法二：从后往前遍历（代码2）
从后往遍历整个字符串，遇到字符T就统计其个数，遇到字符A就统计其之后所有的T的个数，遇到字符P就统计其之后所有的AT的个数。可见此法与方法一思想是一样的。

代码示例（C/C++）

代码1

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
//代码1，从前往后遍历
#include <cstdio>
using namespace std;
const int maxn = 100001;
int main()
{
    char str[maxn];
    scanf("%s",str);
    int coun = 0,coun_p = 0,coun_ap = 0;
    for(int i = 0; str[i] != '\0'; i++){
        switch(str[i])
        {
        case 'P':
            coun_p++;break; //A前面P的个数
        case 'A':
            coun_ap += coun_p;break;    //T前面所有的PA的个数
        default:    //T
            coun +=coun_ap; //该T对应的PAT的个数
        }
        if(coun > 1000000007){
            coun %= 1000000007;
        }
    }
    printf("%d",coun);
    return 0;
}

代码2

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
//代码2，从后往前遍历
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100001;
int main()
{
    char str[maxn];
    scanf("%s",str);
    int coun = 0,coun_T = 0,coun_AT = 0;
    int len = strlen(str);
    for(int i = len - 1; i >= 0; i--){
        switch(str[i])
        {
        case 'T':
            coun_T++;break; //A后面T的个数
        case 'A':
            coun_AT += coun_T;break;    //P后面所有的AT的个数
        default:    //P
            coun +=coun_AT; //该P对应的PAT的个数
        }
        if(coun > 1000000007){
            coun %= 1000000007;
        }
    }
    printf("%d",coun);
    return 0;
}

题目来源：PAT乙级1040
作者：CHEN, Yue
单位：浙江大学

稀罕作者