题目

“ 答案正确 ”是自动判题系统给出的最令人欢喜的回复。本题属于 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
10
11

10
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
APATTAA

输出样例：

1
2
3
4
5
6
7
8
9
10

YES
YES
YES
YES
NO
NO
NO
NO
NO
NO

鸣谢江西财经大学软件学院朱政同学、用户 woluo_z 补充测试数据！

思路

先理解一下答案正确的条件：

  1. 字符串只能包含'P', 'A', 'T'三种字符，简单，有其它字符就是错误的了。
  2. xPATx格式的是正确的。这个条件需要正确理解，当时就是在这条上想错了，结果好多次没有通过。两个x是代指相同的字符串。（有些人包括我理解错的原因大概是按照正则表达式的*去理解这里的x了）
  3. aPbTc正确，aPbATca也正确。翻译一下，就是P和T中间每增加一个A，需要将P之前的内容复制到字符串末尾，得到的新字符串就也是正确的。

结合这三点，总结起来就是：

  • 只存在'P', 'A', 'T'三种字符；
  • 'P', 'T'只能出现一次并且按照该顺序先后出现；
  • P&T之间不能没有A；
  • T之后A的数量 = P之前A的数量 × P&T中间A的数量。

代码实现：

  • 使用三个数count[3]记录P之前，P&T之间，T之后A的数量。

  • 为了检测'P', 'T'的出现及次序，使用一个标记变量pos：

    • 其值在出现P之前为0（使用count[0]记录P之前的A）
    • 只有在出现P且其值为0时，将值变为1（使用count[1]记录P&T之间的A）
    • 只有在出现T且其值为1时，将其变为2（使用count[2]记录T之后的A）

这样即可保证除此之外出现非'A'字符的情况都是不符合要求的。pos顺便还能作为count[]的索引。

代码

Github最新代码，欢迎交流

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

#include <stdio.h>

int main()
{
	char c;
	int num;
	scanf("%d", &num);
	/* read the rest of the line, make sure to start from a new line later */
	while ((c = getchar()) != '\n');

	for (int i = 0; i < num; i++) {
		/* pos: indicate the position of current index for count[]     */
		/* count[3]: number of As; before P, between P & T and after T */
		int pos = 0, count[3] = {0, 0, 0};
		while ((c = getchar()) != EOF) {
			if (c == 'A')                   /* count 'A's     */
				count[pos]++;
			else if (c == 'P' && pos == 0)  /* one P before T */
				pos = 1;
			else if (c == 'T' && pos == 1)  /* one T after P  */
				pos = 2;
			else                            /* 'wrong' string */
				break;
		}

		if (c == '\n'                       /* 1. no other characters at end */
		&& pos == 2                         /* 2. appearance of 'P' and 'T'  */
		&& count[1]                         /* 3. existance of 'A'           */
		&& count[2] == count[1] * count[0]) /* 4. relation between numbers   */
			puts("YES");
		else
			puts("NO");

		/* read the rest of the line */
		if (c != '\n')
			while ((c = getchar()) != EOF && c != '\n');
	}

	return 0;
}