前言

传送门

正文


参考题解

#include<iostream>
#include<algorithm>
using namespace std;
/* 题意： 给出n对夫妻的id，再给出m个id，求m个人中哪些人是单个人参加派对的。 （只要不是夫妻两同时出现在聚会，就算这个人是单独一个人） 思路：模拟+散列 1、根据题意需要记录哪些id是单身的，故使用single[i]表示单身者的id 2、需要记录配偶是谁，即couple[i]=j表示id为i的用户其配偶是id为j的用户，没有配偶的就设为-1 注意： 1、注意边界条件，当cnt=0是，不需输出任何id 2、注意补全前导0 */
const int maxID=1e6+10;
const int N=1e4+10;
int couple[maxID],ids[N],single[N];//couple表示夫妻关系的映射，ids保存聚会中所有人的id ,single[i]表示单身者的id 
bool inParts[maxID];//inParts[i]表示id为i的用户在聚会上 

int main(){
	fill(couple,couple+maxID,-1);
	fill(inParts,inParts+maxID,false);
	int n,m,a,b;
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d %d",&a,&b);
		couple[a]=b;
		couple[b]=a;
	}
	cin>>m;
	int id;
	for(int i=0;i<m;i++){
		cin>>id;
		inParts[id]=true;
		ids[i]=id;
	} 
	int cnt=0;
	for(int i=0,tempId;i<m;i++){
		tempId=ids[i];
		if(couple[tempId]==-1||inParts[couple[tempId]]==false){
			//tempId的用户是单身或者伴偶不在聚会上
			single[cnt++]=tempId; 
		} 
	} 
	sort(single,single+cnt);//从小到大排序 
	cout<<cnt<<endl;
	for(int i=0;i<cnt;i++){
		if(i!=0)cout<<" ";
		//注意前导0 
		printf("%05d",single[i]); 
	} 
	return 0;
}