题目描述

1003 我要通过！ (20 分)

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

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

输入格式

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

输出格式

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

输入样例

10
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
APATTAA

输出样例

YES
YES
YES
YES
NO
NO
NO
NO
NO
NO

思路

条件1：只能包含 ‘P’ ‘A’ ‘T’ 三种字符

通过一个循环，遍历字符串的每一位，如果该位字符不是 “PAT” 中的任意一个，则应该输出 NO

bool check(string s){for(int i=0;i<s.length();i++){if(s[i]!='P'&&s[i]!='A'&&s[i]!='T')return false;}
}

条件2： xPATx 可以判定为正确

其中x为空字符串""

例如：PAT

x也可以是 仅由字符 ‘A’ 组成的字符串

例如：
APAT
AAPATAA
AAAPATAAA
A…APATA…A

总结：PAT两边可以有任意相同个数的 ‘A’

条件3：如果 aPbTc 是正确的，那么 aPbATca 也是正确的

这里对 abc 的要求与 条件2 对 x 的要求一致
我们很容易知道 正确答案的最短字符串是：PAT

我们可以发现，其实两个判断是等价的
1.aPbTc
2.aPbATca
只要将第二个的ca看做是c’ ，b+1看作是b’ , 这两个条件是可以互相转化的

当我们逆向的观察变化，b 每增加 1，c 就增加 a（这里的增加指增加"A"的个数）
我们还可以观察到：

1.a始终都没有发生变化，a的取值由初始值决定
2.b每次只增加1
3.c每次增加 a*(b的增加量)

注意：如果a的初始值是0的话，那k>=1的情况就变成条件2了
总结：P之前 'A’的个数 = P与T之间’A’的个数 * T之后’A’的个数 ：c=a*b

结合三个条件 , 总结起来就是：
1.P和T只能出现一次，而且P在T之前
2.P和T之间至少1个’A’
3.P之前 'A’的个数 = P与T之间’A’的个数 * T之后’A’的个数

代码实现

补充：c++ find函数（自己写一个也非常容易，这里不赘述）

#include <iostream>
#include <string>
using namespace std;
int n;//需要检测的字符串的个数
string a[20];//存放要输入的字符串
bool b[20];//存放输出结果
string ans[]={"NO","YES"};//下标0刚好是NO,下标1刚好是YES，对应false和true
bool check(string s){//P出现的位置，T出现的位置，P出现的个数，T出现的个数int P_loc=-1,T_loc=-1,P_Num=0,T_Num=0;//P之前A的个数，P与T之间A的个数，T之后A的个数int A_Num1=0,A_Num2=0,A_Num3=0;P_loc=s.find('P');T_loc=s.find('T');if(P_loc>T_loc) return false;//如果P在T之后if(P_loc+1==T_loc) return false;//如果P和T是相邻的for(int i=0;i<s.length();i++){if(P_Num>1||T_Num>1) return false;if(s[i]=='P'){P_loc=i;P_Num++;//记录P出现的次数} else if(s[i]=='T'){T_loc=i;T_Num++;//记录T出现的次数} //记录三种情况A出现的次数else if(s[i]=='A'){if(P_loc!=-1&&i<P_loc)A_Num1++;if(P_loc!=-1&&T_loc!=-1&&i>P_loc&&i<T_loc)A_Num2++;if(T_loc!=-1&&i>T_loc)A_Num3++;} else return false;}if(A_Num2*A_Num1==A_Num3)return true;return false;
}
int main(){cin>>n;for(int i=0;i<n;i++){cin>>a[i];b[i]=check(a[i]);}for(int i=0;i<n;i++)cout<<ans[b[i]]<<endl;
}