1003. 我要通过！(20)

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于PAT的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。

得到“答案正确”的条件是：

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

现在就请你为PAT写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式： 每个测试输入包含1个测试用例。第1行给出一个自然数n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过100，且不包含空格。

输出格式：每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出YES，否则输出NO。

输入样例：

8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA

输出样例：

YES
YES
YES
YES
NO
NO
NO
NO

思路：
一开始半个多小时都无从下手，最后看了题解才明白是一个数学归纳法的简单模拟题，而我想到kmp变形去了。。。

其实读题的时候，看到第三个条件，. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的。。中间增加一个A而右边却增加了一个a，增长呈现线性关系，P和T之间的A的总数增了一个，而T右边却增加了a，我们得以得出数学关系式

a中A的个数*（b中A的个数+1） = c中A的个数+a中A的个数

至此就可以编码了
哦，还有一点细节
*PT中间必须要有A

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 bool selectStr(char str[],int length)
 8 {
 9 
10     for(int i=0; i<length; i++)
11     {
12         if(str[i]!='A' && str[i]!='P' && str[i]!='T')
13             return false;
14         else 
15             return true;
16     }
17 }
18 int main()
19 
20 {
21     int n;
22     char str[101];
23     scanf("%d",&n);
24     while(n--)
25     {
26         memset(str,0,101);
27         scanf("%s",str);
28         int length = strlen(str);
29         if(selectStr(str,length))
30         {
31             int lena = 0;
32             int lenb = 0;
33             int lenc = 0;
34             for(int i=0;i<length;i++)
35             {
36                 if(str[i]!='P')
37                     lena++;
38                 else 
39                     break;
40             }
41             for(int i=0,cnt=0;i<length;i++)
42             {
43                 if(str[i]!='T')
44                     cnt++;
45                 else 
46                 {
47                     lenb = cnt-lena-1;
48                     lenc = length-cnt-1;
49                         break;
50                 }
51             
52             }
53             if(lenb == 0)
54                 printf("NO
"); 
55             else
56             { 
57             
58             if(lena*lenb == lenc)
59             {
60                 printf("YES
");
61             }
62             else
63             {
64                 printf("NO
");
65             }
66             } 
67             //test
68             
69         }
70         else
71         {
72             printf("NO
");
73         }
74         
75     }
76     
77     return 0;
78 }