[pat1139]First Contact 前导零

First Contact

题意

给定一个图,图中的点只有男的点或者女的点。给定两个不同的点AB,问他们第一个点通过两个不同的点找到第二个点,并且A找到的点和A同性,B连接的点跟B同性,这样的点对有多少对。

题解

暴力枚举即可,找到所有相邻的同性点,之后同性点之间有连接就是一对点对。

  • wa点 前导零输出,-0000输入
  • 中间的点不能是两边的点,必须是不同的四个点

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
map<int,int> mx;
const int maxn = 3e2+10;
int vis[maxn][maxn];
int idx[maxn];
int gender[maxn];
void output(int x){
char ch[10];
ch[0] = '0';
ch[1] = '0';
ch[2] = '0';
ch[3] = '0';
ch[4] = '\0';
int cnt = 3;
while(x){
ch[cnt--] = (x%10)+'0';
x /= 10;
}
printf("%s",ch);
}
int trans(string x,int &sign){
int a = 0;
int sz = x.size();
if(x[0] == '-'){
rep(i,1,sz){
a += pow(10,4-i) * (x[i] - '0');
}
sign = 1;
}else{
rep(i,0,sz){
a += pow(10,3-i) * (x[i] - '0');
}
}
return a;
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
int n,m;
scanf("%d%d",&n,&m);
int cnt = 1;
rep(i,0,m){
string a,b; cin>>a>>b;
int x,y;
int sign1 = 0,sign2 = 0;
x = trans(a,sign1) ; y = trans(b,sign2);
if(mx[x] == 0){
mx[x] = cnt++;
if(sign1) gender[mx[x]] = 1;
idx[mx[x]] = x;
}
if(mx[y] == 0){
mx[y] = cnt++;
if(sign2) gender[mx[y]] = 1;
idx[mx[y]] = y;
}
int id1 = mx[x];
int id2 = mx[y];
vis[id1][id2] = vis[id2][id1] = 1;
}
int k;scanf("%d",&k);
rep(i,0,k){
int x,y; scanf("%d%d",&x,&y);
x = max(-1*x,x);
y = max(-1*y,y);
int id1 = mx[x]; int id2 = mx[y];
vector<int> xx;vector<int> yy;
if(id1 == 0 || id2 == 0){
puts("0");
continue;
}
rep(j,1,cnt+1)
if(j != id2 && vis[id1][j] && (gender[id1]^gender[j]) == 0)
xx.push_back(j);
rep(j,1,cnt+1)
if(j != id1 && vis[id2][j] && (gender[id2]^gender[j]) == 0)
yy.push_back(j);
vector<pair<int,int>> ans;
for(auto x:xx){
for(auto y:yy){
if(vis[x][y] == 1){
ans.push_back(make_pair(idx[x],idx[y]));
}
}
}
sort(ans.begin(),ans.end());
printf("%d\n",ans.size());
for(auto x:ans){
output(x.fi); printf(" "); output(x.se);
puts("");
//printf("%d %d\n",x.fi,x.se);
}
}
return 0;
}