By YiHeng

Updated:

Contents
  1. 1. 输入格式：
  2. 2. 输出格式：
  3. 3. 输入样例：
  4. 4. 输出样例：
  5. 5. 分析：
  6. 6. 代码：

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

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

输入格式：

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

输出格式：

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

输入样例：

APPAPT

输出样例：

2

分析：

本题最关键的是找到每一个A的位置以及数清楚它左边P的数量left和右边T的数量right。对每一个A来说，由它形成的PAT数量为left * right。具体做法是从左向右先找到第一个A，数清楚它左边的P数量left，右边T的数量right，记录下由它行程的PAT数量count，count=left * right。从第一个A移动到字符串最后一位的过程中，遇到P则left减1，遇到A则计算此时的left * right并把结果加到count上，遇到T则right减1。循环完毕，count值即为所求。

代码：

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
#include<iostream>
using namespace std;
int main(){
    long long int count=0,i=0,j=0,pos=0,length=0,left=0,right=0;
    string s;
    cin >> s;
    length = s.size();
    for (i=0;i<length;i++){
        if (s[i] == 'P') left++;
        if (s[i] == 'A'){
            pos = i;
            for (j=i+1;j<length;j++)
                if (s[j] == 'T') right++;
            break;
        }
    }
    for (i=pos;i<length;i++){
        if (s[i] == 'P') left++;
        if (s[i] == 'A') count += left * right;
        if (s[i] == 'T') right--;
    }
    count = count % 1000000007;
    cout << count ;
    return 0;
}
Contents
  1. 1. 输入格式：
  2. 2. 输出格式：
  3. 3. 输入样例：
  4. 4. 输出样例：
  5. 5. 分析：
  6. 6. 代码：