关于哈希会不会被卡
  • 板块学术版
  • 楼主chenbs
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/5/22 17:52
  • 上次更新2024/5/22 19:57:56
查看原帖
关于哈希会不会被卡
766573
chenbs楼主2024/5/22 17:52

我用单哈希竟然直接过了对称二叉树这道题,记录

我想问一下,我这个哈希代码,能不能构造一组数据卡掉它?

#include<bits/stdc++.h>
// 一些随便找的质数
#define p1 167772161ull
#define p2 469762049ull
#define p3 754974721ull
using namespace std;
typedef unsigned long long ull;
int n,v[1000005],l[1000005],r[1000005],size[1000005];
ull h[1000005],hinv[1000005];
int read() {
	char c=getchar();
	int n=0,f=1;
	while(c<48) {
		if(c == '-') f=-1;
		c=getchar();
	}
	while(c>47) n=n*10+(c^48), c=getchar();
	return n*f;
}
void dfs(int rt) {
	size[rt]=1;
	h[rt]=hinv[rt]=v[rt]*p3;
	if(~l[rt]) {
		dfs(l[rt]);
		size[rt]+=size[l[rt]];
		h[rt]+=h[l[rt]]*p1;
		hinv[rt]+=hinv[l[rt]]*p2;
	}
	if(~r[rt]) {
		dfs(r[rt]);
		size[rt]+=size[r[rt]];
		h[rt]+=h[r[rt]]*p2;
		hinv[rt]+=hinv[r[rt]]*p1;
	}
	h[rt] ^= 999999786000011449;
	hinv[rt] ^= 999999786000011449;
}
int main() {
	n=read();
	for(int i=1; i<=n; i++) v[i]=read();
	for(int i=1; i<=n; i++) l[i]=read(), r[i]=read();
	dfs(1);
	int ans=1;
	for(int i=1; i<=n; i++)
		if(h[l[i]] == hinv[r[i]])
			ans = max(ans,size[i]);
	cout<<ans;
}
2024/5/22 17:52
加载中...