PAT乙级 1003.我要通过!

309

读题意很恶心,写起来要注意很多细节

题目


原题链接

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

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

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


解析


规则如下:
对于(x)PAT(x)一定是正确的,其中(x)是空字符串或者由A组成的字符串,并且两个(x)是相等的
而所有的(x)PA(*n)T(x*n)也是正确的,也即PT中间A的个数 乘上 P前面A的个数 等于 T后面A的个数

再加上判断PT中间至少有一个A即可

代码


C++解法


#include <cstdio>
#include <cstring>

const int maxn = 105;
char s[maxn];

bool judge() {
    bool hasP = false;
    bool hasT = false;
    bool wrong = false;
    int aNums[3] = {0, 0, 0};
    int len = strlen(s);
    for (int i = 0; i < len && !wrong; ++i) {
        if (s[i] == 'A') {
            if (!hasP && !hasT)
                ++aNums[0];
            if (hasP && !hasT)
                ++aNums[1];
            if (hasP && hasT)
                ++aNums[2];
            if (!hasP && hasT)
                wrong = true;
            continue;
        }
        if (s[i] == 'P') {
            if (hasP)
                wrong = true;
            else
                hasP = true;
            continue;
        }
        if (s[i] == 'T') {
            if (hasT)
                wrong = true;
            else
                hasT = true;
            continue;
        }
        wrong = true;
    }
    return hasP && hasT && aNums[1] >= 1 && (aNums[1] * aNums[0] == aNums[2]) &&
           !wrong;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", s);
        printf("%s\n", judge() ? "YES" : "NO");
    }
    return 0;
}


Python解法


import re


def judge(s):
    wrong = False
    l = s.split('P')
    if len(l) != 2:
        return False
    r = l[1].split('T')
    if len(r) != 2:
        return False
    if not re.match(r'[PAT]+', s):
        return False

    # print([l[0], r[0], r[1]])

    return (len(l[0]) * len(r[0]) == len(r[1])) and len(r[0]) > 0


n = int(input())
for i in range(n):
    s = input()
    print("YES" if judge(s) else "NO")


Java解法


import java.util.Scanner;

class Main {
    static Scanner in;

    public static boolean check(String s) {
        boolean hasP = false;
        boolean hasT = false;
        boolean wrong = false;
        int[] aNums = { 0, 0, 0 };

        for (int i = 0; i < s.length() && !wrong; ++i) {
            char c = s.charAt(i);
            if (c == 'P') {
                if (hasP == true) {
                    wrong = true;
                } else {
                    hasP = true;
                }
                continue;
            }
            if (c == 'T') {
                if (hasT == true) {
                    wrong = true;
                } else {
                    hasT = true;
                }
                continue;
            }
            if (c == 'A') {
                if (!hasP && !hasT) {
                    ++aNums[0];
                }
                if (hasP && !hasT) {
                    ++aNums[1];
                }
                if (hasP && hasT) {
                    ++aNums[2];
                }
                if (!hasP && hasT) {
                    wrong = true;
                }
                continue;
            }
            wrong = true;
        }
        // System.out.printf("%s %b %d %d %d\n",s,wrong,aNums[0],aNums[1],aNums[2]);
        return hasP && hasT && (!wrong && (aNums[0] * aNums[1] == aNums[2]) && aNums[1] > 0) == true;
    }

    public static void main(String args[]) {
        in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; ++i) {
            String s = in.next();
            if (check(s) == true)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
        in.close();
    }
}
发布评论
  • 点击查看/关闭被识别为广告的评论