PAT_A1121#Damn Single

Source:

PAT A1121 Damn Single (25 分)

Description:

"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

Keys:

哈希映射

Code:

 /*

 Data: 2019-08-14 16:32:45

 Problem: PAT_A1121#Damn Single

 AC: 13:30

 题目大意：

 找出独自前往派对的人

 输入：

 第一行给出，伴侣数N<=5e4（意味着最多1e5个人）

 接下来N行，p1,p2

 接下来一行，出席人数M<=1e4

 接下来一行，给出M个id(5位)

 输出：

 独自参加派对的人数

 id递增

 基本思路：

 有一点需要注意下，id值可能为0，因此哈希表的初始值置-1就可以了；

 */

 #include<cstdio>

 #include<vector>

 #include<algorithm>

 using namespace std;

 const int M=1e5;

 int cp[M],mp[M]={};

 vector<int> pt,sg;

 int main()

 {

 #ifdef ONLINE_JUDGE

 #else

     freopen("Test.txt", "r", stdin);

 #endif // ONLINE_JUDGE

     int n,v1,v2;

     scanf("%d", &n);

     fill(cp,cp+M,-);

     for(int i=; i<n; i++)

     {

         scanf("%d%d", &v1,&v2);

         cp[v1]=v2;

         cp[v2]=v1;

     }

     scanf("%d", &n);

     while(n--)

     {

         scanf("%d", &v1);

         pt.push_back(v1);

         mp[v1]=;

     }

     for(int i=; i<pt.size(); i++)

         if(cp[pt[i]]==- || mp[cp[pt[i]]]==)

             sg.push_back(pt[i]);

     sort(sg.begin(),sg.end());

     printf("%d\n", sg.size());

     for(int i=; i<sg.size(); i++)

         printf("%05d%c", sg[i],i==sg.size()-?'\n':' ');

     return ;

 }

巴特西

PAT_A1121#Damn Single

Source:

Description:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Keys:

Code:

最新文章

热门文章