PAT-B] 1003. 我要通过！ [字符串处理]

链接：1003. 我要通过！(20)

题意

一道字符串处理问题。
输入一行字符串 :

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

满足这三个条件就输出“YES”， 否则输出“NO”

分析

条件1 只是针对字符串有限制，作前提。

再看 2 和 3 :
条件2 是“YES”的直接要求，而条件3 是 间接要求

整理思路 :

  1. 首先满足前提，字符串中分别只能依次出现一个 P 和 一个 T，其余若干项只能填充 A
  2. 条件2 中提出 P 和 T 之间由一个 A 分隔，且 a == c （小写表示长度，下同）。 条件3 中提出 aPbTc 正确，则 aPbATca 也正确，这就给了我们一个关系式 : c == b * a。只要满足该关系式，字符串就能通过。

有一点注意 :
这道题有题意不清楚的地方。就是并不是 aPbTc 这种形式出现过了，aPbATca 才正确。只要递推到最后的式子满足条件2 就是“YES”

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
int N;
char c;
int f, P, T, i;
int main()
{
    while( ~scanf( "%d", &N ) ){
        getchar();
        for( int t = 0; t < N; t++ ){
            f = 1, i = -1, P = -1, T = -1;
            while( scanf( "%c", &c ) && c != '\n' ){
                i++;
                if( c == 'P' ){
                    if( P == -1 )   P = i;  //第一次遇到 P, 记录位置
                    else    f = 0;          //第二次遇到 P, 改结果 f 为不通过
                }
                else if( c == 'T'){     //同 P 的处理
                    if( T == -1 )   T = i;
                    else    f = 0;
                }
                else if( c != 'A' ) f = 0;  //遇 PAT 以外的字母, 改结果 f 为不通过
            }
            if( f ){
                if( P == -1 || T == -1 )    f = 0;  //判断是否有 P 和 T
                else if( P >= T - 1 )    f = 0;     //判断 P 和 T 的 位置是否满足要求
                else if( i - T != ( T - P - 1 ) * P )    f = 0; //关键递推式
            }
            if( f ) puts( "YES" );
            else    puts( "NO" );
        }
    }
    return 0;
}

小结

分析出结论就不难..
一开始会掉到我提到的注意的地方。（应该不是我脑回路不正常吧！）

字符串处理
PAT-B, 字符串处理