BZOJ 2761: [JLOI2011]不重复数字 hash哈希

时间:2023-12-17 19:21:44

题目就不贴了

点我看题

题意:这题题意很简明,就是给一个序列,把序列里相同的删掉,然后输出,按原数列顺序。

思路:这题之前QZZ和ZN大神犇叫我去做,辣时还不会hash,就留着了。最近某夏令营学会了hash就回来写。

就是很简单的hash裸题。

我的hash就是把数字的每一位加起来然后累乘再膜。

从夏令营中涨了姿势,hash可以选择不判重,然后直接通过多hash的方法减少碰撞概率。

QAQ...刚开始以为3hash就够了,最后5hash才水过去。QAQ注意输出格式,行末没空格。

 const
base1=;
base2=;
base3=;
base4=;
base5=;
QZZ=; //膜神犇RP++
HR=;//膜神犇RP++
TJM=;//膜神犇RP++
ZN=;//膜神犇RP++
HJW=;//膜神犇RP++
var n:longint;
s:string;
num:longint;
a:array[..]of longint;
i,j,x,y,k:longint;
hash1,hash2,hash3,hash4,hash5:int64;
v1,v2,v3,v4,v5:array[..,..]of boolean;
bool:integer;
t,qaq:longint;
begin
read(t);
for qaq:= to t do
begin
read(n);
for i:= to do
for j:= to do
begin
v1[i,j]:=false;
v2[i,j]:=false;
v3[i,j]:=false;
v4[i,j]:=false;
v5[i,j]:=false;
end;
num:=;
for i:= to n do
begin
read(x);
if x>= then bool:= else
begin
bool:=;
x:=-x;
end;
str(x,s);
if bool= then x:=-x;
hash1:=;
hash2:=;
hash3:=;
hash4:=;
hash5:=;
for j:= to length(s) do
begin
hash1:=(hash1*base1+ord(s[j])) mod QZZ;
hash2:=(hash2*base2+ord(s[j])) mod HR;
hash3:=(hash3*base3+ord(s[j])) mod TJM;
hash4:=(hash4*base4+ord(s[j])) mod ZN;
hash5:=(hash5*base5+ord(s[j])) mod HJW;
end;
if (not v1[bool][hash1]) then
begin
v1[bool][hash1]:=true;
v2[bool][hash2]:=true;
v3[bool][hash3]:=true;
v4[bool][hash4]:=true;
v5[bool][hash5]:=true;
inc(num);
a[num]:=x;
end else
if (not v2[bool][hash2]) then
begin
v2[bool][hash2]:=true;
v3[bool][hash3]:=true;
v4[bool][hash4]:=true;
v5[bool][hash5]:=true;
inc(num);
a[num]:=x;
end else
if (not v3[bool][hash3]) then
begin
v3[bool][hash3]:=true;
v4[bool][hash4]:=true;
v5[bool][hash5]:=true;
inc(num);
a[num]:=x;
end else
if (not v4[bool][hash4]) then
begin
v4[bool][hash4]:=true;
v5[bool][hash5]:=true;
inc(num);
a[num]:=x;
end else
if (not v5[bool][hash5]) then
begin
v5[bool][hash5]:=true;
inc(num);
a[num]:=x;
end;
end;
for i:= to num- do
write(a[i],' ');
writeln(a[num]);
end;
end.

hash