PAT甲级1050，1051解题报告

本文主要是介绍PAT甲级1050，1051解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

1050 String Subtraction （20 point(s)）

Given two strings S​1​​ and S​2​​, S=S​1​​−S​2​​ is defined to be the remaining string after taking all the characters in S​2​​ from S​1​​. Your task is simply to calculate S​1​​−S​2​​ for any given strings. However, it might not be that simple to do it fast.

Input Specification:

Each input file contains one test case. Each case consists of two lines which gives S​1​​ and S​2​​, respectively. The string lengths of both strings are no more than 10​4​​. It is guaranteed that all the characters are visible ASCII codes and white space, and a new line character signals the end of a string.

Output Specification:

For each test case, print S​1​​−S​2​​ in one line.

Sample Input:

They are students.
aeiou

Sample Output:

Thy r stdnts.

题目大意：给两个字符串，给出S1-S2，其中减法规则是把前者里面在后者字符串中存在的字符全部删去。

解题思路：However, it might not be that simple to do it fast.别被这句话吓到。。其实很水。

用set存一下第二个字符串，然后对第一个字符串进行遍历，直接用STL的find函数就行了，如果在集合里找得到，就不输出，找不到就输出。

代码如下：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<time.h>
#include<math.h>
#include<set>
#include<list>
#include<climits>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
set<char> m;
int main()
{string a, b;getline(cin, a);getline(cin, b);for (int i = 0; i < b.size(); i++)m.insert(b[i]);for (int i = 0; i < a.size(); i++) {if (find(m.begin(), m.end(), a[i])==m.end()) {cout << a[i];}}cout << endl;return 0;
}

1051 Pop Sequence （25 point(s)）

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K(the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.

Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
NO
YES
NO

题目大意：就是数据结构笔试经常做到的。。告诉你一个进堆栈的序列，然后给你一些出栈的序列，判断这种是否合法，注意一下这里的堆栈有大小限制，也就是堆栈满了就必须pop

解题思路：新建一个堆栈模拟一下，每次从1开始读，进栈之后判断，是不是超出限制了，如果超出了，不用继续，直接就是不合法的。如果没超出，那继续判断是不是和当前数组指针指向的数一致，如果一致，就pop，如此一直继续到不相等或者栈空即可。

代码如下：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<time.h>
#include<math.h>
#include<set>
#include<list>
#include<climits>
#include<queue>
#include<cstring>
#include<map>
#include<stack>
using namespace std;int main()
{int M, N, K;cin >> M >> N >> K;while (K--) {stack<int> tmp;vector<int> a;for (int i = 0; i < N; i++) {int c;cin >> c;a.push_back(c);}bool flag=true;int index = 0;for (int i = 1; i <= N; i++) {tmp.push(i);if (tmp.size() > M) {flag = false;break;}while(!tmp.empty() && tmp.top() == a[index]) {tmp.pop();index++;}}if (tmp.empty()&& flag == true) {cout << "YES" << endl;}else {cout << "NO" << endl;}}return 0;
}

 

这篇关于PAT甲级1050，1051解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---