题目

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

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

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

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

分析

• 读入一个字符串，分别记录P，T的个数，字符P前面A的个数，P和T中间A的个数，字符T后面A的个数。如果这些加起来小于字符串长度，说明有其他字符，不满足条件一
• 条件二：一个P，一个T，中间有一个A，P和T左右的子串ac相等，这样的字符串就是正确的
• 条件三：一个递推式，告诉我们除了满足条件二的字符串正确，还有一种也是正确的，这种正确的字符串可以通过满足条件二的字符串推出来
  • 已知一个字符串满足条件二（a和c相等，b不是空串）。此时让b多加一个A，c加上子串a，得到的也是正确的
  • 继续递推：让b再多加一个a，c再加上字串a，得到的还是正确的
  • 因此条件三说的是：PT中间可以有多个A，有几个A，那么子串c就是子串a的多少倍。换句话说，条件一的基础上，c的长度=a的长度*b的长度，满足这个等式的字符串也是正确的
  • 看一种特殊情况：当PT中间只有一个A时，由上面的等式可得，ac子串理应相等。换句话说，条件三包含了条件二，因此只用判断条件一三即可

实现代码

#include<iostream>
using namespace std;
bool m(string str)
{
    unsigned int i,a,b,c,p,t;//i是字符串下标，abc分别记录P前面，PT中间，T后面的A的个数
    i=a=b=c=p=t=0;//p和t分别记录字符P和T的出现次数

    while(str[i]!='P'&&i<str.size())
    {
        if(str[i]=='A')
            a++;
        i++;
    }

    while(str[i]=='P'&&i<str.size())
        p++,i++;
    while(str[i]!='T'&&i<str.size())
    {
        if(str[i]=='A')
            b++;
        i++;
    }

    while(str[i]=='T'&&i<str.size())
        t++,i++;
    while(i<str.size())
    {
        if(str[i]=='A')
            c++;
        i++;
    }
    if(p!=1||t!=1)return false;//PT必须有且仅有一个
    if(b<=0)return false;//PT中间一定要有A
    if(a+b+c+2!=str.size())return false;//不能出现其他字符
    //如果有除PAT外的其他字母，那a+b+c+2是小于字符串长度的。上面也可以写成a+b+c+p+t
    
    if(c==a*b)return true;//第三个满足的条件
    else return false;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string a;
        cin>>a;
        if(m(a))
            puts("YES");
        else puts("NO");
    }
    return 0;
}