Keshawn_lu's Blog

PAT 1040.有几个PAT

字数统计: 327阅读时长: 1 min
2021/02/10 Share

题目简介:

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

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

输入格式:

输入只有一行,包含一个字符串,长度不超过105,只包含 PAT 三种字母。

输出格式:

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

输入样例:

1
APPAPT

输出样例:

1
2

思路:

从前往后遍历,PA的数量为当前A之前P的数量,PAT的数量为当前T之前PA的数量。

最后累加的PAT数量即为结果。

tip:

  • 需要在累加过程中对P,PA,PAT进行取余操作

代码如下:

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>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <iomanip>

using namespace std;


int main()
{
string str;
cin >> str;

int P = 0;
int PA = 0;
int PAT = 0;
for (int i = 0; i < str.size(); i++) {

if (str[i] == 'P')
P++;
else if (str[i] == 'A')
PA = (PA + P) % 1000000007; //累加 这个A之前P的数量
else
PAT = (PA + PAT) % 1000000007; //累加 这个T之前PA的数量
}

cout << PAT;
}
CATALOG
  1. 1. 题目简介:
    1. 1.1. 输入格式:
    2. 1.2. 输出格式:
    3. 1.3. 输入样例:
    4. 1.4. 输出样例:
  2. 2. 思路:
  3. 3. 代码如下: