Steven_MengのBlog

传送门

为什么要用平衡树呢,这道题不是蛤希裸题吗?

对于加进来的每个数,你暴力蛤希一下,加进一个$vector$里面,查找的时候也是暴力在$vector$里面查找。

经过试验,在模数为$223$时表现较好,为了避免毒瘤出题者卡你之类的,尽量避免用那些比较常见的模数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define MAXN 224
#define MOD 223
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
vector<int>G[MAXN];
inline int id(int x){
return (x%MOD+MOD)%MOD;
}
inline void Insert(int x){
G[id(x)].push_back(x);
}
inline bool Check(int x){
int pos=id(x);
for (register int i=0;i<G[pos].size();++i){
if (G[pos][i]==x) return true;
}
return false;
}
int main(){
int t=read();
while (t--){
for (register int i=0;i<MAXN;++i){
G[i].clear();
}
int n=read();
for (register int i=1;i<=n;++i){
int x=read();
if (!Check(x)){
Insert(x);
printf("%d ",x);
}
}
printf("\n");
}
}

 评论