Count PAT's (25) PAT甲级真题

题目分析：

由于本题字符串长度有10^5所以直接暴力是不可取的，猜测最后的算法应该是先预处理一下再走一层循环就能得到答案，所以本题的关键就在于这个预处理的过程，由于本题字符串匹配的内容的固定的PAT，所以我们可以这样想，对于一个输入的串，我们找到每个A的位置，只要知道这个A的前面有几个P，这个A的后面有几个T，就可以得到以这个A为中心的所有种数，二者相乘即可，然后如果我们能得到0~s.size()-1范围内每个A的前面有多少个P，每个A后面有多少个T，只要从头遍历一遍并且求和就能得到最终答案，由于结果可能很大需要MOD

本题代码：

 1 #include<iostream>

 2 #include<string>

 3 #include<string.h>

 4 #include<stdio.h>

 5 using namespace std;

 6

 7 const int N = 100005;

 8 const int M = 1000000007;

 9 int p[N];

10 int t[N];

11

12 int main(){

13     string s;

14     cin>>s;

15     memset(t, 0, sizeof(t));

16     memset(p, 0, sizeof(p));

17     int len = s.size();

18     for(int i = 1; i < len; i++){

19         if(s[i-1] == 'P') p[i] = p[i-1]+1;

20         else p[i] = p[i-1];

21     }

22     for(int i = len-2; i >= 0; i--){

23         if(s[i+1] == 'T') t[i] = t[i+1]+1;

24         else t[i] = t[i+1];

25     }

26     int ans = 0;

27     for(int i = 0; i < len; i++){

28         if(s[i] == 'A'){

29             int temp = p[i]*t[i]%M;

30             ans += temp;

31             ans %= M;

32         }

33     }

34     printf("%d\n", ans);

35     return 0;

36 }

巴特西

Count PAT's (25) PAT甲级真题

最新文章

热门文章