蒟蒻做这道题的时候,参考几位大佬的代码,写出来这个程序
#include <bits/stdc++.h>
using namespace std;
#define MOD 92083 //good hash table primes拉下来的好质数(雾
#define p 51787
int read()
{
int ans = 0, flag = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
flag = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
ans = (ans << 1) + (ans << 3) + (ch ^ '0');
ch = getchar();
}
return flag > 0 ? ans : ~ans + 1;
};
#define read read()
struct HASH
{
int value[MOD]; //哈希值 i 对应的数为 value[i]
bool exist[MOD]; //判断哈希值为 i 的数是否出现过
int getHash(int val) //查询一个数对应的哈希值
{
int idx = (val % MOD + MOD) % MOD;
while (exist[idx] && value[idx] != val) // idx 位置处已经有数了,且不是 val
idx = (idx + p) % MOD;
return idx;
}
inline void clear() //数组清零
{
memset(value, 0, sizeof(value));
memset(exist, 0, sizeof(exist));
}
} Hash;
int t, n, x, idx, ans = 0;
int main()
{
t = read;
while (t--)
{
Hash.clear();
n = read;
while (n--)
{
x = read;
idx = Hash.getHash(x);
if (Hash.exist[idx]) //这个数之前出现过了
continue;
Hash.value[idx] = x;
Hash.exist[idx] = 1;
printf("%d ", x);
}
puts("");
}
return 0;
}
哈希最主要的函数是结构体里面的getHash
函数(莫要吐槽马蜂辣QAQ),其中MOD
和p
选取的是两个五位质数,本题可以AC。
然鹅做到这道题的加强版的时候,用这两个质数会出现蜜汁TLE(记录在这)。受那道题其他人代码的启发,我改用更大的质数(大约是原先的两倍),就AC了(记录在这)。
网上查过,有人说哈希表的装填因子一般控制在 0.7∼0.8 左右(链接),对于本题 5×104 的数据范围,MOD
取 92083 应该是足够了呀,为什么会在加强版数据里被卡呢?请问这些数据到底应该取多大比较合适呢?有没有大佬能给出一些可以用来 hack 的测试点数据的?
谢谢。