生活随笔
收集整理的這篇文章主要介紹了
1139 First Contact (30 分)【难度: 一般 / 知识点: 模拟】
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
https://pintia.cn/problem-sets/994805342720868352/problems/994805344776077312
難倒是不難，但是有坑，例如-0000，0000故我們還是得用字符串來讀入。
這里的話需要離散化一下，將字符串映射到一個值，這樣的話可以直接用鄰接矩陣來存邊。
#include<bits/stdc++.h>
using namespace std
;
vector
<int>boys
,girls
;
unordered_map
<string
,int>hush
;
unordered_map
<int,string
>val
;
int n
,m
,k
,idx
;
int g
[1005][1005];
int get(string x
)
{if(hush
.count(x
)==0) hush
[x
]=++idx
;val
[hush
[x
]]=x
;return hush
[x
];
}
void solve(string a
,string b
)
{vector
<int>ve1
,ve2
;vector
<pair
<int,int>>ans
;if(a
.size()==5) ve1
=girls
;else ve1
=boys
;if(b
.size()==5) ve2
=girls
;else ve2
=boys
;int a1
=get(a
),b1
=get(b
);for(int i
=0;i
<ve1
.size();i
++){for(int j
=0;j
<ve2
.size();j
++){int x
=ve1
[i
],y
=ve2
[j
];if(x
==a1
||x
==b1
||y
==a1
||y
==b1
) continue;if(g
[a1
][x
]&&g
[x
][y
]&&g
[y
][b1
])ans
.push_back({abs(stoi(val
[x
])),abs(stoi(val
[y
]))});}}cout
<<ans
.size()<<endl
;sort(ans
.begin(),ans
.end());for(int i
=0;i
<ans
.size();i
++) printf("%04d %04d\n",ans
[i
].first
,ans
[i
].second
);
}
int main(void)
{cin
>>n
>>m
;for(int i
=0;i
<m
;i
++){string a
,b
; cin
>>a
>>b
;int x
=get(a
),y
=get(b
);g
[x
][y
]=g
[y
][x
]=1;if(a
.size()==4) boys
.push_back(x
);else girls
.push_back(x
);if(b
.size()==4) boys
.push_back(y
);else girls
.push_back(y
);}sort(boys
.begin(),boys
.end());boys
.erase(unique(boys
.begin(), boys
.end()), boys
.end());sort(girls
.begin(),girls
.end());girls
.erase(unique(girls
.begin(), girls
.end()), girls
.end()); cin
>>k
;while(k
--){string a
,b
; cin
>>a
>>b
;solve(a
,b
);}return 0;
}
《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀
總結(jié)
以上是生活随笔為你收集整理的1139 First Contact (30 分)【难度: 一般 / 知识点: 模拟】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
