「BZOJ2761」[JLOI2011] 不重复数字
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
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
1 2 3 4 5 6
HINT
对于30%的数据，1 <= N <= 100，给出的数不大于100，均为非负整数；
对于50%的数据，1 <= N <= 10000，给出的数不大于10000，均为非负整数；
对于100%的数据，1 <= N <= 50000，给出的数在32位有符号整数范围内。
2014.2.18
我会说sort就没了么。。。
好吧用来练习平衡树
2014.11.7
我发现我基本不会写字符串哈希。。。练习一下
treap
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; int T,n,f; int size,root; struct data{int l,r,v,rnd;}tr[50001]; void rturn(int &k){int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;k=t;} void lturn(int &k){int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;k=t;} void insert(int &k,int x) { if(k==0){size++;k=size;tr[k].v=x;tr[k].rnd=rand();return;} if(tr[k].v==x){f=1;return;} else if(x<tr[k].v){insert(tr[k].l,x);if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k);} else {insert(tr[k].r,x);if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k);} } int main() { scanf("%d",&T); while(T--) { memset(tr,0,sizeof(tr)); root=size=0;int x; scanf("%d%d",&n,&x); f=0;insert(root,x); if(!f)printf("%d",x); for(int i=1;i<n;i++) { scanf("%d",&x);f=0; insert(root,x); if(!f)printf(" %d",x); } printf("\n"); } return 0; } |
hash
|
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 49 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #define mod 58631 #define ll long long using namespace std; 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*10+ch-'0';ch=getchar();} return x*f; } int T,n,cnt; int last[58632],ans[50005]; struct data{int val,next;}a[50005]; void insert(int x,int val) { cnt++; a[cnt].next=last[x]; last[x]=cnt; a[cnt].val=val; } bool add(int x) { int sum=0,t=x; if(t<0)t=-t; while(t) { sum=(sum+(t%10))*(t%10)%mod; t/=10; } for(int i=last[sum];i;i=a[i].next) if(a[i].val==x)return 0; insert(sum,x); return 1; } int main() { T=read(); while(T--) { memset(last,0,sizeof(last)); cnt=0;ans[0]=0; n=read(); for(int i=1;i<=n;i++) { int x=read(); if(add(x))ans[++ans[0]]=x; } for(int i=1;i<ans[0];i++) printf("%d ",ans[i]); printf("%d\n",ans[ans[0]]); } return 0; } |
黄学长，请问sort做法是什么。。。
请问大神，您的 bzoj3224普通平衡树 程序中使用了C++的引用，请问root的值是否被改变？
删除时是会改变的