CF154C Double Profiles 题解
思路解析
题目说的很明白,求有多少个无序点对 \((i,j)\),使得与 \(i\) 直接相连的点集与直接与 \(j\) 相连的点集完全相等。我们想到如果直接判断每个 \(i,j\) 肯定会超时,所以我们想把每一个与任意一点直接相连的点集进行压缩,可以想到使用字符串哈希的想法压缩一个点集。如果两点的点集哈希后相等,说明两点的点集也相等。
注意,需要特判点度为 \(0\) 的情况,以及需要分别讨论 \(i,j\) 之间有连边和没连边的情况,最后注意这题卡 map
。
code
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const ull p = 13;
const int N = 1e6 + 10;
int n, m, sz[N];
ull hs[N], pw[N];
signed main() {
cin >> n >> m;
pw[0] = 1; for(int i = 1; i <= n; i++) pw[i] = pw[i - 1] * p; //预处理
for(int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
sz[u]++; sz[v]++;
hs[u] += pw[v]; //字符串哈希
hs[v] += pw[u];
}
vector<ull> v, v1;
long long ans = 0;
for(int i = 1; i <= n; i++) {
if(sz[i] > 0) v.push_back(hs[i]); //记得特判入度为 0
else v.push_back(0);
v1.push_back(hs[i] + pw[i]);
}
sort(v.begin(), v.end()); sort(v1.begin(), v1.end());
for(int i = 0, j = i; i < v.size(); i = j) {
j = i; while(j < v.size() && v[j] == v[i]) j++;
ans += (long long)(j - i) * (long long)(j - i - 1) / 2;
}
for(int i = 0, j = i; i < v1.size(); i = j) {
j = i; while(j < v1.size() && v1[j] == v1[i]) j++;
ans += (long long)(j - i) * (long long)(j - i - 1) / 2;
}
cout << ans;
return 0;
}
标签:CF154C,pw,int,题解,long,点集,v1,hs,Double
From: https://www.cnblogs.com/2020luke/p/18138602