PAT 1139 First Contact C++版
PAT 1139 First Contact C++版
1.题意
给出人数N，和关系数M。最后给出查询的数K，让你求出待查询的俩个人该如何处成CP。
处CP有规则：
- 如果A和B想成为异性cp，那么会分别找A最好的朋友C【C和A同性】 和B最好的朋友D【D和B同性】进行沟通，现在求的就是这种
C-D的朋友数。 - 如果A和B想成为同性cp，那么会分别找A最好的朋友C和B最好的朋友D进行沟通，现在求的就是这种
C-D的朋友数。【C和D都必须和A,B同性】
2.分析
这题是比较简单的模拟题，我最开始的思路是：
- step1:用一个
G[maxn][maxn]标记两个人之间是否是存在好友关系 - step2:用一个
isGirl[maxn]标记这个人是否是女生 - step3:用一个
vector<int> fre[maxn];存储好友关系 - step4:针对每次查询，用
vector<int> s1[maxn]用于标记查询当前查询的人的同性或者异性好友。 - step5:匹配好友并输出。
3.代码
3.1 代码
#include<cstdio>
#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
#include<iomanip>
#include<cmath>
#define maxn 10000
#define INF 0x3ffffff
using namespace std;
struct Result{
int f1,f2;
};
int N,M;
int isGirl[maxn];//用于标记是否是女生
vector<int> fre[maxn];//用于存储好友关系
int G[maxn][maxn];//定义一个图，用于存储是否有关系
Result res[INF];
int cmp(Result r1,Result r2){
if(r1.f1 == r2.f1) return r1.f2 < r2.f2;
return r1.f1 < r2.f1;
}
void addOppFreind(vector<int> &v,int que,int gender){//异性
int temp;
for(int j = 0;j< fre[abs(que)].size();j++){//找出其所有的好友
temp = fre[abs(que)][j];
if( isGirl[temp] == gender ) {//说明朋友也是女生
v.push_back(temp);//加入到其中
}
}
}
void addSameFreind(vector<int> &v,int que1,int que2,int gender){//同性
int temp;
for(int j = 0;j< fre[abs(que1)].size();j++){//找出其所有的好友
temp = fre[abs(que1)][j];
if( isGirl[temp] == gender && temp!=que2 ) {//说明朋友也是女生
v.push_back(temp);//加入到其中
}
}
}
int main(){
fill(isGirl,isGirl+maxn,0);//初始化为0
cin >> N >>M;
int i,j;
vector<int> s1[maxn] ,s2[maxn];//表示两个好友的关系列表
int ver1,ver2;
for(i= 0;i< M;i++){
cin >> ver1 >> ver2;
if(ver1<0) isGirl[abs(ver1)] = 1;//标记为女生
if(ver2<0) isGirl[abs(ver2)] = 1;
G[abs(ver1)][abs(ver2)] = 1;//用于表示这两个顶点有边
G[abs(ver2)][abs(ver1)] = 1;
fre[abs(ver1)].push_back(abs(ver2));//将其放入到好友列表
fre[abs(ver2)].push_back(abs(ver1));
}
int que1,que2;
int K;//查询次数
cin >> K;
while( K-- ){
cin >> que1 >> que2;
if( (que1<0 && que2>0) || (que1>0 && que2<0) ){//说明两者异性
if( que1<0 ){//说明que1是女生
if(s1[abs(que1)].size()==0) addOppFreind(s1[abs(que1)],que1,1);
}
else{//说明这个人是男生
if(s1[abs(que1)].size()==0) addOppFreind(s1[abs(que1)],que1,0);
}
if(que2<0){//说明que2是女生
if(s2[abs(que2)].size()==0) addOppFreind(s2[abs(que2)],que2,1);
}
else{//说明que2是男生
if(s2[abs(que2)].size()==0) addOppFreind(s2[abs(que2)],que2,0);
}
}
else{//说明两者同性
if(que1 < 0){//为女
if(s1[abs(que1)].size()==0) addSameFreind(s1[abs(que1)],que1,que2,1);
if(s2[abs(que2)].size()==0) addSameFreind(s2[abs(que2)],que2,que1,1);
}
else{//男生
if(s1[abs(que1)].size()==0) addSameFreind(s1[abs(que1)],que1,que2,0);
if(s2[abs(que2)].size()==0) addSameFreind(s2[abs(que2)],que2,que1,0);
}
}
//开始匹配好友
int count = 0;
set<int> cnt;
for(i = 0;i < s1[abs(que1)].size();i++){
for(j = 0;j< s2[abs(que2)].size();j++){
if(G[ s1[abs(que1)][i] ][ s2[abs(que2)][j] ] == 1 ){//ok
int minVal = min(s1[abs(que1)][i],s2[abs(que2)][j]);//找出最小值
int maxVal = max(s1[abs(que1)][i],s2[abs(que2)][j]);
int val = 10000 * maxVal + minVal;
if(cnt.find(val) == cnt.end()) {//说明没找到
cnt.insert(val);
res[count].f1 = s1[abs(que1)][i];
res[count].f2 = s2[abs(que2)][j];
count ++;
}
}
}
}
cout << count<<"\n";
sort(res,res+count,cmp);
for(i = 0;i< count;i++){
cout<<setfill('0')<<setw(4)<<res[i].f1<<" ";
cout<<setfill('0')<<setw(4)<<res[i].f2<<endl;
}
}
}
但是上面的代码存在一个问题，在交代码的时候得到如下的结果：
有三个测试用例无法通过的原因是：
- 【0000和-0000的区别】
- 上面这个问题导致在
if(s2[abs(que2)].size()==0) addSameFreind(s2[abs(que2)],que2,que1,0);判断中出现问题，于是会有三个测试用例过不了 - 最后一个测试用例超时
3.2 主要问题
上述的代码主要有如下几个问题：
- 我对不同的性别做了一个判断，导致有很多重复的代码。这是一个可以改进的地方，针对题目的叙述，可以得知：同学只能找同性的朋友作为红娘，所以可以修改成：使用一个
map<int,vector<int>> v;来保存同性好友 - 但是我们需要判断不同的好友之间是否是好友，所以可以修改成：需要用一个
map<int,vector<int>> arr;去保存全部好友关系
3.3
在修改之后，得到的代码如下：
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
map<int,vector<int>> v;//同性好友
map<int,vector<int>> arr;//全部好友
struct people
{
int x,y;
people(int x,int y):x(x),y(y){}
};
void search(vector<people> &ans, int a,int b)
{
for(int i = 0; i < v[a].size(); i++)//a的同性好友
{
for(int j = 0; j < v[b].size(); j++)//b的同性好友
{
if(v[a][i] == b || v[b][j] == a || v[a][i] == v[b][j]) continue;
//如果能在arr中找到 v[b][j]，则说明是好友关系，则放入到ans中
if( find( arr[v[a][i]].begin(), arr[v[a][i]].end(), v[b][j] ) != arr[v[a][i]].end() )
ans.push_back(people(v[a][i],v[b][j]));
}
}
}
bool cmp(people a,people b)
{
if(a.x != b.x)
return a.x < b.x;
else
return a.y < b.y;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 0; i < m; i++)
{
string a,b;
cin>>a>>b;
if(a.size() == b.size())//same gender
{
v[abs(stoi(a))].push_back(abs(stoi(b)));
v[abs(stoi(b))].push_back(abs(stoi(a)));
}
arr[abs(stoi(a))].push_back(abs(stoi(b)));
arr[abs(stoi(b))].push_back(abs(stoi(a)));
}
int k;
cin>>k;
while(k--)
{
int a,b;
cin>>a>>b;
vector<people> ans;
search(ans,abs(a),abs(b));
printf("%d\n",ans.size());
sort(ans.begin(),ans.end(),cmp);
for(auto w:ans)
{
printf("%04d %04d\n",w.x,w.y);
}
}
return 0;
}
4.测试用例
10 18
-2001 1001
-2002 -2001
1004 1001
-2004 -2001
-2003 1005
1005 -2001
1001 -2003
1002 1001
1002 -2004
-2004 1001
1003 -2002
-2003 1003
1004 -2002
-2001 -2003
1001 1003
1003 -2001
1002 -2001
-2002 -2003
2
1001 -2001
-2002 -2003
10 18
-2001 1001
-2002 -2001
1004 1001
-2004 -2001
-2003 1005
1005 -2001
1001 -2003
1002 1001
1002 -2004
-2004 1001
1003 -2002
-2003 1003
1004 -2002
-2001 -2003
1001 1003
1003 -2001
1002 -2001
-2002 -2003
5
1001 -2001
-2003 1001
1005 -2001
-2002 -2004
1111 -2003
4 5
1001 1002
1001 1003
1001 1004
1002 1003
1002 1004
1
1001 1004
4 6
1003 1004
1001 1002
1001 1003
1001 1004
1002 1003
1002 1004
1
1001 1004
6 6
1003 1004
1001 1002
1001 1003
1001 1004
1002 1003
1111 1004
2
1111 1114
1111 1004
4 6
1003 1004
1001 1002
1001 1003
1001 1004
1002 1003
1002 1004
2
1001 1004
1002 1004
4 6
1003 1004
1001 1002
1001 1003
1001 1004
1002 1003
1002 1004
1
1002 1004
4 5
-1001 -1002
-1001 -1003
-1001 -1004
-1002 -1003
-1002 -1004
1
-1001 -1004
10 18
-2001 1001
-2002 -2001
1004 1001
-2004 -2001
-2003 1005
1005 -2001
1001 -2003
1002 1001
1002 -2004
-2004 1001
1003 -2002
-2003 1003
1004 -2002
-2001 -2003
1001 1003
1003 -2001
1002 -2001
-2002 -2003
2
1001 -2001
1001 -2001