image.png
image.png
這道題讓我想到了編譯原理的內容矩父，首先這道題的難點在于讀懂第3個條件.這三個條件不是孤立的铣卡，是有聯(lián)系的：
正確答案的字符串集合：條件2的字符串集合+條件3的字符串集合
條件3的字符串集合是由條件2的字符串集合擴充而來的。
我們先分析條件2：
xPATx 注意前后兩個x是一模一樣的偏竟。
x只能包含A或者為空
那么條件2的字符串集合是中間有一個PAT煮落，前后有數(shù)目一樣的字母A（0個或者n個）
再分析條件3：
我一開始讀條件3真是一頭霧水。讀了好幾遍踊谋，看了一下解析才回過味來蝉仇。
aPbTc：b中至少含有一個A，未擴充時a和c有同樣數(shù)目的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個數(shù)：(x-1) * y + y = z 也就是 x * y = z
示意圖
PS:這道題讓我學習到了一個挺有意思的函數(shù)：string類型的find_first_of()函數(shù)。它可以找到某個字符第一次出現(xiàn)的位置瓦糕，返回下標底洗。計算三個位置的A的數(shù)目很方便。
代碼：
#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的個數(shù)
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;
}
