首页 > 其他分享 >PAT Basic 1003. 我要通过!

PAT Basic 1003. 我要通过!

时间:2023-02-24 20:22:05浏览次数:44  
标签:pchar char PAT NO else 我要 printf 字符串 1003

PAT Basic 1003. 我要通过!

1. 题目描述:

答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件,系统就输出“答案正确”,否则输出“答案错误”。

得到“答案正确”的条件是:

  1. 字符串中必须仅有 PAT这三种字符,不可以包含其它字符;
  2. 任意形如 xPATx 的字符串都可以获得“答案正确”,其中 x 或者是空字符串,或者是仅由字母 A 组成的字符串;
  3. 如果 aPbTc 是正确的,那么 aPbATca 也是正确的,其中 abc 均或者是空字符串,或者是仅由字母 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

相关文章