2024年2月22日。
“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件,系统就输出“答案正确”,否则输出“答案错误”。
得到“答案正确”的条件是:
- 字符串中必须仅有
P
、A
、T
这三种字符,不可以包含其它字符; - 任意形如
xPATx
的字符串都可以获得“答案正确”,其中x
或者是空字符串,或者是仅由字母A
组成的字符串; - 如果
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,仅含有PAT三种字符,
那么每个字符都是需要检查的。
获取串x,串abc然后进行字符比对是比较麻烦,因为这里
的子串全是A或者空,我们可以用串长度表示符合条件的串
比如空串长度为0,AAA为3;
正确条件1:
xPATx正确,此时x为空,则是PAT型;这是基础条件;
正确条件2:
aPbTc正确,那么需满足正确条件1:即b为串“A”,
变为aPATc,此时应当满足a串与c串相同,无论非空与否;
以后这里用abc表示每个串的长度来代表串;因为正确串的内容仅含‘A';
当b==1时,a==c;此时满足xPATx;
当b==0时,此时无法满足aPbTc正确,为aPTc;
当b>1时,比如AAPAATA(a==2,b==2,c==1)
AAPAATA若是aPbTc型,不满足正确条件1,若是
aPbATca型,那么AAPATA为aPbTc型,也不满足,所以
无法获得答案正确;
我们分析b>1时的正确条件,任何aPbATca正确的前提的是上一个aPbTc正确
而最初的aPbTc最初b只能等于1,否则不满足正确条件1xPATx;
那么我们可以从最初的aPbTc往后面推到得出正确的一般式;发现正确条件2是
包含正确条件1的,可以用aPbTc来表示xPATx的;找到正确条件2的一般条件即可;
PAT正确,那么PAAT正确,如果PAAT正确,那么PAAT也是正确的。
这里是可以递推的。
然后就是递推式的表示
x为全A或空;
xPATx正确,xPAATxx正确;则xPAAATxxx正确;则xPAAAATxxxx正确;
xxPATxx正确;xxPAATxxxx正确;则xxPAAATxxxxxx正确;则xxPAAAATxxxxxxxx正确;
从这里我们可以逐渐看出递推式的规律,b一开始只能是字符A,然后a串一确定,后续一组
正确的也都确定了,a定也就是x定,即满足xPATx;
a=1,b=1,c=1; a=2,b=1,c=2;
a=1,b=2,c=2; a=2,b=2,c=4;
a=1,b=3,c=3; a=2,b=3,c=6;
a=1,b=4,c=4; a=2,b=4,c=8;
得出规律c==a*b;这里因为PT之间增加一个A字符,同时c也对应增加一个a串,满足成倍增加,可以乘法
意思是:b加1时,若a为2,则c加2,是按份增加;b加1后面c就加一份a;
c=a*b,并且b不能等于0;
*/
#include<iostream>
#include<string>
using namespace std;
void check(string s){
int a=0;
int b=0;
int c=0; //表示三个串的长度;
int flag=0; //flag为1表示该串不满足正确条件;
int Xp=0;
int Xt=0; //记录PT的下标;作为循环的边界;
//记录a串长度;
for(int i=0;i<s.length();i++){
if(s[i]=='A'){
a++; //a串A的个数;
}
else if(s[i]=='P'){
Xp=i; //找到P跳出;
break;
}
else{
flag=1; //不满足正确条件;
}
}
//记录b串长度;
for(int i=Xp+1;i<s.length();i++){
if(s[i]=='A'){
b++; //b串A的个数;
}
else if(s[i]=='T'){
Xt=i;
break; //找到T跳出;
}
else{
flag=1; //不满足正确条件;
}
}
//记录c串长度;
for(int i=Xt+1;i<s.length();i++){
if(s[i]=='A'){
c++; //c串A的个数;
}
else{
flag=1; //不满足正确条件;
}
}
//输出结果;
if(flag){ //flag为1表示该串不满足正确条件;
cout<<"NO"<<endl;
}
else{
if(c==a*b&&b!=0){ //aPbATca的条件;
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
}
int main(){
int n;
cin>>n; //输入字符串数;
string Data[n];
for(int i=0;i<n;i++){ //读入字符串;
cin>>Data[i];
}
for(int i=0;i<n;i++){
check(Data[i]); //逐个检查:
}
return 0;
}
/*
解题反思:
我第一次写这个题的时候用的是字符串逐个比较,然后实现的比较麻烦
后来看到别人的i*j==k;开始想是怎么样得出这个条件的,于是读别人
的代码,发现字符串全A可以用长度特征来表示字符串;然后是发现有递推
的规律,才写出了这道题,我第一次写的时候没有发现递推这一点,导致
有一个测试点无法通过,以后遇到相同类型的元素,可以考虑用数量来表示
串特征。然后还有一点就是写代码时赋值=和等价==要细心;
*/