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。

输入样例：

10 PAT PAAT AAPATAA AAPAATAAAA xPATx PT Whatever APAAATAA APT APATTAA 

输出样例：

YES YES YES YES NO NO NO NO NO NO 

分析：

1. 字符串只能由P，A，T由三个字符组成

2. 题中“a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。” 我理解为：要么a，b，c都是空的，或者a，b，c都是相同的字符串，比如:a=“AA”，b=“AA”，c=“AA我觉得这是我做不到的原因之一(还是太好吃了(？ ?_?)?）

我不明白问题的意思。下面是必须的17分的代码：

#include <iostream> #include <cstdio> #include <string>  using namespace std;   int n; string s;  int main() { 
         scanf("%d", &n);  while (n--) { 
          cin >> s;      //通过寻找子串   if (s=="PAT"|| s == "PATA" || s == "APAT" || s.find("APATA") != string::npos) { 
           printf("YES\n");   }   else if (s.find("PAAT")!=string::npos ||     s.find("PAATA") != string::npos || 
			s.find("APAATA") != string::npos || 
			s.find("APAATAA") != string::npos) { 
       
			printf("YES\n");
		}
		else { 
       
			printf("NO\n");
		}
	}

	return 0;
}

参考大神的代码，以下是AC版本：

#include <iostream>
#include <cstdio>
#include <map>
#include <string>

using namespace std;	

int n;
string s;

int main()
{ 
       
	int p = 0, t = 0;		//P的下标，T的下标
	scanf("%d", &n);
	while (n--) { 
       
		cin >> s;
		map<char, int> m;
		for (int i = 0; i < s.length(); i++) { 
       
			m[s[i]]++;
			if (s[i]=='P') { 
       
				p = i;		
			}
			if (s[i] == 'T') { 
       
				t = i;
			}
		}

		//P和T只能出现1次
		//m['A'] != 0是为了防止出现PxT的情况
		//m.size() == 3只能有3个字符组成
		//p-t!=1不能出现PT中间没有A的情况
		//最后一条：我不理解，开头A的个数 * 中间A的个数==结尾A的个数, p*(t-p)==s.length()-t-1
		if (m['P']==1&& m['T'] == 1 && m['A'] != 0 && m.size() == 3 && t-p!=1 && p*(t-p-1)==s.length()-t-1) { 
       
			printf("YES\n");
		}
		else { 
       
			printf("NO\n");
		}
	}

	return 0;
}