PAT乙級 1003. 我要通過！

題目：

“答案正確”是自動判題系統給出的最令人歡喜的回復。本題屬于PAT的“答案正確”大派送 —— 只要讀入的字符串滿足下列條件，系統就輸出“答案正確”，否則輸出“答案錯誤”。

得到“答案正確”的條件是：

1. 字符串中必須僅有P, A, T這三種字符，不可以包含其它字符； 2. 任意形如 xPATx 的字符串都可以獲得“答案正確”，其中 x 或者是空字符串，或者是僅由字母 A 組成的字符串； 3. 如果 aPbTc 是正確的，那么 aPbATca 也是正確的，其中 a, b, c 均或者是空字符串，或者是僅由字母 A 組成的字符串。

現在就請你為PAT寫一個自動裁判程序，判定哪些字符串是可以獲得“答案正確”的。

思路：

???? 首先第三個條件上來有個“如果”，這個明顯是告訴有前提的，排除第一個條件后我們可以基本確定是通過第二個條件來推定，好了我們根據正則表達式的特點，知道基本是#PAT#的模型，所以就有PAT三個字母，因為題目要求每個測試輸入包含1個測試用例，所以我們假設就是PAT作為正確的表達式，有第三個條件”aPbTc?“正確，所以a和c都是null,b是A,同時”aPbATca”也是正確的，所以我們肯定”PAAT”也是正確的，我們把其再看成”aPbTc”型，就有”PAAAT”也是正確的；再來我們假定”APATA”正確，所以根據”aPbTc?“，可以推的”APAATAA”正確，繼續還有”APAAATAAA”等正確；可以看出?P前A的個數乘?P?T中間的A的個數?等于T后A的個數。

　　對于第1個規則：0*0=0。對于第2個規則：x*1=x。對于第3個規則：aPbTc如果正確，那么b一定是A、a=c,bA就是AA,a*2=aa=ca。

代碼：

　　　　

#include<stdio.h>
#include<string.h>
int main()
{char str[105]; int n,i;scanf("%d",&n);for(i=0;i<n;i++){int a=0,b=0,c=0; //分別表示aPbTc中abc的長度 int flag=0;  //判斷是否有其他字符 int j,flag1=0,flag2=0; //表示是否經過P,T scanf("%s",str);for(j=0;j<strlen(str);j++){if(str[j]=='A'||str[j]=='P'||str[j]=='T') {if(str[j]=='P') flag1=1;else if(str[j]=='T') flag2=1;else{if(flag1!=1) a++;if(flag1==1&&flag2!=1) b++;if(flag2==1) c++;}}else{flag=1;break;}}if(a*b==c&&flag==0&&b!=0) printf("YES\n");else printf("NO\n");}return 0;
}

?

?

?

??

?