PAT乙级B1003题解（本人以及算法笔记两份）
题目：
“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。
得到“答案正确”的条件是：
1.字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；
2.任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
3.如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。
现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。
输入格式：
每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。
输出格式：
每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。
输入样例：
9
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
输出样例：
YES
YES
YES
YES
NO
NO
NO
NO
NO
思路：仔细观察题目中的三个条件，可以看出最终输入的字符串中只能由一个P和一个T，这两个字符将整个字符串分为了三个部分，分别在P的左侧，P和T的中间，T的右侧，其中这三个部分可能由若干个A拼接的字符串或者空字符串，在满足一定条件下组合而成的。
笔者提供一个如下思路：
1.条件1是筛选是否含有PAT这三个字符，根据样例可以很清晰看出，P和T这两个字符必须存在，并且只能分别存在一次，而A这个字符至少存在一次，当然具体来说是存在与P和T之间的A字符数量至少为1，但是在此我们尽量细化问日，将这个情况放在23两个条件讨论。
2.案例中”xPATx“的形式，划分下来就是在P左边以及T右边出现的字符串中只有A或空字符串，并且两者形式一摸一样。
3.如果按照条件3去构造字符串，很明显符合条件的字符串将有无数种，那么直接演绎推理是不现实的，这个时候就可以考虑递归思想的灵活使用了。“aPbATca”可以逆推到“aPbTc”上，通过添加起始判定条件可以很容易解构条件3.
下面是本人代码实现：
#include
using namespace std;
//获取字符串的长度
int GetLength(char str[]);
//获取子串长度
int GetSubLength(char str[], int begin, int end);
//获取元素在串中位置
int LocateElem(char str[], char ch);
//获取元素在串中的数量
int GetElem(char str[], char ch, int begin, int end);
bool FirstCondition(char str[]);
bool SecondCondition(int A1, int A2, int A3);
int main()
{
int n;
cin >> n;
while (n--)
{
char str[110];
cin >> str;
int len = GetLength(str); //字符串的总长度
//判断前的准备工作
//根据字符串中P和T的位置将字符串分为三个部分
int Ppos = LocateElem(str, 'P');
int Tpos = LocateElem(str, 'T');
//A1 A2 A3分别对应三个部分字串中A的个数
int A1 = GetElem(str, 'A', 0, Ppos);
int A2 = GetElem(str, 'A', Ppos + 1, Tpos);
int A3 = GetElem(str, 'A', Tpos + 1, len);
//先进行第一轮判断,再进行第二轮条件的判断
if (FirstCondition(str) && SecondCondition(A1, A2, A3))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
//获取字符串的长度
int GetLength(char str[])
{
int len = 0;
while (str[len] != '\0')
len++;
return len;
}
//获取子串长度
int GetSubLength(char str[], int begin, int end)
{
int cnt = 0;
for (int i = begin; i < end; i++)
cnt;
return cnt;
}
//获取元素在串中位置
int LocateElem(char str[], char ch)
{
int pos = 0;
while (str[pos] != ch)
pos++;
return pos;
}
//获取元素在串中的数量
int GetElem(char str[], char ch, int begin, int end)
{
int cnt = 0;
for (int i = begin; i < end; ++i)
if (str[i] == ch)
cnt++;
return cnt;
}
//第一判断条件
bool FirstCondition(char str[])
{
//P和T的数量有且仅有，等于1
//A的数量至少为1
//PAT的总数量加起来等于字符串的数量
int len = GetLength(str); //字符串的长度
int Pcnt = GetElem(str, 'P', 0, len); //串中P的数量
int Tcnt = GetElem(str, 'T', 0, len); //串中T的数量
int Acnt = GetElem(str, 'A', 0, len); //串中A的数量
int sum = Pcnt + Acnt + Tcnt; //字符串中PAT总共的数量
if (Pcnt == 1 && Tcnt == 1 && Acnt >= 1 && sum == len)
return true;
return false;
}
//第二判断条件
bool SecondCondition(int A1, int A2, int A3)
{
if (A1 < 0 || A2 < 0 || A3 < 0)
return false;
if ( A2 == 1 && A1 == A3)
return true;
else
{
A2 = A2 - 1;
A3 = A3 - A1;
return SecondCondition(A1, A2, A3);
}
}
算法笔记代码实现（包含一定数学技巧）
思路：
总体思路和上述类似，但是经过进一步分析可以发现一些规律，每次A2回退的步骤中都会减1，因此从初始字符串回退到PAT这个格式，需要进行A2-1次回退。而T右边A的个数A3再经过A2-1次回退后将变成A3-A1*(A2-1)，这个时候判断条件仍然是P左边A的个数等于T右边A的个数，即A1 == A3-A1*(A2-1)，如果成立则输出"YES"，否则输出’NO‘
参考代码
#include
#include
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
char str[110];
scanf("%s",str); //输入字符串
int len = strlen(str);
//分别表示P的个数、T的个数、除PAT外字符的个数
int num_p =0,num_t=0,other=0;
int loc_p =-1,loc_t=-1; //分别表示P的位置、T的位置
for(int i=0;i<len;i++)
{
//若当前字符为P，则P的个数加1，位置变为i
if(str[i] == 'P')
{
num_p++;
loc_p = i;
}
//若当前字符为T，则T的个数加1，位置变为i
else if(str[i]=='T')
{
num_t++;
loc_t = i;
}
//如果不是PAT中的一个，则other++
else if(str[i] == 'A')
other++;
if((num_p!=1)||(num_t!=1)||(other!=0)||(loc_t-loc_p<=1))
{
printf("NO\n");
continue;
}
int A1 = loc_p, A2= loc_t-loc_p-1,A3=len-loc_t-1;
if(A1 == A3-A1*(A2-1))
{
printf("YES\n");
}
else
printf("NO\n");
return 0;
}
//tips:算法笔记代码变量表示有点混乱，笔者没有进一步验证，有代码问题欢迎询问。