Java教程

pat甲级——1003我要通过!

本文主要是介绍pat甲级——1003我要通过!,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

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

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

1.字符串中必须仅有 P、 A、 T这三种字符,不可以包含其它字符;
2.任意形如 xPATx 的字符串都可以获得“答案正确”,其中 x 或者是空字符串,或者是仅由字母 A 组成的字符串;
3.如果 aPbTc 是正确的,那么 aPbATca 也是正确的,其中 a、 b、 c 均或者是空字符串,或者是仅由字母 A 组成的字符串。

现在就请你为 PAT 写一个自动裁判程序,判定哪些字符串是可以获得“答案正确”的。

分析

  • 读入一个字符串,分别记录P,T的个数,字符P前面A的个数,P和T中间A的个数,字符T后面A的个数。如果这些加起来小于字符串长度,说明有其他字符,不满足条件一
  • 条件二:一个P,一个T,中间有一个A,P和T左右的子串ac相等,这样的字符串就是正确的
  • 条件三:一个递推式,告诉我们除了满足条件二的字符串正确,还有一种也是正确的,这种正确的字符串可以通过满足条件二的字符串推出来
    • 已知一个字符串满足条件二(a和c相等,b不是空串)。此时让b多加一个A,c加上子串a,得到的也是正确的
    • 继续递推:让b再多加一个a,c再加上字串a,得到的还是正确的
    • 因此条件三说的是:PT中间可以有多个A,有几个A,那么子串c就是子串a的多少倍。换句话说,条件一的基础上,c的长度=a的长度*b的长度,满足这个等式的字符串也是正确的
    • 看一种特殊情况:当PT中间只有一个A时,由上面的等式可得,ac子串理应相等。换句话说,条件三包含了条件二,因此只用判断条件一三即可

实现代码

#include<iostream>
using namespace std;
bool m(string str)
{
    unsigned int i,a,b,c,p,t;//i是字符串下标,abc分别记录P前面,PT中间,T后面的A的个数
    i=a=b=c=p=t=0;//p和t分别记录字符P和T的出现次数

    while(str[i]!='P'&&i<str.size())
    {
        if(str[i]=='A')
            a++;
        i++;
    }

    while(str[i]=='P'&&i<str.size())
        p++,i++;
    while(str[i]!='T'&&i<str.size())
    {
        if(str[i]=='A')
            b++;
        i++;
    }

    while(str[i]=='T'&&i<str.size())
        t++,i++;
    while(i<str.size())
    {
        if(str[i]=='A')
            c++;
        i++;
    }
    if(p!=1||t!=1)return false;//PT必须有且仅有一个
    if(b<=0)return false;//PT中间一定要有A
    if(a+b+c+2!=str.size())return false;//不能出现其他字符
    //如果有除PAT外的其他字母,那a+b+c+2是小于字符串长度的。上面也可以写成a+b+c+p+t
    
    if(c==a*b)return true;//第三个满足的条件
    else return false;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string a;
        cin>>a;
        if(m(a))
            puts("YES");
        else puts("NO");
    }
    return 0;
}
这篇关于pat甲级——1003我要通过!的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!