1003 我要通过!【PAT (Basic Level) Practice （中文）】

1003 我要通过!【PAT (Basic Level) Practice （中文）】

原题链接：1003 我要通过！ (pintia.cn)

1.前言

• 分数：20

• 难度：⭐️⭐️⚝⚝⚝

• 知识点：

  • C程序设计/分支控制/switch
  • C程序设计/函数与程序结构/函数定义与调用

• 运行限制

  代码长度限制	16 KB
  时间限制	400 ms
  内存限制	64 MB

2.题目描述

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

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

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

现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式：

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

输出格式：

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

输入样例：

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

输出样例：

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

3.解题思路

3.1题目分析

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

1. 字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；

   • 读到其他字符获得“答案错误”。

2. 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；

   • 如果x 是空字符串，则只有PAT ，如果x是仅由字母 A 组成的字符串则PAT前后的 A 的个数相同。

3. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。

   • 如果 a、 b、 c 均是空字符串，只剩下PT，没有A获得“答案错误”。

   • 如果 a、 b、 c 均是字母 A 组成的字符串，与第2点结合起来：xPATx是正确的推出xPAATxx 是正确的，xPAATxx 是正确的推出xPAAATxxx是正确的，xPAAATxxx是正确的推出xPAAAATxxxx是正确的，以此类推。P前A的个数乘以中间A的个数等于T后A的个数。

3.2基本思路

对字符串进行遍历，计算字符 P、 A、 T 的数量，并记录它们的位置，检查位置关系和数量关系是否满足要求。

3.3详解步骤

1. 输入需要检测的字符串个数。

2. 定义一个函数judge，判断字符串是否获得“答案正确”；

   • 循环读取字符串中的每一个字符；

   • 如果读到P，第一次读到P，记录P读到了一次，如果第二次读到P，结束循环，获得“答案错误”；

   • 如果读到T，读到P之后再读到T，记录T读到了1次，如果第二次读到T，或者之前没有读到P，结束循环，获得“答案错误”；

   • 如果读到A，分别记录前中后A的个数；

   • 如果读到其他字符，循环终止，获得“答案错误”；

   • 读取结束之后

     • 如果P或T其中任一一个不存在，或者中间没有A，则获得“答案错误”；

     • 如果满足P、T都存在，中间有A，P前A的个数乘以中间A的个数等于T后A的个数，获得“答案正确”。

     • P前A的个数乘以中间A的个数不等于T后A的个数，获得“答案错误”。

3. 循环读取字符串，调用函数judge判断，输出 YES或 NO。

3.4注意点

可以获得“答案正确”的最终条件需要结点2、3两点推导得出结论。

4.参考答案

#include 
//定义一个函数judge，判断字符串是否获得“答案正确”；
int judge( char *ins ){
    //n1, n2, n3记录在前中后位置A的个数
    int i, n1, n2, n3, P, T;
    n1 = n2 = n3 = 0;
    P = T = 0;
    //循环读取字符串中的每一个字符
    for (i=0; ins[i]!='\0'; i++) {
        switch (ins[i]) {
        //如果读到P
        case 'P':
            if (P)return 0;//如果第二次读到P，结束循环，获得“答案错误”
            else P = 1;//第一次读到P，记录P读到了一次
            break;
        //如果读到T
        case 'T':
            if (!P || T)return 0;//如果第二次读到T，或者之前没有读到P，结束循环，获得“答案错误”；
            else T = 1;//读到P之后再读到T，记录T读到了1次
            break;
        //如果读到A        
        case 'A':
            if (!P) n1++;//记录P前A的个数
            else if (!T) n2++;//记录中间A的个数
            else n3++;//记录T后A的个数
            break;
        //如果读到其他字符，循环终止，获得“答案错误”；
        default:
            return 0;
            break;
        }
    }
    //如果P或T其中任一一个不存在，或者中间没有A，则获得“答案错误”；
    if (!(P&&T)||!n2)return 0;
    //如果满足P、T都存在，中间有A，P前A的个数乘以中间A的个数等于T后A的个数，获得“答案正确”。
    if ((n1*n2)==n3)return 1;
    //P前A的个数乘以中间A的个数不等于T后A的个数，获得“答案错误”。
    else return 0;
}
int main(){
    //定义存储输入字符串的数组char ins[101]
    char ins[101];
    int n,i;
    //读取字符串个数n
    scanf("%d", &n);
    //循环读取字符串，调用函数judge判断，输出 YES或 NO；
    for(i=0;i<n;i++){
        scanf("%s", ins);
        if (judge(ins))printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

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