bzoj 2761: [JLOI2011]不重复数字 (map||Treap)

链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2761

思路: map标记

实现代码:

#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
int main()
{
int t,n,x;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i = ;i <= n;i ++){
scanf("%d",&x);
mp[x]++;
if(mp[x]==) printf("%d ",x);
}
printf("\n");
mp.clear();
}
}

这道题也可以用平衡树写,虽然也很水/////

Treap写法:

实现代码:

#include<bits/stdc++.h>
using namespace std;
const int M = 1e5 +;
struct node{
int l,r,siz,cnt,wt,val;
}t[M];
int cnt,flag; void lt(int &k){
int tmp = t[k].r;
t[k].r = t[tmp].l;
t[tmp].l = k;
t[tmp].siz = t[k].siz;
t[k].siz = t[t[k].l].siz + t[t[k].r].siz + t[k].cnt;
k = tmp;
} void rt(int &k){
int tmp = t[k].l;
t[k].l = t[tmp].r;
t[tmp].r = k;
t[tmp].siz = t[k].siz;
t[k].siz = t[t[k].l].siz + t[t[k].r].siz + t[k].cnt;
k = tmp;
} void Insert(int &k,int num){
if(!k){
k = ++cnt;
t[k].wt = rand();
t[k].val = num;
t[k].cnt = t[k].siz = ;
return ;
}
++t[k].siz;
if(num == t[k].val){
++t[k].cnt;
flag = ;
return ;
}
if(num < t[k].val){
Insert(t[k].l,num);
if(t[t[k].l].wt < t[k].wt) rt(k);
}
else{
Insert(t[k].r,num);
if(t[t[k].r].wt < t[k].wt)
lt(k);
}
} int main()
{
int T,n,x,root;
scanf("%d",&T);
while(T--){
memset(t,,sizeof(t));
root = cnt = ;
scanf("%d",&n);
for(int i = ;i <= n;i ++){
cin>>x;
flag = ;
Insert(root,x);
if(!flag) printf("%d ",x);
}
printf("\n");
}
return ;
}
上一篇:angularJs项目实战!03:angularjs与其他类库的协作


下一篇:使用 ResponseBodyAdvice 拦截Controller方法默认返回参数,统一处理返回值/响应体