题目简介:
答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 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
| 8 PAT PAAT AAPATAA AAPAATAAAA xPATx PT Whatever APAAATAA
|
输出样例:
1 2 3 4 5 6 7 8
| YES YES YES YES NO NO NO NO
|
思路:
三个条件汇总在一起的意思就是:
- P,T必须有且仅由一次出现,且P,T中间得有A
- 开头A的数量 * 中间A的数量 = 结尾A的数量
- 其他字母不得出现
所以我先把P和T的位置找出来,从而来进行判断。
tip:
代码如下:
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 75 76 77 78 79 80
| #include <iostream> #include <string> #include <unordered_map>
using namespace std;
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) {
int flag = 0; string str; cin >> str; if (str.size() < 3) {
cout << "NO" << endl; continue; }
int p_pos = str.find("P"); if (p_pos == str.npos) {
cout << "NO" << endl; continue; }
for (int j = 0; j < p_pos; j++) {
if (str[j] != 'A') {
flag = 1; break; } }
int t_pos = str.find("T"); if (t_pos == str.npos) {
cout << "NO" << endl; continue; }
if (t_pos - p_pos == 1) {
cout << "NO" << endl; continue; } for (int j = p_pos + 1; j < t_pos; j++) {
if (str[j] != 'A') {
flag = 1; break; } }
for (int j = t_pos + 1; j < str.size(); j++) {
if (str[j] != 'A') {
flag = 1; break; } }
if ( (p_pos * (t_pos - p_pos - 1)) != (str.size() - t_pos - 1) ) flag = 1;
if (flag == 0) cout << "YES" << endl; else cout << "NO" << endl; }
}
|