首页 > > 程序设计 > C/C++ >

1003.我要通过(PAT)

2018-06-17 21:01:52来源：未知阅读 ()

题干如下:

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

现在需要做的就是考虑哪些形式的字符串是正确的形式。首先看条件1，字符串中仅包含P,A,T三种字符，意味着如果出现其他字符那么这个字符串肯定不满足条件。再看条件2，任意XPATX的字符串符合条件，这个好理解，就是PAT的两端要么是空字符要么是数量相等的A。最后比较关键的就是条件3，如果aPbTc是正确的，那么aPbATca也是正确的，这里很明显，b字符串无法为空，并且如果a串不等于c串，那么aPATc不正确(不满足条件2)。所以我们先假设b串为“A”，a串等于c串，那么aPATa是正确的，接着aPAAT(aa)也是正确的，继续往下推导，aPAAT(aa)是正确的，那么aPAAAT(aaa)是正确的，aPAAAT(aaa)是正确的，那么aPAAAAT(aaaa)也是正确的......可以总结出形如aP(n个A)T(n个a)形式的字符串是正确的。

综上所述，字符串的要求:aP(n个A)T(n个a)，其中a串为空或者A组成的字符串，n是大于等于0的整数。

 1 #include <iostream>
 2 using namespace std;
 3 int juge(char *s);
 4 int main(){
 5     int n,i;
 6     char s[10][105];
 7     cin>>n;
 8     for(i=0;i<n;i++)
 9       cin>>s[i];
10     for(i=0;i<n;i++){
11         if(juge(s[i]))
12           printf("YES\n");
13         else printf("NO\n");
14     }
15     return 0;
16 }
17 int juge(char *s){
18     int i,lena=0,lenb=0,len;
19     for(i=0;;i++){
20         if(s[i]=='A')               //a串中A的数目 
21          lena++;
22         else{
23         if(s[i]=='P')
24          break; 
25         else return 0;
26          }
27     }
28     for(i=i+1;;i++){
29         if(s[i]=='A')               //b串中A的数目 
30           lenb++;
31         else{
32         if(s[i]=='T')
33           break;
34         else return 0;
35         }
36     } 
37     if(lenb==0)  return 0;          //b为空串 
38     len = i +  lena*lenb+1; 
39     for(i=i+1;i<len;i++){           //ac串是否均为字符A 
40         if(s[i]=='A')
41           continue;
42         else return 0;
43     }
44     if(s[len]=='\0') return 1;      //是否到达字符串底部      
45     else return 0;
46 } //AC