PAT乙级刷题记录——1003 我要通过！ (20分)

89 阅读 0 评论 59 点赞

我是靠谱客的博主朴素口红，最近开发中收集的这篇文章主要介绍PAT乙级刷题记录——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

思路

这题首先要看懂题意，要是题意看懂了，也是很好做的。条件1和条件2没什么好说的，比较好理解，尤其要注意条件3：【如果 aPbTc是正确的，那么 aPbATca也是正确的】，用“人话”来说就是，如果某一个字符串是正确的，那么在P和T之间再插一个A，并且在字符串最后再插入左边部分的字符串a（注意，这里一定要是左边的字符串a，我一开始以为是随便什么长度的字符串都行，所以WA了两个测试点），那么此时的形式也是对的。

举例来说，AAPATAA符合条件2，因此，在中间插一个A，以及最后插入左边部分，得到AAPAATAAAA也是正确的。

所以，对于给定的一个PAT字符串，我们只需要寻找P和T中间A的个数，每删掉一个中间的A，就要从字符串右边删掉左边部分A的个数，直到出现xPATx或者PAT的形式。比如：AAAPAAATAAAAAAAAA，这个也是符合题目要求的，那么怎么按照我们说的来操作呢，很简单，因为P和T中间要删去2个A，所以右边部分要删去2×3个A，删去之后，左边部分的长度和右边部分的长度相等，说明对称，即：是一种可行方案。

一般化来说，假设中间部分的字符串是mid，左边部分是left，右边部分是right（均不包含P和T两个字母），因此，上面的思路转化为代码就是：

right.length() = right.length()-(mid.length()-1)*left.length();
if(left.length()!=right.length()) cout<<"NOn";
else cout<<"YESn";

代码

#include<cstdio>
#include<stdlib.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
cin.ignore();
for(int i=0;i<n;i++){
bool flag = true;
string tmp;
getline(cin, tmp);
if(tmp.find("P")!=string::npos&&tmp.find("A")!=string::npos&&tmp.find("T")!=string::npos){
string left, mid, right;
int posP = tmp.find("P");
int posT = tmp.find("T");
if(posP>0){
left = tmp.substr(0, posP);
for(int i=0;i<left.length();i++){
if(left[i]!='A') flag = false;
}
}
if(posT<tmp.length()-1){
right = tmp.substr(posT+1);
for(int i=0;i<right.length();i++){
if(right[i]!='A') flag = false;
}
}
mid = tmp.substr(posP+1, posT-posP-1);
for(int i=0;i<mid.length();i++){
if(mid[i]!='A') flag = false;
}
if(right.length()-(mid.length()-1)*left.length()!=left.length()) flag = false;
if(flag==true) cout<<"YESn";
else cout<<"NOn";
}
else{
cout<<"NOn";
}
}
return 0;
}