Steven_Meng's Blog

传送门

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

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

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

#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");
    }
}