BZOJ 4264 小C找朋友哈希+脑子

蔚落 2021-11-17 15:28 194阅读 0赞

好吧我觉得是脑子，别人觉得是套路$qwq$

--------------------

这道题相当于是求除了$u,v$两点互相连接，所连的点相同的点对$(u,v)$

我们首先每个点一个随机权值，对于$u$点记为$w\[u\]$，然后记与$u$点相连的点的异或和为$hsh\[u\]$

分类：

1.  若$u,v$相连，则$u,v$是朋友满足$(hsh\[u\]^w\[v\])==(hsh\[v\]^w\[u\])$；
2.  若$u,v$不相连，则$u,v$是朋友满足$hsh\[u\]==hsh\[v\]$；

对于第一种情况，直接枚举每条边上的两点就行了；对于第二种情况，先把$hsh$数组$sort$一遍，然后对于$hsh$相同的点来说，设共有$cnt$个点的$hsh\[u\]==c$，$c$是某定值，则答案个数是$C\_\{cnt\}^2$。

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<cctype>
    #include<cstdlib>
    #include<vector>
    #include<queue>
    #include<map>
    #include<set>
    #define fr first
    #define sc second
    #define ull unsigned long long
    #define ll long long
    #define R register int
    using namespace std;
    namespace Fread {
        static char B[1<<15],*S=B,*D=B;
        #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
        inline int g() {
            R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
            do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
        }
    }using Fread::g;
    const int N=1000010;
    pair<int,int> e[N];
    int n,m; ll ans;
    ull vl[N],hsh[N];
    signed main() {
    #ifdef JACK
        freopen("NOIPAK++.in","r",stdin);
    #endif
        n=g(),m=g(); srand(100023323);
        for(R i=1;i<=n;++i) vl[i]=(ull)rand()*rand()*rand()*rand();
        for(R i=1,u,v;i<=m;++i) u=e[i].fr=g(),v=e[i].sc=g(),hsh[u]^=vl[v],hsh[v]^=vl[u];
        for(R i=1;i<=m;++i) ans+=(int)((hsh[e[i].fr]^vl[e[i].sc])==(hsh[e[i].sc]^vl[e[i].fr]));
        sort(hsh+1,hsh+n+1); R cnt=0; for(R i=1;i<=n;++i) {
            ++cnt; if(i==n||hsh[i]!=hsh[i+1]) ans+=(ll)cnt*(cnt-1)/2,cnt=0;
        } printf("%lld",ans);
    }

--------------------

2019.06.10

转载于:https://www.cnblogs.com/Jackpei/p/11000339.html