c++PTAB1003我要通过(找规律)

1003 我要通过! (20 分)
“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 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

思想核心

这三个条件分别是,仅仅含有PAT这三种字符,不含有其他,第二个条件是,任意形如"xPATx*都是正确的,x可以是空字符串,或者是仅由字母A构成的字符串。第三个前后中都可以有空字符串或者仅含a的字符串,感觉可以用正则。

完整源码

左边乘以中间==右边。

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\test\\input.txt","r",stdin);
    int t;
    cin >> t;
    char c[4] = {'P','A','T'};
    string a;
    while(t--){
        cin >> a;
        int left = 0,right = 0,mid = 0;
        int p= 0,t = 0;
        for(int i=0;i<a.size();i++){
            if(a[i]==c[1]&&p==0 && t==0){//判断L之前的
                left++;
                continue;
            }
            if(a[i]==c[0]){//判断P是否有
                p++;
                continue;
            }
            if(a[i]==c[1]&&p==1&&t==0){//判断P之后是否有A
                mid++;
                continue;
            }
            if(a[i]==c[2]){//判断是否有T
                t++;
                continue;
            }
            if(a[i]==c[1] && p==1 && t==1){//判断T之后是否有A
                right++;
                continue;
            }
        }
        if(left+mid+right+2 != a.length()) cout << "NO" << endl;
        else if(p==1 && t==1 && left*mid == right && mid!=0) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

方法2,所有的条件3都基于条件2,个人认为这段代码亮点是如何判断P一定在T的左边呢,假设p的位置是i,t的位置是j,j-i一定大于>=1不然那就是t在p的右边。这个真的亮到我了。

#include<cstdio>
#include<cstring>

int main()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\test\\input.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        char str[110];
        scanf("%s",str);//输入字符串
        int len = strlen(str);
        //分别代表P的个数,T的个数,除pat外字符的个数
        int num_p = 0,num_t = 0,other = 0;
        int loc_p = -1,loc_t = -1; //分别代表P的位置,T的位置
        for(int i =0;i<len;i++){
            if(str[i]=='P'){//若当前字符为P,则p的个数加1,位置表为i
                num_p++;
                loc_p = i;
            }else if(str[i] == 'T'){ //若当前字符为T,则T的个数加1,位置变为i
                num_t++;
                loc_t = i;
            }else if(str[i] != 'A') other++;//如果不是P,A,T中的一个,other++
        }
        //如果p的个数不为1,或者T的个数不为1
        //或者存在除pat外的字符,或者p和T之间没有字符
        if((num_p!=1) || (num_t != 1)|| (other!=0) || (loc_t-loc_p<=1)){
            printf("NO\n");
            continue;
        }
        //x,y,z的含义可通过loc_p和loc_t得到
        int x = loc_p,y = loc_t-loc_p-1,z= len-loc_t-1;
        if(z-x*(y-1) == x) {
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }

    return 0;
}

上一篇:省选模拟18


下一篇:6-2 邻接表存储图的广度优先遍历 (20 分)