社区讨论

关于正确性及效率求问

P11615【模板】哈希表参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mhpi380o
此快照首次捕获于
2025/11/08 07:42
3 个月前
此快照最后确认于
2025/11/08 07:42
3 个月前
查看原帖
首先是正确性 只给出手写哈希表部分
CPP
typedef unsigned long long ull;
constexpr int len=(1<<23);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct HashMap {
	inline ull F(ull x) {
		static const ull s1=rng(),s2=rng(),s3=rng();
		x+=s1;
		x=(x^(x>>33))*s2;
		x=(x^(x>>30))*s3;
		return x;
	}
	bitset<len+5>hav;
	ull key[len+5];
	ull value[len+5];
	int gt(const ull&x) {
		int i=F(x)&(len-1);
		while(hav[i]&&key[i]!=x)i=(i+1)&(len-1);
		hav[i]=1,key[i]=x;
		return i;
	}
	ull& operator[](const ull&x) {
		return value[gt(x)];
	}
};
我发现如果把这部分从
CPP
static const ull s1=rng(),s2=rng(),s3=rng();
换成
CPP
ull s1=rng(),s2=rng(),s3=rng();
就会导致哈希表出现问题 实测样例都过不去
输出哈希表更改过程如下
CPP
// static const ull s1=rng(),s2=rng(),s3=rng();
// cout<<x<<" "<<res[x]<<"->"<<y<<endl;

0 0->4
0 4->998244353
1000000000000000000 0->20120712
1000000000000000000 20120712->1000000000000000000
1000000000000000000 1000000000000000000->998244353
5000000000080482856
CPP
// ull s1=rng(),s2=rng(),s3=rng();
// cout<<x<<" "<<res[x]<<"->"<<y<<endl;

0 0->4
0 0->998244353
1000000000000000000 0->20120712
1000000000000000000 0->1000000000000000000
1000000000000000000 0->998244353
0
求大佬解答为什么一定要加static const,而且不加这个为什么会出问题
效率问题在我写一半的时候发现原因了

回复

3 条回复,欢迎继续交流。

正在加载回复...