给定n个人和他们之间的朋友关系(x与y是朋友或不是朋友),问有多少对(x,y),使得对于任意的和x,y不同的k,x与k和y与k的朋友关系相同(同时和k是朋友或者同时和k不是朋友)(既通过好友关系检查某人是不是某人的小号233)
首先计算出每个人的全部朋友,然后算一个hash,如果两个人的hash相同,则认为他们满足条件。但是需要注意三点
- hash算法应该是对于朋友序列无序的
- 当两个人互相是朋友的时候,他们即使满足要求也会因为自己不在自己的朋友中而导致h两个人的hash不相等,所以需要算两次,一次朋友列表中不带自己,一次带自己。分别对应上述两种情况
- 要用双值hash防碰撞(说实话我还没见过哪个单值hash能不碰撞的orz)
以下是AC代码,这题虽然是过了但是用的时间大约是2400ms,时限是3000ms,剩的时间不多。看CF上的大佬们有人写的600ms的,简单看了一眼没太看明白orz。
#include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; #define debug(x) cout<<#x<<": "<<x<<endl #ifndef ONLINE_JUDGE const int MAXN = (int) 1e3 + 5; #endif #ifdef ONLINE_JUDGE const int MAXN=(int)1e6+5; #endif const int MOD = (int) 1e9 + 7; using ulg = unsigned long long; ulg power1[MAXN]; ulg power2[MAXN]; inline pair<ulg, ulg> get_hs(const vector<int> &v) { ulg hs1 = 0, hs2 = 0; for (int i = 0; i < v.size(); ++i) { hs1 = (hs1 + power1[v[i]]) % MOD; hs2 = (hs2 + power2[v[i]]) % MOD; } return {hs1, hs2}; } inline void init() { power1[0] = power2[0] = 1; for (int i = 1; i < MAXN; ++i) { power1[i] = power1[i - 1] * 23 % MOD; power2[i] = power2[i - 1] * 17 % MOD; } } int main() { init(); int n, m; scanf("%d%d", &n, &m); vector<vector<int>> pers(n + 2, vector<int>()); while (m--) { static int a, b; scanf("%d%d", &a, &b); pers[a].push_back(b); pers[b].push_back(a); } pair<ulg, ulg> occ_cnt[MAXN]; for (auto it = pers.begin() + 1; it != pers.end(); ++it) { auto hs = get_hs(*it); occ_cnt[it - pers.begin()] = hs; } ulg ans = 0; map<pair<ulg, ulg>, ulg> hs_cnt; for (int i = 1; i <= n; ++i) { if (hs_cnt.find(occ_cnt[i]) != hs_cnt.end()) { ++hs_cnt[occ_cnt[i]]; } else { hs_cnt.insert(make_pair(occ_cnt[i], 1)); } } for (auto it = hs_cnt.begin(); it != hs_cnt.end(); ++it) { //debug(it->first), debug(it->second), debug(' '); if (it->second > 1) { ans += (it->second - 1) * it->second >> 1; } } hs_cnt.clear(); for (int i = 1; i <= n; ++i) { occ_cnt[i] = make_pair((occ_cnt[i].first + power1[i]) % MOD, (occ_cnt[i].second + power2[i]) % MOD); } for (int i = 1; i <= n; ++i) { if (hs_cnt.find(occ_cnt[i]) != hs_cnt.end()) { ++hs_cnt[occ_cnt[i]]; } else { hs_cnt.insert(make_pair(occ_cnt[i], 1)); } } for (auto it = hs_cnt.begin(); it != hs_cnt.end(); ++it) { //debug(it->first), debug(it->second), debug(' '); if (it->second > 1) { ans += (it->second - 1) * it->second >> 1; } } cout << ans << endl; return 0; }
Comments | NOTHING