PAT乙级1003 || 我要通过！（详解，C/C++示例，测试点分析）

Posted on In

我要通过！

题目描述

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

  1. 字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；
  2. 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
  3. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。
    现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式

每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。

输出格式

每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。

输入样例

1
2
3
4
5
6
7
8
9
8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA

输出样例

1
2
3
4
5
6
7
8
YES
YES
YES
YES
NO
NO
NO
NO

问题解决

解题思想

此题难点在于理解题意，有描述的3个条件可知，“答案正确”的字符串应满足以下条件：

  1. 必须只包含’P’，’A’，’T’三种字符，含有其它字符时必然是“答案错误”

  2. ‘PAT’两端只能含有’A’，由条件2知，两端’A’的个数相等时，此字符串输出“答案正确”

  3. 条件3是最难理解的，要使 aPbTc 是正确的，则b必定是’A’，a与c中’A’的个数相等时（可同时为0）恰好是条件2的情况，此时 aPbATca 也是正确的，以此迭代下去可以得到如下规律（设’P’之前、’P’与’T’之间及’T’之后’A’的个数为count1、count2和count3）：
    $$
    count1 \times count2=count3
    $$

理解了题意，代码过程就比较简单了。

代码示例（C）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#define N 101
int main()
{
    int n,i,j,count1,count2,count3;
    //count1统计P之前A的个数
    //count2统计P与T之间A的个数
    //count3统计T之后A的个数
    char str[N];
    scanf("%d",&n);
    getchar();//吸收掉缓冲区的换行符
    for(i = 0; i < n; i++){
        gets(str);
        j = 0;
        count1 = count2 = count3 = 0;
        while(str[j] != '\0'){
            if(str[j] == 'P'||str[j] == 'A'||str[j] == 'T'){
                //首先判断是否满足条件1
                //找到第一个P
                while(str[j] == 'A'&&str[j] != '\0'){
                    count1++;
                    j++;
                }
                if(str[j]!='\0'&&str[j] == 'P'){
                    j++;
                    while(str[j] == 'A'&&str[j] != '\0'){
                        count2++;
                        j++;
                    }
                    if(str[j]!='\0'&&str[j] == 'T'){
                        j++;
                        while(str[j] == 'A'&&str[j] != '\0'){
                            count3++;
                            j++;
                        }
                        if(str[j] != '\0'){//T之后还有除A之外的字符
                            printf("NO\n");
                            break;
                        }
                        else{
                            //满足count1 * count2 == count3且三者不同时为零
                            if((count1 * count2 == count3)&&(count1||count2||count3)){
                                printf("YES\n");
                                break;
                            }
                            else{
                                printf("NO\n");
                                break;
                            }
                        }
                    }
                    else{
                        printf("NO\n");
                        break;
                    }
                }
                else{
                    printf("NO\n");
                    break;
                }
            }
            else{//不满足条件1
                printf("NO\n");
                break;
            }
        }
    }
    return 0;
}

题目来源：PAT乙级1003
作者：CHEN, Yue
单位：浙江大学

稀罕作者