链接

[https://vjudge.net/contest/293343#problem/B]

题意

就是n男m女。然后给出他们喜欢那些人

再给出q次询问

每次参加party的人

让你找出某个人满足喜欢在场的所有人而且在场所有人都不喜欢他

如果不存在输出0；

分析

首先这题目的样例是给出一个信息。就是他们可以搞基同性恋

就直接模拟就好了。关键怎样模拟使得更高效，就是查找更高效

你得保存每个人喜欢的人。直接把名字映射成数字就好了

map<string,int> 名字对应的数字

vector a[] 为啥不用vector a[] 用来保存每个人喜欢的人

他喜欢的人还没map过就gg了

下面为了更方便地查找你得

在把喜欢的关系映射一下、

map < pair<int,int>,int > P

后面舞会就查找了

给两份代码 一份是MLE的

具体看代码吧

代码

MLE

#include<bits/stdc++.h>

using namespace std;

#define ll long long

map<string,int> ma;

map<int,string> is;

vector<string> ve[70000];

map<pair<int,int>,int > mp;

int pa[70000];

int main(){

	int t,m,n,k,q;

	scanf("%d",&t);

	while(t--){

		scanf("%d%d%d",&n,&m,&q);

		for(int i=0;i<n+m;i++){

			ve[i].clear();

			string l,bl;

			cin>>l;

			scanf("%d",&k);

			ma[l]=i,is[i]=l;

			//cout<<"i "<<i<<endl;

			for(int j=0;j<k;j++)

			{

				cin>>bl;

				ve[i].push_back(bl);

			}

		}

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

		for(int j=0;j<ve[i].size();j++)

		 mp[make_pair(i,ma[ve[i][j]])]=1;

		while(q--){

			scanf("%d",&k);  string s;

		  for(int i=0;i<k;i++)

		  {

		  	cin>>s;

		  	pa[i]=ma[s];

		  }

		  bool flag;

		  for(int i=0;i<k;i++){

		  	 flag=1;

		  	 for(int j=0;j<k;j++){

		  	 	 if(i!=j){

		  	 	 	  if(mp[make_pair(pa[i],pa[j])]==0||mp[make_pair(pa[j],pa[i])]==1){

		  	 	 	  	flag=0;

		  	 	 	  	break;

						  }

					}

			   }

			   if(flag)  {

			   	printf("1 ");

			   	cout<<is[pa[i]]<<"\n";

			   	break;

			   }

		  }

		  if(!flag) puts("0");

		}

		cout<<endl;

	}

	return 0;

}

AC代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

map<string,int> ma;

map<int,string> is;

vector<string> ve[70000];

map<pair<int,int>,int > mp;

string str[70000];

int pa[70000];

int main(){

	int t,m,n,k,q;

	scanf("%d",&t);

	while(t--){

		scanf("%d%d%d",&n,&m,&q);

		mp.clear();

        ma.clear();

		for(int i=0;i<n+m;i++){

			ve[i].clear();

			string l,bl;

			cin>>l;

			scanf("%d",&k);

			ma[l]=i;

			for(int j=0;j<k;j++)

			{

				cin>>bl;

				ve[i].push_back(bl);

			}

		}

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

		for(int j=0;j<ve[i].size();j++)

		 mp[make_pair(i,ma[ve[i][j]])]=1;

		while(q--){

			scanf("%d",&k);  string s;

		  for(int i=0;i<k;i++)

		  {

		  	cin>>str[i];

		  	pa[i]=ma[str[i]];

		  }

		  bool flag;

		  for(int i=0;i<k;i++){

		  	 flag=1;

		  	 for(int j=0;j<k;j++){

		  	 	 if(i!=j){

		  	 	 	  if(mp[make_pair(pa[i],pa[j])]==0||mp[make_pair(pa[j],pa[i])]==1){

		  	 	 	  	flag=0;

		  	 	 	  	break;

						  }

					}

			   }

			   if(flag)  {

			   	cout<<1<<" "<<str[i]<<"\n";

			   	break;

			   }

		  }

		  if(!flag) puts("0");

		}

		puts("");

	}

	return 0;

}