1003.我要通過(PAT)

題乾如下:

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

      現在需要做的就是考慮哪些形式的字元串是正確的形式。首先看條件1，字元串中僅包含P,A,T三種字元，意味著如果出現其他字元那麼這個字元串肯定不滿足條件。再看條件2，任意XPATX的字元串符合條件，這個好理解，就是PAT的兩端要麼是空字元要麼是數量相等的A。最後比較關鍵的就是條件3，如果aPbTc是正確的，那麼aPbATca也是正確的，這裡很明顯，b字元串無法為空，並且如果a串不等於c串，那麼aPATc不正確(不滿足條件2)。所以我們先假設b串為“A”，a串等於c串，那麼aPATa是正確的，接著aPAAT(aa)也是正確的，繼續往下推導，aPAAT(aa)是正確的，那麼aPAAAT(aaa)是正確的，aPAAAT(aaa)是正確的，那麼aPAAAAT(aaaa)也是正確的......可以總結出形如aP(n個A)T(n個a)形式的字元串是正確的。

      綜上所述，字元串的要求:aP(n個A)T(n個a)，其中a串為空或者A組成的字元串，n是大於等於0的整數。

 1 #include <iostream>
 2 using namespace std;
 3 int juge(char *s);
 4 int main(){
 5     int n,i;
 6     char s[10][105];
 7     cin>>n;
 8     for(i=0;i<n;i++)
 9       cin>>s[i];
10     for(i=0;i<n;i++){
11         if(juge(s[i]))
12           printf("YES\n");
13         else printf("NO\n");
14     }
15     return 0;
16 }
17 int juge(char *s){
18     int i,lena=0,lenb=0,len;
19     for(i=0;;i++){
20         if(s[i]=='A')               //a串中A的數目 
21          lena++;
22         else{
23         if(s[i]=='P')
24          break; 
25         else return 0;
26          }
27     }
28     for(i=i+1;;i++){
29         if(s[i]=='A')               //b串中A的數目 
30           lenb++;
31         else{
32         if(s[i]=='T')
33           break;
34         else return 0;
35         }
36     } 
37     if(lenb==0)  return 0;          //b為空串 
38     len = i +  lena*lenb+1; 
39     for(i=i+1;i<len;i++){           //ac串是否均為字元A 
40         if(s[i]=='A')
41           continue;
42         else return 0;
43     }
44     if(s[len]=='\0') return 1;      //是否到達字元串底部      
45     else return 0;
46 } //AC

題目鏈接：https://www.patest.cn/contests/pat-b-practise/1003