PAT甲级1121,1124解题报告

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

1121 Damn Single （25 point(s)）

"Damn Single (单身狗)" is the Chinese nickname for someone who is being single. You are supposed to find those who are alone in a big party, so they can be taken care of.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤50,000), the total number of couples. Then N lines of the couples follow, each gives a couple of ID's which are 5-digit numbers (i.e. from 00000 to 99999). After the list of couples, there is a positive integer M (≤ 10,000) followed by M ID's of the party guests. The numbers are separated by spaces. It is guaranteed that nobody is having bigamous marriage (重婚) or dangling with more than one companion.

Output Specification:

First print in a line the total number of lonely guests. Then in the next line, print their ID's in increasing order. The numbers must be separated by exactly 1 space, and there must be no extra space at the end of the line.

Sample Input:

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

Sample Output:

5
10000 23333 44444 55555 88888

题目大意：把一个数组里的成对的全部去掉把单身狗留下

解题思路：存个双向的哈希表，遍历数组标记每个数组成对次数，如果下标为2，那就不是单身狗。

#include<iostream>
#include<string.h>
#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>
#include<string>
using namespace std;
map<int, int> a;
vector<int> res;
vector<int> cur;
map<int, int> b;
int main()
{int N;scanf("%d", &N);for (int i = 0; i < N; i++) {int x,y;scanf("%d %d", &x,&y);a[x] = y;a[y] = x;}int T;scanf("%d", &T);for (int i = 0; i < T; i++) {int x;scanf("%d", &x);cur.push_back(x);b[x]++;b[a[x]]++;}for (int i = 0; i < T; i++) {if (b[cur[i]] == 1)res.push_back(cur[i]);}sort(res.begin(), res.end());cout << res.size() << endl;for (int i = 0; i < res.size(); i++) {if (i != res.size() - 1) {printf("%05d ", res[i]);}elseprintf("%05d\n", res[i]);}return 0;
}

1124 Raffle for Weibo Followers （20 point(s)）

John got a full mark on PAT. He was so happy that he decided to hold a raffle（抽奖） for his followers on Weibo -- that is, he would select winners from every N followers who forwarded his post, and give away gifts. Now you are supposed to help him generate the list of winners.

Input Specification:

Each input file contains one test case. For each case, the first line gives three positive integers M (≤1000), N and S, being the total number of forwards, the skip number of winners, and the index of the first winner (the indices start from 1). Then M lines follow, each gives the nickname (a nonempty string of no more than 20 characters, with no white space or return) of a follower who has forwarded John's post.

Note: it is possible that someone would forward more than once, but no one can win more than once. Hence if the current candidate of a winner has won before, we must skip him/her and consider the next one.

Output Specification:

For each case, print the list of winners in the same order as in the input, each nickname occupies a line. If there is no winner yet, print Keep going... instead.

Sample Input 1:

9 3 2
Imgonnawin!
PickMe
PickMeMeMeee
LookHere
Imgonnawin!
TryAgainAgain
TryAgainAgain
Imgonnawin!
TryAgainAgain

Sample Output 1:

PickMe
Imgonnawin!
TryAgainAgain

Sample Input 2:

2 3 5
Imgonnawin!
PickMe

Sample Output 2:

Keep going...

题目大意：模拟微博抽奖。

解题思路：其实和队列类似吧，但实际不用队列做，基本上就按顺序模拟一下就好了

#include<iostream>
#include<string.h>
#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>
#include<string>
using namespace std;
vector<string> cur;
vector<string> res;
int main()
{int a, b, c;scanf("%d %d %d", &a, &b, &c);for (int i = 0; i < a; i++) {string tmp;cin >> tmp;cur.push_back(tmp);}if (a < c) {cout << "Keep going..." << endl;}else {for (int i = c-1; i < a;) {if (count(res.begin(),res.end(),cur[i])==0) {res.push_back(cur[i]);//cout << cur[i] << endl;i = i + b;}else {i = i + 1;}}for (int i = 0; i < res.size(); i++) {cout << res[i] << endl;}}return 0;
}

 

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

---