B1003 我要通过！

Posted on |

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

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

字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；
任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
如果 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
12
13
14
15
16
17
18
19
输入样例：
8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
输出样例：
YES
YES
YES
YES
NO
NO
NO
NO

所有的Yes都源于条件2
条件3 逆推 最后都是判断条件2的成立

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAX 10001
#define INF 0x3f3f3f
using namespace std;

int main(){
	
	int t;
	cin>>t;
	getchar();
	while(t--){
		string s;
		getline(cin,s);
		int loc_p,loc_a,loc_t,others=0;
		int num_p=0,num_t=0,num_a=0;
		for(int i=0;i<s.length();i++){
			if(s[i]=='P'){
				loc_p=i;
				num_p++;
			}
			else if(s[i]=='T'){
				loc_t=i;num_t++;
			}
			else if(s[i]=='A'){
				num_a++;
			}
			else others++;
		}
		if(num_a==0||others!=0||num_p!=1||num_t!=1) {
		cout<<"NO"<<endl;continue;
	}
	int x=loc_p,y=loc_t-loc_p-1,z=s.length()-1-loc_t;
	if(z-(y-1)*x==x) cout<<"YES"<<endl;
	else 	cout<<"NO"<<endl;
	}
	
	
	
	
}

复习

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
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	
	cin>>n;
	string str;
	getchar();
	for(int i=0;i<n;i++){
		getline(cin,str);	
		int num_p=0,num_t=0,other=0;
		int loc_p=0,loc_t=0;
		for(int i=0;i<str.length();i++){
			if(str[i]=='P') {
				num_p++;loc_p=i; 
			}
			else if(str[i]=='T'){
				num_t++;loc_t=i;
			}
			else if(str[i]!='A')
			other++;
		}
			int left=loc_p,mid=loc_t-loc_p-1,right=str.length()-loc_t-1;
//			cout<<"!"<<left<<" "<<mid<<" "<<right<<endl;
		if(other>0||num_p!=1||num_t!=1||(loc_t-loc_p<=1)) {
			cout<<"NO"<<endl;
		} 
	
		else{
			
			right-=(mid-1)*left;
			if(right!=left) cout<<"NO"<<endl;
				else	cout<<"YES"<<endl;
		}
	
	}
	
}