1003

image.png
image.png
这道题让我想到了编译原理的内容，首先这道题的难点在于读懂第3个条件.这三个条件不是孤立的，是有联系的：
正确答案的字符串集合：条件2的字符串集合+条件3的字符串集合
条件3的字符串集合是由条件2的字符串集合扩充而来的。

我们先分析条件2：
xPATx 注意前后两个x是一模一样的。
x只能包含A或者为空
那么条件2的字符串集合是中间有一个PAT，前后有数目一样的字母A（0个或者n个）

再分析条件3：
我一开始读条件3真是一头雾水。读了好几遍，看了一下解析才回过味来。
aPbTc：b中至少含有一个A，未扩充时a和c有同样数目的A
aPbATca：b中添加一个字母A，c中添加一个a

那么设a中有y个字母A，那么未扩充的c也有y个字母A；
PT之间有x个字母A，除了最开始的PAT中的一个A，后来添加了(x-1)个A，扩充了(x-1)次；
T之后又z个字母A。

z的字母A个数：(x-1) * y + y = z 也就是 x * y = z

示意图

PS:这道题让我学习到了一个挺有意思的函数：string类型的find_first_of()函数。它可以找到某个字符第一次出现的位置，返回下标。计算三个位置的A的数目很方便。

代码：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int cou;
    cin>>cou;

    vector<string> strs;
    for(int i=0;i<cou;i++)
    {
        string str;
        cin>>str;
        strs.push_back(str);
    }

    for(int i=0;i<cou;i++)
    {
        string str=strs[i];
        bool flag=true;
        //条件一
        for(int j=0;j<str.length();j++)
        {
            if(str[j]!='P'&&str[j]!='A'&&str[j]!='T')
                flag=false;
        }

        //只有一个P
        int countP=0;
        for(int j=0;j<str.length();j++)
        {
            if(str[j]=='P')
                countP++;
        }
        if(countP!=1)
            flag=false;

        //只有一个T
        int countT=0;
        for(int j=0;j<str.length();j++)
        {
            if(str[j]=='T')
                countT++;
        }
        if(countT!=1)
            flag=false;

        //P在T之前
        if(str.find_first_of('P')>str.find_first_of('T'))
            flag=false;

        //计算三个位置A的个数
        int numA_1,numA_2,numA_3;
        numA_1=str.find_first_of('P');
        numA_2=str.find_first_of('T')-str.find_first_of('P')-1;
        numA_3=str.length()-str.find_first_of('T')-1;
        
        //位置2至少有一个A
        if(numA_2<1)
            flag=false;
        //a*b=c
        if(numA_1*numA_2!=numA_3)
            flag=false;

        if(flag)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }

    return 0;
}