PAT Basic 1003. 我要通过!
1. 题目描述:
“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件,系统就输出“答案正确”,否则输出“答案错误”。
得到“答案正确”的条件是:
- 字符串中必须仅有
P
、A
、T
这三种字符,不可以包含其它字符; - 任意形如
xPATx
的字符串都可以获得“答案正确”,其中x
或者是空字符串,或者是仅由字母A
组成的字符串; - 如果
aPbTc
是正确的,那么aPbATca
也是正确的,其中a
、b
、c
均或者是空字符串,或者是仅由字母A
组成的字符串。
现在就请你为 PAT 写一个自动裁判程序,判定哪些字符串是可以获得“答案正确”的。
2. 输入格式:
每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 \(n\) (≤10),是需要检测的字符串个数。接下来每个字符串占一行,字符串长度不超过 100,且不包含空格。
3. 输出格式:
每个字符串的检测结果占一行,如果该字符串可以获得“答案正确”,则输出 YES
,否则输出 NO
。
4. 输入样例:
10
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
APATTAA
5. 输出样例:
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
6. 性能要求:
Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB
思路:
首先条件1指出字符串只能含有'P','A','T'三种字符,所以遇到其它字符直接输出"NO"即可。
另外这道题的关键就是找出规律,通过条件2可知以下两种形式的字符串是输出"YES"的:
- "PAT" (x为空字符串时)
- "APATA" (x为字符'A'时)
然后就是按照条件3将以上两种形式的正确字符串进行递推,分别可以得到以下形式的正确字符串:
- "PAAT" / "PAAAT" / "PAAAAT" ...
- "APAATAA" / "APAAATAAA" / "APAAAATAAAA" ...
即正确字符串中有且只有一个'P'和'T',且对于第二种递推形式有等式\(count1 * count2 == count3\)成立,其中\(count1\),\(count2\)和\(count3\)分别代表P之前,PT之间和T之后的字符'A'的数量。而对于第一种递推形式其只有PT之间存在字符'A',但同样满足上述等式,所以实际上只需一个判断条件。
My Code:
// #include <stdio.h>
// 第一次的思路,以为P、T之间的A最多有2个,没看懂题意。参考别人的题解写的最终代码。
// int main(void)
// {
// unsigned char n; // number of positive int
// unsigned char count = 0; // count number of A between P, T
// unsigned char flag = 0; // flag to meet P or T
// char words[101];
// char * pchar;
// scanf("%d", &n);
// while(n)
// {
// scanf("%s", words);
// pchar = words;
// while(*pchar != '\0')
// {
// if(*pchar != 'P' && *pchar != 'T' && *pchar != 'A')
// {
// //printf("%c", *pchar);
// printf("NO\n");
// break;
// }
// else if(*pchar == 'P')
// {
// if(flag == 0)
// flag = 1;
// else
// {
// printf("NO\n");
// break;
// }
// }
// else if(*pchar == 'A')
// {
// if(flag == 1)
// count++;
// if(count > 2)
// {
// printf("NO\n");
// break;
// }
// }
// else // *pchar == 'T'
// {
// if(flag == 1 && count > 0)
// {
// flag = 0;
// count = 0;
// }
// else
// {
// printf("NO\n");
// break;
// }
// }
// pchar++;
// }
// flag = 0;
// count = 0;
// if(*pchar == '\0')
// printf("YES\n");
// n--;
// }
// return 0;
// }
#include <stdio.h>
int main(void)
{
unsigned char n = 0;
char words[101];
char *pchar;
unsigned char count1=0, count2=0, count3=0;
unsigned char flag1 = 0, flag2 = 0;
/* count1 correspond to A numbers preceding P
count2 correspond to A numbers between P T
count3 correspond to A numbers after T
here must have count1 * count2 == count3 */
scanf("%d", &n);
while(n)
{
scanf("%s", words);
pchar = words;
while(*pchar != '\0')
{
if(*pchar != 'P' && *pchar != 'T' && *pchar != 'A')
{
printf("NO\n");
break;
}
else if(*pchar == 'P')
{
if(flag1 == 0)
flag1 = 1;
else
{
printf("NO\n");
break;
}
}
else if(*pchar == 'A')
{
if(flag1 == 0)
count1++;
else if(flag2 == 0)
count2++;
else
count3++;
}
else // *pchar == T
{
if(flag2 == 0)
flag2 = 1;
else
{
printf("NO\n");
break;
}
}
pchar++;
}
if(*pchar == '\0')
{
if(count2 != 0 && (count1 * count2 == count3) && flag1 && flag2) // flag1, flag2 makesure the character 'P', 'T' exist and only one.
printf("YES\n");
else
printf("NO\n");
}
count1 = count2 = count3 = 0;
flag1 = flag2 = 0;
n--;
}
return 0;
}
标签:pchar,char,PAT,NO,else,我要,printf,字符串,1003
From: https://www.cnblogs.com/tacticKing/p/17152986.html