1003 我要通过!(PAT)

1003 我要通过!(PAT)传送门

思路:按照字符串顺序以最后一个P和最后一个T将字符串分成三部分(其实是哪个位置的P或T都行),统计这三部分的A的个数,然后按照题意分类讨论;

补充:其实本题在于理解第三种情况的意思:
如果我把aPbTc 改写成:如果xPbTx是正确的,那么xPbATxx也是正确的,你可能就懂了。1003 我要通过!(PAT)
AC代码

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;

int main()
{
	string s;
	int t;
	cin>>t;
	while(t--)
	{
		cin>>s;
		int pp=-1,tt=-1,flag=0;
		for(int i=0;i<s.size() ;i++)
		{
			if(s[i]!='A'&&s[i]!='P'&&s[i]!='T'){			//保证字符串中只有PAT
				cout<<"NO"<<endl;
				flag=1;
				break;
			}
			if(s[i]=='P') pp=i;				//P最后出现的下标
			if(s[i]=='T') tt=i;				//T最后出现的下标
		}
		if(flag)continue;
		if(pp==-1||tt==-1){		//P和T没有同时出现
			cout<<"NO"<<endl;
			continue;
		}
		int  sum1=0,sum2=0,sum3=0;		//统计三部分A出现的次数
		for(int i=pp;i>=0;i--)
		if(s[i]=='A')sum1++;
		
		for(int i=pp;i<tt;i++)
		if(s[i]=='A')sum2++;
		
		for(int i=tt;i<s.size() ;i++)
		if(s[i]=='A')sum3++;
		
		if(sum1==0&&sum3==0&&sum2!=0&&(sum2+2==s.size() ))	  //开头和结尾没有A时,P和T之间A的个数+2==字符串长度,保证没有多余的P和T出现;
		cout<<"YES"<<endl;
		else if(sum1!=0&&sum3!=0&&(sum3/sum1==sum2))  //开头和结尾都有A时,结尾A的个数一定得是开头A的个数的整数倍,并且这个整数一定是中间A的个数
		cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
} 
上一篇:BZOJ 1924 Sdoi2010 所驼门王的宝藏


下一篇:PP图|QQ图|正态性检验|K-S检验|S-W检验|