Description

給出N個數，要求把當中反復的去掉。僅僅保留第一次出現的數。 比如，給出的數為1 2 18 3 3 19 2 3 6 5 4。當中2和3有反復。去除后的結果為1 2 18 3 19 6 5 4。

Input

輸入第一行為正整數T，表示有T組數據。

接下來每組數據包含兩行，第一行為正整數N，表示有N個數。第二行為要去重的N個正整數。

Output

對于每組數據，輸出一行，為去重后剩下的數字，數字之間用一個空格隔開。

Sample Input

2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6

Sample Output

1 2 18 3 19 6 5 4
1 2 3 4 5 6

HINT

對于30%的數據，1 <= N <= 100，給出的數不大于100。均為非負整數；

對于50%的數據。1 <= N <= 10000，給出的數不大于10000，均為非負整數；

對于100%的數據，1 <= N <= 50000。給出的數在32位有符號整數范圍內。

提示:

因為數據量非常大，使用C++的同學請使用scanf和printf來進行輸入輸出操作，以免浪費不必要的時間。

題解：裸平衡樹。

#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int n,t,x; bool f; struct Node{Node*ch[2];int r,s,v;Node(int v):v(v){ch[0]=ch[1]=NULL;r=rand();}int cmp(int x){if (x==v) return -1;else return (x<v?

0:1); } }; Node* root; void rotata(Node* &o,int d) { Node*k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;o=k; } void insert(Node* &o,int x) { if (o==NULL) o=new Node(x); else { int d=o->cmp(x); if (d==-1) {f=false;return;} if (d!=-1) { insert(o->ch[d],x); if (o->ch[d]->r>o->r) rotata(o,d^1); } } } int main() { scanf("%d",&t); while(t--) { root=NULL; scanf("%d%d",&n,&x);f=true; insert(root,x); if (f) printf("%d",x); for (int i=1;i<n;i++) { f=true;scanf("%d",&x); insert(root,x); if (f) printf(" %d",x); } printf("\n"); } } 

總結

以上是生活随笔為你收集整理的【bzoj2761】【JLOI2011】【不反复数字】【平衡树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。