1003 我要通过！(20)（20 分）

题目：https://pintia.cn/problem-sets/994805260223102976/problems/994805323154440192

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

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

1. 字符串中必须仅有P, A, T这三种字符，不可以包含其它字符；\

1. 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；\
2. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a, b, c 均或者是空字符串，或者是仅由字母 A 组成的字符串。

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

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

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

输入样例：

8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA

输出样例：

YES
YES
YES
YES
NO
NO
NO
NO

#include<iostream>
#include<cstring>
using namespace std;
int main(){
	int i,j,num,sum=0;
	int len=0;
	int a1=0,p=0,t=0,a2=0,a3=0;//a1、p、a2、t、a3分别用来存：P之前的A，P，P和T之间的A，T，T之后的A  的数量
        char str[10][150];         //把输入的每个字符串存入数组
        char arr[10];              //来做标记用的，判断字符串是否正确，以便最后输出
	cin>>num;
	for(i=0;i<num;i++){
		cin>>str[i];
	}
	
	for(i=0;i<num;i++){
		len=strlen(str[i]);
		a1=a2=a3=p=t=0;   //每次记得要把变量清零，方便下一个字符串的计数
		for(j=0;j<len;){
			while(str[i][j]=='A'){//是在while循环里面j++，而不是把j++放在for()里面或者str[i][j++]
				 a1++;
				 j++;
			}
			while(str[i][j]=='P'){
				 p++;
				 j++;
			}			  
			while(str[i][j]=='A'){
				 a2++;
			     j++;
			}			    
			while(str[i][j]=='T'){
				 t++;
				 j++;
			}			
			while(str[i][j]=='A'){
				 a3++;
				 j++;
			}
			sum=a1+p+a2+t+a3;   //用来判断是否含有其他字符
			if(sum!=len){       //含有其他字符就记为'0',此条字符串判断完毕，退出本次循环
				arr[i]='0';
				break;
			}
			else if(p==1&&t==1&&a1==a3&&a2>=1){      //重点：见下详解
				arr[i]='1';
				break;
			} 			  
			else if(p==1&&t==1&&a2!=0&&(a1*a2)==a3){  //重点：见下详解
				arr[i]='1';
				break;
			}
			arr[i]='0';        //不满足条件的标记为'0'
		}
	}
	for(i=0;i<num;i++)
	  if(arr[i]=='1')
	     printf("YES\n");
	  else
	     printf("NO\n"); 
	return 0;	
} 

这个题目真的是让我很心累啊，其实自己做了半天，但是一直有两个通不过。后来自己看了下别人的思路，才通过。

其实这个题目就是需要你发现其中关键的数学规律：

  1:当P之前和T之后都为空字符串时，PAT成为条件3中的那个正确的串，循环往复，那么P和T之间就可以有任意多的A

  2:当P之前和T之后都有数量相等的A时，当它成为条件3中的那个正确的串，可以发现，每次P和T之间增加一个A，T之后的A的数量会增加一倍 最初P之前A的数量，即：

      a1 P a2 T a3

      a1*a2=a3  且  a2!=0

我自己就是这个规律没有找好，所以通过的测试点也不全。