BZOJ 4264 小C找朋友 哈希+脑子
2024-10-19 11:44:44
好吧我觉得是脑子,别人觉得是套路$qwq$
这道题相当于是求除了$u,v$两点互相连接,所连的点相同的点对$(u,v)$
我们首先每个点一个随机权值,对于$u$点记为$w[u]$,然后记与$u$点相连的点的异或和为$hsh[u]$
分类:
- 若$u,v$相连,则$u,v$是朋友满足$(hsh[u]^w[v])==(hsh[v]^w[u])$;
- 若$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[<<],*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=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
}using Fread::g;
const int N=;
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();
for(R i=;i<=n;++i) vl[i]=(ull)rand()*rand()*rand()*rand();
for(R i=,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=;i<=m;++i) ans+=(int)((hsh[e[i].fr]^vl[e[i].sc])==(hsh[e[i].sc]^vl[e[i].fr]));
sort(hsh+,hsh+n+); R cnt=; for(R i=;i<=n;++i) {
++cnt; if(i==n||hsh[i]!=hsh[i+]) ans+=(ll)cnt*(cnt-)/,cnt=;
} printf("%lld",ans);
}
2019.06.10
最新文章
- Get sdcard directory by adb
- 团队开发——冲刺1.b
- SVM之SMO最小序列
- Flex 选项卡加载方式简介
- URAL1017. Staircases
- Hacking Secret Ciphers with Python翻译序言
- linq to sql 博客集锦
- bootstrap 响应式导航条模板(含下拉菜单,弹出框)
- android 面试之listview
- centos 7 Chrony 集群同步时间
- Javascript高级编程学习笔记(16)—— 引用类型(5) Function类型
- Promise.all和Promise.race区别,和使用场景
- 【VMware vSphere】详解VDP安装步骤
- The Little Prince-12/10
- Linux用户创建/磁盘挂载相关命令
- [CC-XXOR]Chef and Easy Problem
- go语言之进阶篇字符串操作常用函数介绍
- C# 历史曲线控件 基于时间的曲线控件 可交互的高级曲线控件 HslControls曲线控件使用教程
- 学习GIT 版本控制的好去处 另GDB资料
- KBEngine 服务器端-loginapp-协议构建、解析执行详细介绍
热门文章
- bzoj1000~1025
- mysql调优参考笔记
- 【LeetCode】060. Permutation Sequence
- Springboot监控之一:SpringBoot四大神器之Actuator之2--spring boot健康检查对Redis的连接检查的调整
- JSP介绍(4)--- JSP 过滤器
- docker Get started part 4: Accessing your cluster cannot curl
- python 基础 操作文件和目录
- Ok6410裸机驱动学习(一)开发工具
- 27.【转载】挖洞技巧:如何绕过URL限制
- javascript 数组中出现的次数最多的元素