1003 我要通过! (20分)
“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件,系统就输出“答案正确”,否则输出“答案错误”。
得到“答案正确”的条件是:
- 字符串中必须仅有
P
、 A
、 T
这三种字符,不可以包含其它字符;
- 任意形如
xPATx
的字符串都可以获得“答案正确”,其中 x
或者是空字符串,或者是仅由字母 A
组成的字符串;
- 如果
aPbTc
是正确的,那么 aPbATca
也是正确的,其中 a
、 b
、 c
均或者是空字符串,或者是仅由字母 A
组成的字符串。
现在就请你为 PAT 写一个自动裁判程序,判定哪些字符串是可以获得“答案正确”的。
输入格式:
每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (<10),是需要检测的字符串个数。接下来每个字符串占一行,字符串长度不超过 100,且不包含空格。
输出格式:
每个字符串的检测结果占一行,如果该字符串可以获得“答案正确”,则输出 YES
,否则输出 NO
。
输入样例:
8 PAT PAAT AAPATAA AAPAATAAAA xPATx PT Whatever APAAATAA
|
输出样例:
解题思想:这道题的重点就是要发现规律
P
和T
的个数只能为1
P
和T
之间的A
的个数必须大于等于1
P
左边A
的个数乘以P
和T
之间A
的个数等于T
后面A
的个数
代码如下:
C语言:
#include <stdio.h> //重点是p之前a的个数与p,t之间a的个数的积等于t之后的a #include <string.h> int pat(char s[]) { int res = 1; int num_p = 0, num_t = 0, num_a = 0; int lc1 = 0, lc2 = 0; int len = strlen(s); for (int j = 0; j < len; ++j) { if(s[j] != 'P' && s[j] != 'A' && s[j] != 'T') { res = 0; return res; } if(s[j] == 'P') { num_p++; lc1 = j; } else if(s[j] == 'T') { num_t++; lc2 = j; } else { num_a++; } } if (num_p != 1 || num_t != 1 || num_a < 1) { res = 0; return res; } if((lc1 * (lc2 - lc1 - 1)) != len-lc2-1) { res = 0; } return res; }
int main() { int n, i = 0,len; char str[10][100]; scanf("%d", &n); len = n; while (n--) { scanf("%s", str[i++]); } for (int j = 0; j < len; ++j) { if(pat(str[j])) { printf("YES"); } else { printf("NO"); } if(j < len - 1) { printf("\n"); } } return 0; }
|
C++:
#include <iostream> #include <map> using namespace std; int main() { int n, p = 0, t = 0; string s; cin >> n; for(int i = 0; i < n; i++) { cin >> s; map<char, int> m; for(int j = 0; j < s.size(); j++) { m[s[j]]++; if (s[j] == 'P') p = j; if (s[j] == 'T') t = j; } if (m['P'] == 1 && m['A'] != 0 && m['T'] == 1 && m.size() == 3 && t-p != 1 && p * (t-p-1) == s.length()-t-1) printf("YES\n"); else printf("NO\n"); } return 0; }
|