一、题目详情
问题描述：
“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 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
鸣谢江西财经大学软件学院朱政同学、用户 woluo_z 补充测试数据！
代码长度限制：16 KB
时间限制：400 ms
内存限制：64 MB
二、题目解析
代码：
#include <stdio.h>
#include <string.h>
int main()
{
/*
* str[10][101]：用于存储输入的字符串，各占一行，长度不超过100
* n：用于存储输入的字符串的个数，n<=10
* len：用于存储每个字符串的长度，便于循环处理
* sum_befor, sum_mid, sum_after：分别统计字符P之前、P和T之间、T之后字符A的个数，记为“前中后”
* b_P, b_T：分别标识首次出现字符P和T
* res：用于标识字符串是否合法(符合规则)
* i，j：循环变量
*/
int n, i, j, len, res, sum_befor, sum_mid, sum_after;
int b_P, b_T;
char str[10][101];
scanf("%d", &n);//读取整数n
getchar();//吃掉回车换行符，便于后续准确读取输入的字符串
//根据整数n循环获取字符串
for(i=0;i<n;i++)
{
gets(str[i]);
}
//按序依次判别字符串是否“答案正确”
for(i=0;i<n;i++)//分别处理每个字符串
{
len = strlen(str[i]);//获取字符串长度
res = 1; b_P = 0; b_T = 0;//标识值复位
sum_befor = 0; sum_mid = 0; sum_after = 0;//统计值复位
for(j=0;j<len;j++)//分别处理字符串中的每个字符
{
if(str[i][j]=='P' || str[i][j]=='A' || str[i][j]=='T')//合法字符
{
if(str[i][j]=='P')//若为字符P
{
if(b_P==0 && b_T==0)//首次出现字符P，且首个字符T未出现
{
b_P = 1;//标记字符P首次出现
continue;//跳出当前循环，进行下一次循环，随即处理下一个“字符”
}
else//再次出现字符P
{
res = 0;//非法字符，标记该字符串的输出结果为：NO
break;//结束当前循环，进行下一次循环，随即处理下一个“字符串”
}
}
if(str[i][j]=='A')//若为字符A，根据字符A出现的位置，则统计其数量
{
if(b_P==0)//尚未出现字符P
{
sum_befor++;//前位累计
}
if(b_P==1 && b_T==0)//首个字符P已出现，且首个字符T未出现
{
sum_mid++;//中位累计
}
if(b_T==1)//首个字符T已出现
{
sum_after++;//后位累计
}
}
if(str[i][j]=='T')//若为字符T
{
if(b_P==1 && b_T==0)//首次出现字符T，且已出现字符P
{
b_T = 1;//标记字符T首次出现
continue;//跳出当前循环，进行下一次循环，随即处理下一个“字符”
}
else//再次出现字符T
{
res = 0;//非法字符，标记该字符串的输出结果为：NO
break;//结束当前循环，进行下一次循环，随即处理下一个“字符串”
}
}
}
else//非法字符
{
res = 0;//非法字符，标记该字符串的输出结果为：NO
break;//该语句可省略；结束当前循环，进行下一次循环，随即处理下一个“字符串”
}
}
if(res)//字符串中的字符均合法
{
//前中后的数量需满足：sum_after=sum_befor*sum_mid，且sum_mid>0
if(sum_after == sum_befor * sum_mid && sum_mid > 0)
printf("YES\n");
else
printf("NO\n");
}
else//字符串中含有非法字符，输出NO
printf("NO\n");
}
return 0;
}提交结果(分数/满分)：
18/20
测试点1：答案错误
表明：您的程序未能对评测系统的数据返回正确的结果。原因不详，高手指点，拜谢！
提示：
1. “答案正确”的条件分析
- 字符串中必须仅有
P、A、T这三种字符，不可以包含其它字符； - 任意形如
xPATx的字符串都可以获得“答案正确”，其中x或者是空字符串，或者是仅由字母A组成的字符串； - 如果
aPbTc是正确的，那么aPbATca也是正确的，其中a、b、c均或者是空字符串，或者是仅由字母A组成的字符串。
条件1可知，规定了合法字符必须仅有三种：P、A、T。
条件2和条件3可视为对字符A出现的位置和数量加以约束，可用sum_befor、sum_mid、sum_after分别统计字符A在字符P之前、P和T之间、T之后出现的数量，与此同时，为便于分析条件，可用sum_a、sum_b和sum_c分别表示a、b和c中字母A的数量。
条件2可知，sum_mid必为1，且满足sum_after=sum_befor*sum_mid。
条件3可知，sum_befor、sum_mid、sum_after与sum_a、sum_b、sum_c的关系可表述为：sum_befor=sum_a，sum_mid=sum_b+1，sum_after=sum_c+sum_a。若aPbATca 是正确的，则sum_mid必大于等于1，且基于条件2需满足sum_a*(sum_b+1)=sum_a+sum_c，即可得到sum_a*sum_b=sum_c。通过联立上述关系，同样可得到sum_after=sum_befor*sum_mid。
综上所述，“答案正确”应满足以下两个条件：
- sum_after = sum_befor * sum_mid
- sum_mid > 0
if(res)//字符串中的字符均合法
{
//前中后的数量需满足：sum_after=sum_befor*sum_mid，且sum_mid>0
if(sum_after == sum_befor * sum_mid && sum_mid > 0)
printf("YES\n");
else
printf("NO\n");
}
else//字符串中含有非法字符，输出NO
printf("NO\n");2. 字母P、T出现的次序和字母A出现的数量问题
分别用b_P和b_T标识字母P、T是否出现，0表示未出现，1表示初次出现。
分别用sum_befor、sum_mid、sum_after分别统计字符A在字符P之前、P和T之间、T之后出现的数量。
1) 字母P、T出现的次序：
- 若字母P或T在初次出现后，不能再次出现，否则res=0
- 字母P必须出现在字母T之前，即满足：b_P==0&&b_T==0，否则res=0
if(str[i][j]=='P')//若为字符P
{
if(b_P==0 && b_T==0)//首次出现字符P，且首个字符T未出现
{
b_P = 1;//标记字符P首次出现
continue;//跳出当前循环，进行下一次循环，随即处理下一个“字符”
}
else//再次出现字符P
{
res = 0;//非法字符，标记该字符串的输出结果为：NO
break;//结束当前循环，进行下一次循环，随即处理下一个“字符串”
}
}- 字母T必须出现在字母P之后，即满足：b_P==1&&b_T==0，否则res=0
if(str[i][j]=='T')//若为字符T
{
if(b_P==1 && b_T==0)//首次出现字符T，且已出现字符P
{
b_T = 1;//标记字符T首次出现
continue;//跳出当前循环，进行下一次循环，随即处理下一个“字符”
}
else//再次出现字符T
{
res = 0;//非法字符，标记该字符串的输出结果为：NO
break;//结束当前循环，进行下一次循环，随即处理下一个“字符串”
}
}2) 字母A出现的数量：
- 字母P未出现时，即满足：b_P==0，则sum_before累加
- 首个字符P已出现，且首个字符T未出现时，即满足：b_P==1&&b_T==0，则sum_mid累加
- 首个字符T已出现，即满足：b_T==1，则sum_after累加
if(str[i][j]=='A')//若为字符A，根据字符A出现的位置，则统计其数量
{
if(b_P==0)//尚未出现字符P
{
sum_befor++;//前位累计
}
if(b_P==1 && b_T==0)//首个字符P已出现，且首个字符T未出现
{
sum_mid++;//中位累计
}
if(b_T==1)//首个字符T已出现
{
sum_after++;//后位累计
}
}