[CodeForces-154C] Double Profiles 哈希

发布于 2019-04-16  4,570 次阅读


给定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;
}

终有一日, 仰望星空