题解 P4305 【[JLOI2011]不重复数字】

题解 P4305 【[JLOI2011]不重复数字】

这题怎么又没有pascal题解呢~我来水一发

这题第一眼看到自然想到了桶，但数字这么大，在

32位有符号整数范围内那怎么办呢？

哈希！！！
于是我们对每个数字哈希后存进桶里不就行了吗？

显然如果这么简单，这就不会是到省选了

仔细观察题面会发现是32位

有符号
整数，所以会有负数！！！那怎么开桶呢？

pascal的数组上下界不像c++,pascal可以任意给定上界和下界(当然不能太大或太小)。

所以我们在开数组的时候把下界开到负就行了

uses math;
var
a:array[-30000010..30000010] of boolean;
i,j,m,k,l,p,n,t,x,y,xx:longint;
begin
readln(t);
for p:=1 to t do
begin
readln(n);
y:=maxlongint;
xx:=-maxlongint;
for i:=1 to n do
begin
read(x);
t:=x mod 300000007;//哈希使数字在-30000010..30000010内
if a[t]=false then
begin
a[t]:=true;
write(x,' ');//别忘了输出原数字而不是哈希后的数字
end;
xx:=max(xx,t);
y:=min(y,t);//一个优化，在初始化时候只初始化改过的最大值与最小值的区间内就好了
end;
writeln;
for i:=y to xx do a[i]:=false;//多组数据别忘了初始化
end;
end.