首页 > 其他分享 >CF154C Double Profiles 题解

CF154C Double Profiles 题解

时间:2024-04-16 16:56:38浏览次数:29  
标签:CF154C pw int 题解 long 点集 v1 hs Double

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

相关文章

  • [题解] [CCPC陕西省赛2022 D题] Hash
    [CCPC陕西省赛2022D题]Hash题目描述给定一个字符串\(S\),按照如下方法获取\(S\)的哈希值://LanguageC++14longlongmod=5999993;longlonggethas(strings){longlongret=0;for(charc:s)ret=(ret*29+(c-'a'+1))%mod;returnret;}找到一个......
  • CF1097F Alex and a TV Show 题解
    题目链接点击打开链接题目解法很牛的套路啊!看到集合并,且只要求奇偶性的问题,第一个想到\(bitset\)\(1,2,4\)操作都是好维护的,关键是第\(3\)个操作看到$\gcd$,首先想到莫反令\(c_{x,i}\)为集合\(x\)中数\(i\)的出现次数则\(c_{x,i}=\sum\limits_{i|j}\sum\limit......
  • 如何写好一篇题解?
    为什么要写题解?首先要清楚知道一点,写题解不仅是帮助别人在做题遇到困难时指明方向,更是提升自己的最快途径。经常有人问我:“如何提升自己的程序设计能力”。我都会回答:“写题解”。写题解可以帮助你彻底掌握某一个知识点。无论一道题目是否是你独立写出来的,你都应该去尝试写题解......
  • 取胜 题解
    很厉害的题,记录下题意是随机一棵无根树,随一个根,每条边存在(能走通)的概率为\(p\),以根为起点,每次一方选择当前点的一个能走通的儿子走过去,问先手必胜的概率.容易发现可以当成有根树.用\(F(x)\)和\(G(x)\)表示必胜树和必败树的egf,有\[\begin{cases}F(x)=xe^{F(x)}\le......
  • 开机后mysql服务未启动问题解决
    问题:mysql的启动类型设置了自动,但是电脑开机后还是需要手动启动。 解决方法:一、Win+R快捷键弹出运行框 二、输入regedit后回车 三、地址栏内输入计算机\HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control后回车 四、找到Control入径后,新建一个名称为ServicesPipe......
  • [题解][2021-2022年度国际大学生程序设计竞赛第10届陕西省程序设计竞赛] Type The Str
    题目描述给定n个字符串,有以下几种操作:打出一个字符,花费1。删除一个字符,花费1。复制并打出一个之前打出过的字符串,花费k。求打出所有n个字符串的最小花费。(注意,打出顺序和字符串输入的顺序不必相同)题解显然,操作3需要算字符串的最长公共子序列来处理。这个问题可以转换为......
  • P4298 [CTSC2008] 祭祀 题解
    P4298[CTSC2008]祭祀题解给定DAG,求最长反链长度,最长反链方案,有多少个点可以成为反链上的点。Case1熟知Dilworth定理:偏序集的最长反链的长度等于最小链划分。因为偏序集有传递性,所以我们也需要对DAG做一遍传递闭包。这样可以套用Dilworth定理,最小链划分等于点数减......
  • [题解][2021-2022年度国际大学生程序设计竞赛第10届陕西省程序设计竞赛] Hash
    题目描述给定字符串T,要求求字符串S,满足以下条件:S是T的前缀S和T运行某段代码的哈希值相同(代码见下)T只包含小写字母S和T的长度差不超过50哈希代码://LanguageC++14longlongmod=5999993;longlonggethas(strings){longlongret=0;for(charc:s)ret=......
  • PGSQL 问题解决
    1服务无法启动 这里更改安装目录bin下面例如E:\WorkingSoftware\PostgreSql\16\bin更改权限,下面都改下 2  安装时提示database出错,就初始化下执行以下命令E:\WorkingSoftware\PostgreSql\16\bin\pg_ctl.exe-DE:\WorkingSoftware\PostgreSql\16\dat......
  • 2024小学组AHOI赛后题解
    观看建议调成浅色模式(右下角图标)写前扯一下这次省赛可谓是人才辈出啊。结束前一个半小时就交卷,可见这次考试的难度。后我问他们是不是很有信心AKXX:做了前两题,后两题崩溃了。。。好吧,其实第三题没那么难,不过AK的真没有,听说没有一个人做对。接下来带大家看看这几题。(记得,看......