PAT A1093 Count PAT's(C++)

PAT甲级目录 | PAT乙级目录

题目描述

原题地址:A1093 Count PAT’s
中文版:B1040 有几个PAT

解题思路

逻辑题。先遍历字符串,对每一个 ‘A’ ,有效的 ‘PAT’ 个数 $m = left_P * right_T$,即为 ‘A’ 左侧的 ‘P’ 字符数与其右侧的 ‘T’ 字符数的乘积。

每个 ‘A’ 字符左右的 ‘P’ 和 ‘T’ 数量可以通过他们的总数间接求得。一边遍历 ‘A’ 一边可以得到 left_P, right_T = 总的 ‘T’ - left_T。

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>
using namespace std;
int main(){
int left_P = 0, right_T = 0;
long long ans = 0;
string S;
getline(cin, S);
for(int i = 0; i < S.length(); i++) {
if(S[i] == 'T') right_T++;
}
for(int i = 0; i < S.length(); i++){
if(S[i] == 'P') left_P++;
if(S[i] == 'T') right_T--;
if(S[i] == 'A') ans = (ans + left_P * right_T) % 1000000007;
}
cout << ans << endl;
return 0;
}