PAT乙1003.我要通过

发表于 | 分类于

题目

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

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

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

现在就请你为PAT写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。
输入格式： 每个测试输入包含1个测试用例。第1行给出一个自然数n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过100，且不包含空格。

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

输入样例：
8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
输出样例：
YES
YES
YES
YES
NO
NO
NO
NO

思路

感觉自己都大三了，在做题方面依然像个初学者，哎。还是得勤刷题啊。

此题是道规律题，考点就是让学生找规律。

三个条件都需要满足。首先第一个条件，就是不出现其他字符，直接判断即可；第二个条件，就是说明PAT两边的x是相同字符串，而且只能是由A组成的字符串；对于第三个条件，这个地方其实我没有理解成数量关系，因此导致有些混乱：一开始中间部分肯定是“PAT”，中间每增加一个‘A’，右端增加a，也就等价于：a*b=c，均指字符串a，b，c中‘A’的个数。更清晰的理解为a*(b+1)=c+a（哎，我为什么没有想到。）

我发现自己的薄弱点就是不知道怎么计算这些不同位置A的个数，并且在考虑P和T位置可能颠倒的情况没有使用下标，而是老想着在循环中计算个数。另外就是对字符串的操作还不熟练，并且题意也没有弄明白，导致判断条件特别多，也没有做对。知道了一定的方法后，重新在原来的框架下做。

现在自己的版本，满分20分，只能得18分，还有两分不知道为何错误。贴出我自己看着都嫌弃的代码：

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
70
71
72
73
74
#include <iostream>
using namespace std;

int main(){
	int n;
	cin >> n;
	while(n--){
		string str;
		cin >> str;
		int again = 0;
		int cntp = 0;
		int cntt = 0;
		int posP=-1;
		int posT=-1; 
		for(int i=0; i<str.length(); i++){
			if(str[i]!='A' && str[i]!='P' && str[i]!='T'){ //出现其他字符 
				cout << "NO" << endl; 
				break;
			}
			else if(str[i] == 'P'){ //有两个及以上的P 
				posP = i;
				cntp ++;
				if(cntp > 1){
					cout << "NO" << endl; 
					break;
				}
			}
			else if(str[i] == 'T'){ //有两个及以上的T 
				posT = i;
				cntt ++;
				if(cntt > 1){
					cout << "NO" << endl;
					break;
				}
			}
			else{
				again = 1;
				break;
			}
			if(posP >= posT-1 && posP>=0 && posT>=0){
				cout << "NO" << endl;
				break;
			}
		}
		
		if(again == 1){ //这里需要计算出三个位置的A的个数,再用公式a*b=c来判断正误。 
			//又卡在这里了。。。 
			//a的个数可以用P的下标来表示,要换个思路。 
			int a=0, b=0, c=0;
			for(int i=0; i<str.length(); i++){
				if(str[i] == 'P'){
					a = i;
				}
				if(str[i] =='T'){
					b = i-(a+1);
				}
			} 
			c = str.length()-a-b-2;
			
			if(a * b == c){
				cout << "YES" << endl;
			}
			else{
				cout << "NO" << endl;
			}
		}
		
	}
}

/***
没有判断P/A/T三个字母必须存在，因此出错。

***/

哎，不忍直视的代码。虽然说得到了一定的分数，但是在上面计算三个位置A的个数，我是看了别人的才会的。一直想着如何在循环里计算个数，没想到P和T的坐标也可以利用起来的，太傻了。下面先查找与我的思路相似的代码进行修改：

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
#include <iostream>
using namespace std;
int main(){
	int n;
	cin >> n;
	while(n--){
		string str;
		cin >> str;
		int cntp = 0, cntt = 0;
		bool result = true;
		for(int i=0; i<str.length(); i++){
			if(str[i]!='A' && str[i]!='P' && str[i]!='T'){ //出现其他字符 
				result = false;
				break;
			}
			else if(str[i] == 'P'){ //有两个及以上的P 
				cntp ++;
				if(cntp > 1){
					result = false;
					break;
				}
			}
			else if(str[i] == 'T'){ //有两个及以上的T 
				cntt ++;
				if(cntt > 1){
					result = false;
					break;
				}
			}
		}
		
		if(result == true){ //这里需要计算出三个位置的A的个数,再用公式a*b=c来判断正误。  
			//a的个数可以用P的下标来表示,要换个思路。
			int count1 = str.find("P"); 
			int count2 = str.find("A");
			int count3 = str.find("T"); //索引查找出现某字符串的第一个位置,可替代循环查找 
			if(count1 == -1 || count2 == -1 || count3 == -1){
				result = false; 
			}
			else{
				int a = count1;
				int b = count3 - (a+1);
				int c = str.length()-a-b-2;
				if(a*b == c) 
					result = true;
				else 
					result = false;		
			}
		}
		if(result == true){
			cout << "YES" << endl;
		}
		else{
			cout << "NO" << endl;
		}
	}
}

通过对比可以知道，我不一样的地方时，没有判断P，A，T三个字母有可能不在的情况，这也是我错误的原因。考虑得太不周到了。。。戴斯铭你清醒一点！做题要考虑所有情况！另外，find函数非常方便，要善于使用。基本就按照上面的思路，即可将题目完成。