P4305 【[JLOI2011]不重复数字】

Rainbow_qwq · 2020-01-27 12:55:39 · 题解

P4305 [JLOI2011]不重复数字

今天早上看见 xht37 说加强了数据。然后 map/set 就被卡掉了。

但是 C++11 的 unordered_map 是哈希，能过！

unordered_map 的定义与用法都与 map 差不多，只不过是用Hash来存储的，判断是O(1)的。

而map判断是O(\log n)的。

代码：（不开O2也过了）

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
    char c=getchar();int x=0,f=1;
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=x*10+c-48;
    return x*f;
}
int T,n,x;
unordered_map<int,bool>s;//定义
void work()
{
    s.clear();//清空
    n=read();
    For(i,1,n){
        x=read();
        if(!s[x]){//没有的话，直接输出+标记掉。
            printf("%d ",x);
            s[x]=1;
        }
    }puts("");//换行
}
int main()
{
    T=read();
    while(T--)work();
    return 0;
}