社区讨论
关于正确性及效率求问
P11615【模板】哈希表参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mhpi380o
- 此快照首次捕获于
- 2025/11/08 07:42 3 个月前
- 此快照最后确认于
- 2025/11/08 07:42 3 个月前
首先是正确性 只给出手写哈希表部分
CPPtypedef 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)];
}
};
我发现如果把这部分从
CPPstatic const ull s1=rng(),s2=rng(),s3=rng();
换成
CPPull 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 条回复,欢迎继续交流。
正在加载回复...