PAT乙级1040-----有几个PAT (25分)(难)

1040 有几个PAT (25分)

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

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

输入格式：

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

输出格式：

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

输入样例：

APPAPT

输出样例：

2







本题所用的规律：P一定在A和T之前，T一定在P和A之后

第一个P记为P1，中间的PAT记为Px,Ax,Tx，最后一个T记为Tn
思路1：暴力法，三重循环，显然时间复杂度为O(n³)，无法满足题设要求
思路2：链表法，找到 P1，然后用数组T_sum记录P1后每个T到P1之间的A的数量，同时将T1 T2......Tn链串联起来，接着从P1开始遍历字符串，遇见P，则计算PAT数量，
          遇见A，则每个T_sum所有元素减1，遇见T，则链首指针后移一位，时间复杂度为O(n²)，依然无法满足
最终思路3：为了减少时间复杂度，尽可能一遍遍历获取尽可能多的信息，因此我从P1开始向Tn方向遍历，将遍历到的当前位置以左P1以右看成可见区，这一段是我们要操作的
从P1开始：
1.遇见Px，则记录Px与P1相比不可见的PAT数量（算式为sum+(A_sum+A_T)*(Total_T-T1) (Total_T为T的总数，T1为可见T的个数))
就是P1与Px之间P1能构成的PAT数量以及P1与Px之间的A和Px与Tn之间的T能构成的PAT数量之和

2.遇见Ax，A_T加1（A_T为P1与T1，T1与T2......T(n-1)与Tn之间A的数量）

3.遇见Tx，则A_sum=A_sum+A_T(A_sum为P1到可见的最远的Tx之间A的个数)，同时将A_T清0，sum=sum+A_sum(sum为P1到可见的最远的Tx之间PAT的个数)


首次通过代码:

 1 #include<stdio.h>
 2 #include<string.h>
 3 //首个P表示为P1
 4 int main(){
 5     char a[100002];
 6     scanf("%s",a);
 7     int len=strlen(a);
 8     int A_sum=0;//P1到Px间A的数量
 9     int Total_T=0;//P1后T的总数
10     int Total_P=0;//P1后P的总数(数组lack_PAT有效的下标总数)
11     int A_T=0;//P1到T1，T1到T2.....间A的个数
12     int T1=0;
13     int P_position=1,T_positon=0;//P1的位置
14     long long sum=0;
15     int lack_PAT[100002]={0};
16     int flag=1;
17     //P1的位置
18     for(int i=0;i<len;i++){
19         if(flag){
20         if(a[i]=='P') {
21          P_position=i;
22          flag=0;
23          }
24         }
25          else{
26            if(a[i]=='T') {
27               Total_T++;
28               T_positon=i;
29            }
30          }    
31     }
32     if(T_positon<P_position) {
33         printf("0");return 0;
34     }
35 
36     for(int i=P_position+1;i<=T_positon;i++){
37        if(a[i]=='P'){
38            lack_PAT[Total_P++]=sum+(A_sum+A_T)*(Total_T-T1);//核心
39        }
40        else if(a[i]=='A'){
41          A_T++;
42        }
43        else {
44           A_sum+=A_T;
45           A_T=0;
46           sum+=A_sum;
47           T1++;
48        }
49     }
50     long long sum1=sum;
51     for(int i=0;i<Total_P;i++){
52         sum1=(sum1+sum-lack_PAT[i])%1000000007;
53     }
54     printf("%lld",sum1);
55     return 0;
56 }

View Code