• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

hash

开发技术 开发技术 4小时前 3次浏览

1 利用一个随机数rand()对 每一个点 进行一个随机负值 利用 数的大小和 等等 来表示一些 关系 从而可以减少时间复杂度 和 思维难度;

要有4个rand()而且前面是 1ll 不然不行的。

1ll 很重要

例题:

hashhash

天作之合
Description

对于一张n个点,m条边的无向图,若对于点i,j,除i,j 外其他所有点要么都与i,j有边相连,要么都与i,j无边相连,那么i和j就被称作一对“天作之合”。请你求出“天作之合”有多少对。


Input
第一行有两个整数n,m。1≤n≤1000001≤m≤200000。

接下来m行,每行两个整数x,y,表示x和y之间有边相连。


Output
一行,一个整数,表示“天作之合”的数量。


Sample Input 1 

3 3
1 2
2 3
1 3
Sample Output 1

3

View Code

代码

hashhash

#include <bits/stdc++.h>
using namespace std;
#define ri register int 
#define ull unsigned long long 
#define M 100005

int n,m; 
ull val[M];
ull ar[M];
vector <int> p[M];
void yuchu()
{
    ull  ans=0;
    for(ri i=1;i<=n;i++)
    {
        val[i]=1ll*rand()*rand()*rand();// attention
        ans+=val[i];
    }
    //printf("%lldn",ans);
    
}
int main(){
    //freopen("D:\学习\C++\决赛\天作之合_丁一鹏\data\3.in","r",stdin);
    scanf("%d%d",&n,&m);
    yuchu();
    
    for(ri i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        p[a].push_back(b);
        p[b].push_back(a);
        ar[a]+=val[b];
        ar[b]+=val[a];
    }
    
    long long  ans =0;
    for(ri i=1;i<=n;i++)
    {
        for(ri j=0;j<p[i].size();j++)
        {
            int b=p[i][j];
            if(b<i) continue;
            if(ar[i]-val[b]==ar[b]-val[i])
            ans++;
        }
    }
    
    sort(ar+1,ar+1+n);
    int cent=0;
    for(ri i=2;i<=n;i++)
    {
        if(ar[i-1]==ar[i])
        {
            cent++;
            if(i==n)
            {
              cent++;
              ans+=(1ll*cent*(cent-1)/2);
            }
        }
        else
        {
            cent++;
            ans+=(1ll*cent*(cent-1)/2);
            cent=0;
        }
    }
    printf("%lldn",ans);
    return 0;
    
}

View Code

 


程序员灯塔
转载请注明原文链接:hash
喜欢 (0)