PAT 乙级 1003.我要通过! C++/Java
2024-09-05 01:25:28
1003 我要通过! (20 分)
“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件,系统就输出“答案正确”,否则输出“答案错误”。
得到“答案正确”的条件是:
- 字符串中必须仅有
P
、A
、T
这三种字符,不可以包含其它字符; - 任意形如
xPATx
的字符串都可以获得“答案正确”,其中x
或者是空字符串,或者是仅由字母A
组成的字符串; - 如果
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
分析:
- 只能有一个P一个T
- 对于 xPATx,PAT, AAPATAA都是YES,只要两端的 A 的个数相同
- PAT是正确的,那么PAAT也是正确的
- AAPATAA是正确的,那么AAPAATAAAA也是正确的
- 总结:只能有一个P和T,前面A的个数 * 中间A的个数 = 后面A的个数
- 可以用三个变量,front,mid,rear将每个部分的A的个数记录下来,最后判断front * mid是否等于rear
对于aPbTc和aPbATca,
#include <iostream>
#include <string>
using namespace std; bool pass(string str)
{
if (str == "PAT")
{
return true;
} int index, front, mid, rear;
index = front = mid = rear = ; while (str[index] == 'A')
{
index++;
front++; //记录前面A的个数
}
if (str[index] == 'P')
{
index++;
}
else
{
return false;
} while (str[index] == 'A')
{
mid++; //记录中间A的个数
index++;
} if (str[index] == 'T')
{
index++;
}
else
{
return false;
} while (str[index] == 'A')
{
rear++; //记录后面A的个数
index++;
} if (!str[index] && rear == mid * front && mid > )
{
return true;
} return false;
} int main()
{
int n;
string str;
cin >> n; for (int i = ; i < n; ++i)
{
cin >> str;
bool flag = pass(str);
if (flag)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
} return ;
}
map解法:
首先了解下 map 是什么, map 是 C++ 的STL容器,内部实现是红黑树(一种非严格意义的平衡二叉树,具有排序功能), map 提供一对一的关系
map<K, T> 类模板定义在头文件 map 中,它定义了一个保存 T 类型对象的 map, 每个 T 类对象都有一个关联的K类型的键。
map的特性:
- 所有的元素会根据元素的键值(key)自动排序
- map所有元素都是pair,同时拥有key(键值)和value(实值)
- pair的第一个元素视为键值key,第二个元素视为实值value
- map不允许两个元素拥有相同的键值
map的基本构造函数
map<int ,string >intMap; map<string , int >strMap; map< char ,string>charMap; map<sring, char>strMap; map<char ,int>charMap; map<int ,char >intMap;
map的基本操作函数
begin() 返回指向map头部的迭代器 clear() 删除所有元素 count() 返回指定元素出现的次数 empty() 如果map为空则返回true end() 返回指向map末尾的迭代器 equal_range() 返回特殊条目的迭代器对 erase() 删除一个元素 find() 查找一个元素 get_allocator() 返回map的配置器 insert() 插入元素 key_comp() 返回比较元素key的函数 lower_bound() 返回键值>=给定元素的第一个位置 max_size() 返回可以容纳的最大元素个数 rbegin() 返回一个指向map尾部的逆向迭代器 rend() 返回一个指向map头部的逆向迭代器 size() 返回map中元素的个数 swap() 交换两个map upper_bound() 返回键值>给定元素的第一个位置 value_comp() 返回比较元素value的函数
思路:
将 P, A, T 三个字符作为键值存入map,对应的value是它们出现的次数,最后还要判断 map.size()是否等于3
#include <iostream>
#include <string>
#include <map>
using namespace std; bool pass(string str)
{
map<char, int> charMap;
int length = str.size();
int posOfP = , posOfT = ;
for (int i = ; i < length; ++i)
{
charMap[str[i]]++;
if (str[i] == 'P')
{
posOfP = i; //这时候的i为P前面 A 的个数(执行完循环体的步骤才会执行++i)也可以理解为P的位置
}
if (str[i] == 'T')
{
posOfT = i; //i为T的位置
}
}
if (charMap['P'] == && charMap['T'] == && charMap['A'] != && charMap.size() == && posOfT - posOfP != && posOfP*(posOfT - posOfP - ) == str.size() - posOfT - )
{
return true;
}
else
{
return false;
}
} int main()
{
int n;
string str;
cin >> n; for (int i = ; i < n; ++i)
{
cin >> str;
bool flag = pass(str);
if (flag)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return ;
}
23行代码:
if (charMap['P'] == && charMap['T'] == && charMap['A'] != && charMap.size() == && posOfT - posOfP != && posOfP*(posOfT - posOfP - ) == str.size() - posOfT - )
charMap['P'] == && charMap['T'] == && charMap['A'] != && charMap.size() == 3 为了防止出现`PT` 或 P和T个数大于1的情况
而charMap.size() == 3 是为了防止出现除 PAT 之外的字母
posOfT - posOfP != 1 && posOfP*(posOfT - posOfP - 1) == str.size() - posOfT - 1)
1.假设给定字符串是AAPATAA,那么posOfT = 4, posOfP = 2, posOfT - posOfP = 2,所以,中间A的个数 = posOfT - posOfP - 1
2.假设给定字符串是PT,那么 posOfT - posOfP = 1,所以posOfT - posOfP != 1是用来排除PT这种中间没有A的情况的
3.假设给定字符串是AAPATAA,那么str.size() = 7, posOfT = 4, str.size() - posOfT - 1 = 后面A的个数
满足上述条件就返回 true
最新文章
- duplicate symbols for architecture arm64 after xCode 8.0 update
- AI PRO I 第4章
- CSS3线性渐变和径向渐变
- main函数读取jar包外部的配置文件properties
- MASM6.15汇编程序例子
- 分析与提取QQ木马盗号技术
- WebApp开发:ajax请求跨域问题的解决
- Spring MVC 解读——<;context:component-scan/>;
- Nginx优化—配置优化
- ListView中添加ScrollView只显示一两行的问题
- 视频(其他)下载+tomcat 配置编码+图片上传限制大小
- js正则表达式验证
- apache访问日志分析[转]
- 程序员修炼之道中所有tips总结
- 【AGC030F】Permutation and Minimum DP
- thinkphp5: 循环输出表格,并固定表格单元宽度(过长省略号)
- vi命令删除
- 单例模式实例&;多线程应用
- rcnn系列
- pyhton笔记(一):字符编码、变量