Hello, 2020!（桶排序）

太过爱你忘了你带给我的痛 2022-11-30 01:25 6阅读 0赞

##### 题目背景 #####

时针与分针重合在「零」的那一霎那，嘀嗒声便宣告了新一年的到来。在过去的一年里，世事无常。屏幕面前的你可能不久前才听闻「OI」，也可能暂时地结束了竞赛生涯；可能在赛场上叱咤风云名列榜首，也可能独自承受着比赛失利的落寞。无论如何，过去仍旧是过去，将来依然是将来。以此题为开端，迎接你的 2020 吧！

##### 题目描述 #####

本场比赛有 n 名出题人，m 名选手。出题人从 1 至 n 依次标号，选手从 1 至 m 依次标号。比赛结束后选手的最终排名为 1 至 m 中其一，且互不相同。报名结束后，第 i 位出题人看了看报名列表，对其他出题人说：「我觉得只有这 kii 位选手有可能最终排名第一，他们分别是 ai,1,ai,2,…,ai,ki。其他人不可能最终排名第一。」你面前屏幕上的这道题的出题人通过时空隧道，预先得知了谁是最终排名第一的选手。出题人把这 n 位出题人的预测都告诉了你，还告诉你恰好只有 p 个出题人的预测是正确的。请你求出哪些选手可能最终获得第一名，并以从小到大的顺序依次输出这些选手的编号。

##### 输入格式 #####

从标准输入中读取数据。第一行，三个正整数 n,m,p，表示出题人数，选手数，与正确预测数。接下来 n 行，每行第一个非负整数 ki 表示第 i 位出题人预测可能最终排名第一的选手位数；接下来 ki 个正整数 ai,1,ai,2,…,ai,k，表示这位出题人预测可能最终排名第一的选手编号。

##### 输出格式 #####

输出数据至标准输出中。第一行，输出一个非负整数，表示可能最终获得第一名的选手个数。第二行，以从小到大的顺序依次输出这些选手的编号。输入输出

##### 样例输入 \#1 #####

4 3 2  
2 2 3  
1 1  
3 1 2 3  
2 1 3

##### 输出 \#1 #####

1  
2

#include<bits/stdc++.h>
    using namespace std;
    int c[1000001],t,s[1000001],sum,d;
    int main()
    { 
        int n,m,p;
        cin>>n>>m>>p;
        for(int i=0;i<n;i++)
        { 
      	scanf("%d",&t);
     	while(t--)
      	{ 
                scanf("%d",&d);
                ++c[d];
      	}
        }
        for(int i=1;i<=m;i++)
        {  
      	if(c[i]==p)
     	{ 
                s[sum]=i;
                ++sum;
      	}
        } 
        printf("%d\n",sum);
        sort(s,s+sum);
        for(int i=0;i<sum;i++)
        {  
      	printf("%d ",s[i]);
        } 
        printf("\n");
        return 0;
    }