1 利用一个随机数rand()对 每一个点 进行一个随机负值 利用 数的大小和 等等 来表示一些 关系 从而可以减少时间复杂度 和 思维难度;
要有4个rand()而且前面是 1ll 不然不行的。
1ll 很重要
例题:
天作之合 Description 对于一张n个点,m条边的无向图,若对于点i,j,除i,j 外其他所有点要么都与i,j有边相连,要么都与i,j无边相连,那么i和j就被称作一对“天作之合”。请你求出“天作之合”有多少对。 Input 第一行有两个整数n,m。1≤n≤100000,1≤m≤200000。 接下来m行,每行两个整数x,y,表示x和y之间有边相连。 Output 一行,一个整数,表示“天作之合”的数量。 Sample Input 1 3 3 1 2 2 3 1 3 Sample Output 1 3View Code
代码
#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("%lld\n",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("%lld\n",ans); return 0; }View Code