【PAT乙级】1003 我要通过！

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

输出样例：

YES
YES
YES
YES
NO
NO
NO
NO

思路分析：

• 这个题关键在于读懂题，能读懂题很重要啊！一开始我就没看懂题，看了其他hxd的思路才算是明白了，下面我们就来分析一下题目的三个条件。

条件1：字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；

• 此处说的很清楚了，输入的字符串只能是带有P、A、T这三种字符的字符串，含有其他字符就算错

条件2：任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；

• 条件2结合条件1，就得出了输入的字符串必须含有P、A、T这三个字符，且形式必须为xPATx型，即PAT两边要么全为空；要么全是A,且两边对称

条件3：如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A组成的字符串。

• 满足条件3的前提是满足条件1和2，千万不要把它当成一个单独的正确形式！！！ 而要把它理解成为一个附加条件，即xPATx型正确，那么xPAATxx也是正确的，例如：APATA [√]，那么APAATAA也[√]
• 条件分析完了，那么解题的重点是什么呢？我认为解题的重点在于确定P前，P与T之间，T之后A的个数，我们对3个条件进行简单的分析就可以看出：P前A的个数 × P与T之间A的个数 = T之后A的个数 ；这是由于条件限制所得出的规律，a与c要对称，且b只能等于A，所以P与T之间A的个数要么是1要么是2，当P与T之间A的个数为1时，a = b，当P与T之间A的个数为2时，a = 2b
• 算法漏洞：通过对条件的分析，我们得出了简单算法 P前A的个数 × P与T之间A的个数 = T之后A的个数 ，但是这个算法有一个漏洞在于：APT为显示yes，这是因为1 × 0 = 0，符合算法条件，这是目前市面上大多数解题思路都没有想到的（也可能是懒得想，毕竟一个小题不值得浪费太多时间，不考虑这个也可以通过测试），为了保证解题的严谨性，我们可以再在代码上加上一个限制条件：P与T之间A的个数 != 0，来避免这种情况。

代码实现：

// 此处给出两种写法
// 这里的两种写法虽然写法不同，但是思想是一致的

// 写法一
#include<cstdio>
using namespace std;

void solve() {
	int x;
	scanf("%d", &x);
	getchar();
	for (int i = 0; i < x; i++) {
		int Aqnum = 0, Aznum = 0, Ahnum = 0;
		int P, A, T;
		P = A = T = 0; // P A T 的个数
		int rp = 1; // 控制 是 P 前 还是 P~T之间 和 T 之后的变量    【1 2 3 前中后】
		int cnd = 1; // 若含有其他字符就改为 0
		for (char s; s=getchar(), s != 'n';) {
			s == 'P' ? P++, rp = 2 : s == 'A' ? A++ : s == 'T' ? T++, rp = 3 : cnd = 0; // 可以使用if来写 其实也就是这个意思。
			switch (rp) {
			case 1:Aqnum++; break; // 前
			case 2:if (s != 'P') Aznum++; break; // 中
			case 3:if (s != 'T') Ahnum++; break; // 后
			}
		}
		if (P == 1 && A &&T == 1 && Aznum != 0 && Aqnum*Aznum == Ahnum && cnd) // 只有1个P 只有1个T 并且满足乘法 还满足 没有其他字符的话
			printf("YESn"); 
		else  
			printf("NOn"); 
	}
}
int main() {

	solve(); 
	return 0;
}


// 写法二
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	char s[107];
	while(t--)
	{ 
		int Pflag=0,Tflag=0; //P所在位置的下标，T所在位置的下标 
		int anum=0,pnum=0,tnum=0; //A的数量，P的数量，T的数量 
		int aanum=0,banum=0,canum=0; //P左边的A的数量，P和T中间A的数量，T右边的A的数量 
		scanf("%s",s);
		for(int i=0;i<strlen(s);i++)
		{

			if(s[i]=='A')anum++;
			else if(s[i]=='P')
			{
				Pflag=i;
				pnum++;
			}
			else if(s[i]=='T')
			{
				Tflag=i;
				tnum++;
			}
		}
		//按照条件可知：
		//P的个数有且只能是1，T的个数有且只能是1，A的个数最少是1
		//并且字符串中只能有这三种字符 
		if(pnum!=1||tnum!=1||anum==0||((pnum+tnum+anum)!=strlen(s)))
		{
			printf("NOn");
		}
		else
		{
			aanum=Pflag-0;       //P左边的A的数量 
			banum=Tflag-Pflag-1; //P和T之间的A的数量 
			canum=strlen(s)-Tflag-1; //T右边的A的数量
			if(canum==aanum*banum)
				printf("YESn");
			else 
				printf("NOn"); 
		}

	}
	return 0;
}

运行结果图：

最后

以上就是平常画板为你收集整理的【PAT乙级】1003 我要通过！的全部内容，希望文章能够帮你解决【PAT乙级】1003 我要通过！所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。