PTA 1040 有几个PAT

题目描述

思路讲解

分析：要想知道构成多少个PAT，那么遍历字符串后对于每一A，它前面的P的个数和它后面的T的个数的乘积就是能构成的PAT的个数。然后把对于每一个A的结果相加即可～～辣么就简单啦，只需要先遍历字符串数一数有多少个T～～然后每遇到一个T呢～～countt–;每遇到一个P呢，countp++;然后一遇到字母A呢就countt * countp～～把这个结果累加到result中～～最后输出结果就好啦~~对了别忘记要对10000000007取余哦～～

PS：假设神奇的你对每次都遇到的神奇的为什么要对1000000007取模感兴趣，请戳

为什么要对1000000007取模

代码展示

#include 
#include 

using namespace std;


int main() {
    string s;
    cin >> s;
    int count = 0, len = s.length(), countP = 0, countT = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'T') countT++;
    }

    for(int i = 0; i < len; i++){
        if(s[i] == 'P') countP++;
        if(s[i] == 'T') countT--;
        if(s[i] == 'A') count = (count + (countP * countT) % 1000000007) % 1000000007;
    }

    cout << count;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23