Skip to content

1065 单身狗

Statement

Metadata

  • 作者: CHEN, Yue
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 200 ms
  • 内存限制: 64 MB

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。

输入格式

输入第一行给出一个正整数 N（\le 50 000），是已知夫妻/伴侣的对数；随后 N 行，每行给出一对夫妻/伴侣——为方便起见，每人对应一个 ID 号，为 5 位数字（从 00000 到 99999），ID 间以空格分隔；之后给出一个正整数 M（\le 10 000），为参加派对的总人数；随后一行给出这 M 位客人的 ID，以空格分隔。题目保证无人重婚或脚踩两条船。

输出格式

首先第一行输出落单客人的总人数；随后第二行按 ID 递增顺序列出落单的客人。ID 间用 1 个空格分隔，行的首尾不得有多余空格。

输入样例 

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

输出样例 

5
10000 23333 44444 55555 88888

Solution

#include <bits/stdc++.h>
using namespace std;
#define MAXN 50000
string a[MAXN], b[MAXN];
int comp(string x, string y) {
    return x < y;
}
int main() {
    map<string, string> p;
    map<string, int> q;
    int N, i, j, k, t;
    cin >> N;
    string s1, s2;
    for (i = 0; i < N; i++) {
        cin >> s1 >> s2;
        p[s1] = s2;
        p[s2] = s1;
        q[s1] = 1;
        q[s2] = 1;
    }
    cin >> t;
    for (i = 0, j = 0, k = 0; i < t; i++) {
        cin >> s1;
        if (q[s1]) {
            q[s1] = 2;
            b[k++] = s1;
        } else
            a[j++] = s1;
    }
    for (i = 0; i < k; i++) {
        if (q[p[b[i]]] != 2)
            a[j++] = b[i];
    }
    sort(a, a + j, comp);
    cout << j << endl;
    if (j) {
        cout << a[0];
        for (i = 1; i < j; i++) cout << " " << a[i];
        cout << endl;
    }
}
Last update: May 4, 2022
Back to top