PAT A1093 Count PAT's(C++)

发表于 | 分类于 | |
字数统计: 213 字 | 阅读时长 ≈ 1 分钟
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;
}