[C++]PAT乙级1003. 我要通过!(17/20)
C++ 通过 20 17 PAT 乙级 我要 1003
2023-09-27 14:24:42 时间
/* 1003. 我要通过!(20) “答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于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 */ /* 思路: 方法1:规则制约法 复杂度:O(n) 方法2:递归 O(n^2) */ #include<stdio.h> #include <string.h> using namespace std; const int MAX_LENGTH = 100; //判断是否满足条件1:1. 字符串中必须仅有P, A, T这三种字符,不可以包含其它字符; bool isPATChars(char chs[], int len){ for(int i=0;i<len;i++){ if(chs[i] != 'P' && chs[i] != 'A' && chs[i] != 'T') return 0; } return 1; } bool isPAT(char chs[], int len){ if(len < 3) return false; int p_flag=-1;//标记P位置 int t_flag=-1;//标记T位置 int a_count=0; //统计中间a的个数:若中间a的个数为1-2个,正确;反之,不正确 for(int i=0;i<len;i++){ if(chs[i] == 'A'){ if(p_flag != -1){ if(t_flag == -1){ a_count++; } } } else if(chs[i] == 'P'){ if(p_flag == -1){//说明:找到第1个字符'P' p_flag = i; } else {//说明有超过1个字符'P'了 return false; } } else {//当前元素为 'T' if(t_flag == -1){//说明:找到第1个字符'T' if(p_flag == -1){ //说明: 此时出现的'T'比'P'先出现,错误情况 return false; } t_flag = i; //出现的第一个在'P'后面的 ‘T’ } else {//说明有超过1个字符'T'了 return false; } if(p_flag != -1){//说明:'P'在'T'之前出现了,正确情况 if(p_flag == i - 1){ //说明:'P'与'T'紧贴着,中间没有'A' 错误情况 return false; } } else {//说明:'P'在'T'之前出现了,错误情况 return false; } } } if(p_flag == -1 || t_flag == -1 || a_count>2 || a_count<1)//保证PAT均有出现 return false; return true; } int main(){ int size; char chs_arr[10][MAX_LENGTH]; scanf("%d", &size); for(int i=0;i<size;i++){ scanf("%s", (chs_arr+i)); } for(int i=0;i<size;i++){ //scanf("%s", (chs_arr+i)); //printf("%d", strlen(chs_arr[i])); if(isPATChars(chs_arr[i], strlen(chs_arr[i]))){ if(isPAT(chs_arr[i], strlen(chs_arr[i]))){ printf("YES\n"); } else { printf("NO\n"); } } else { printf("NO\n"); } } return 0; }
相关文章
- 笔记:windows环境下线程编程(C++实现同步与互斥)
- 贪心c++(结合LeetCode例题)
- c/c++多线程模拟系统资源分配(并通过银行家算法避免死锁产生)
- 【数据库开发】windows环境下通过c++使用redis
- C++-关键字:const
- C++:头文件的作用【头文件放函数声明,当源文件需要这些函数时,可以通过宏命令“#include”将该头文件包含进来,就可以使用头文件对应的具体函数了】
- C++中的关键字用法--- explicit
- [转]c++流缓冲---rdbuf()
- 快餐店运行模拟C++程序源码代写
- C++输入一个字符串,把其中的字符按照逆序输出的两种方法
- C++版修真小说
- windows下python调用C/C++以及使用C扩展python python通过pythonnet调用C# dll
- C++工程通过opencv找到自己定义的矩形中的两平行线的距离
- 【C++】C++核心编程部分-内存分区模型-引用-函数提高-类与对象-文件操作
- 数据结构(C++版)——7-1 队列的实现及基本操作(链栈实现,无上限)
- C++中常通过封装一些宏关键字来达到简化目的
- 学习Cocos2d-x Lua:从C++过渡到Lua
- cocos2d --- c++ 通过 sprite 显示摄像头数据解决方案(趟过的坑)
- Docker 安装C/C++编译环境
- C++通过COM接口操作PPT
- c++模板类
- 19.C++-(=)赋值操作符、初步编写智能指针
- C++opencv创建图像
- C++著名类库和C++标准库介绍