文章目錄

• • 題目分析
  • 題目鏈接

題目分析

來源：acwing

題目分析：

圖論模擬題。

給定暗戀的兩個人A 和B，需要尋找一對C 和D ，滿足:A和C是朋友，C和D是朋友，D和B是朋友。而且A、C同性別，B、D同性別。題目給的暗戀：可能是異性(男對女，或者女對男)，也可能是同性暗戀同性。

數(shù)據(jù)不大，枚舉即可。只要建好圖標(biāo)記好邊g[N][N]，然后直接暴力枚舉即可

for(auto c :a的同性別陣營 )for(auto d : b的同性別陣營)if( c != a && c != b && d != a && d != b && g[a][c] && g[c][d] && g[d][b] )res.push_back({c , d});

題目的難點之一在于給定的不是數(shù)字，而是字符串，因為0000 和 -0000表示男生 和女生，不能單純從數(shù)字上來看，所以用字符串來存，這樣的話，需要做一個從字符串到數(shù)字的映射，需要使用hash表。輸出的時候還需要輸出字符串（不需要輸出表示女生的負(fù)號），因此還需要數(shù)字和字符串的逆映射，需要不停地處理輸入輸出。

第二個難點是枚舉的時候需要按照性別枚舉，這時候男生和女生需要分別存。

STL語法點補(bǔ)充：
下面使用了vector的去重，使用方法erase() 和uniue().

vector<int> boys; boys.erase( unique(boys.begin(),boys.end()), boys.end() );

上面的代碼是對數(shù)組boys進(jìn)行刪除重復(fù)元素。

還用到了STL中的hash table unordered_map<string,int > mp;實現(xiàn)從字符串到數(shù)字的映射。使用方法count()判斷是否已經(jīng)映射過。如果mp.count(x) == 0表示還沒有映射過。

ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 310;int n, m; bool g[N][N]; string num[N]; unordered_map<string,int > mp; int id ; vector<int> boys, girls; int main(){cin >> n >> m;while(m--){string a, b;cin >> a >> b;string x =a ,y =b;if(x.size()==5) x =x.substr(1);if(y.size() ==5) y = y .substr(1);//沒出現(xiàn)過，映射成全新的數(shù)if(mp.count(x) == 0) mp[x] = ++id,num[id] = x;//原來的編號是什么if(mp.count(y) == 0) mp[y] = ++id, num[id] = y;int px= mp[x] ,py = mp[y];//之間有邊g[px][py] = g[py][px] = true;if(a[0] != '-') boys. push_back(px);else girls.push_back(px);if(b[0] != '-' ) boys. push_back(py);else girls.push_back(py);}sort(boys.begin(),boys.end());//刪除重復(fù)元素boys.erase(unique(boys.begin(),boys.end()), boys.end());sort(girls.begin(),girls.end());//刪除重復(fù)元素girls.erase(unique(girls.begin(),girls.end()), girls.end());int k ;cin >> k;//詢問while(k--){vector<pair<string,string>> res; //存結(jié)果string x, y;cin >> x >> y;//判斷是男孩還是女孩vector<int> p= boys, q = boys;if(x[0] == '-') p =girls, x = x. substr(1);if( y[0] == '-') q = girls, y = y.substr(1);int a = mp[x] ,b = mp[y];//圖的遍歷//找兩個點for(int c: p) //c從a的性別里找for(int d : q){ //d從b的性別里找if( c !=a && c !=b && d!= a && d!= b && g[a][c] && g[c][d] && g[d][b])res.push_back({num[c],num[d]});}cout<< res.size()<<endl;sort(res.begin(),res.end());for( auto p :res ) cout << p.first <<" "<< p.second <<endl;}}

題目鏈接

PAT甲級1139 First Contact (30 分)

總結(jié)

以上是生活随笔為你收集整理的PAT甲级1139 First Contact (30 分)：[C++题解] 图论、暴力枚举两个点、hash映射的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。