1003. 我要通过！(20)

题目链接：http://www.patest.cn/contests/pat-b-practise/1003

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

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

规则总结为：P之前的A的个数乘以P与T之间的A的个数等于P后面的A的个数

对于第2个规则x*1=x

对于第3个规则初始条件为aPbTc 是正确的，则说明b必定等于A，且a=c=A，结论为aPbATca 也是正确的，说明a*b=a*a,且c*a=a*a即a*b=c*a。然后第三条规则可以递归，产生式为b->bA。

代码如下：

 1 #include<iostream>
 2 #include<string>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int indexP,indexT,n,leng;
 7 string st;
 8 
 9 
10 int main()
11 {
12     cin>>n;
13     while(n--)
14     {
15         cin>>st;
16         indexP=st.find("P");
17         indexT=st.find("T");
18         leng=st.length();
19         if(indexP+1>=indexT||indexP==string::npos||indexT==string::npos)
20         {
21             cout<<"NO"<<endl;
22         }
23         else
24         {
25             string st1(st,0,indexP);
26             string st2(st,indexP+1,indexT-indexP-1);
27             string st3(st,indexT+1,leng-indexT-1);
28             string new_st=st1+st2+st3;
29             if(new_st.find_first_not_of("A")!=string::npos)
30             {
31                 cout<<"NO"<<endl;
32             }
33             else
34             {
35                 if(indexP==0&&leng-indexT-1==0)  //P和T之间可以有任意个A 
36                     cout<<"YES"<<endl; 
37                 else if(indexP*(indexT-indexP-1)==leng-indexT-1)  
38                     cout<<"YES"<<endl;  
39                 else  
40                        cout<<"NO"<<endl; 
41             }
42         }
43     }
44     return 0;
45 }

1003. 我要通过！(20)

相关推荐