P1097 统计数字

admin

https://www.luogu.com.cn/problem/P1097
题目描述
某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*10^9）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入输出格式
输入格式：
输入文件count.in包含n+1行；

第一行是整数n，表示自然数的个数；

第2~n+1每行一个自然数。

输出格式：
输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

输入输出样例
输入样例#1：
8
2
4
2
4
5
100
2
100

输出样例#1：
2 3
4 2
5 1
100 2
说明
40%的数据满足：1<=n<=1000

80%的数据满足：1<=n<=50000

100%的数据满足：1<=n<=200000，每个数均不超过1500 000 000（1.5*109）

NOIP 2007 提高第一题

黄煦喆

1. #include<iostream>
   
2. #include<map>
   
3. using namespace std;
   
4. int n,a;
   
5. map<int,int>m;
   
6. map<int,int>::iterator it;
   
7. int main()
   
8. {
   
9.     cin>>n;
   
10.     for(int i=1;i<=n;i++)
    
11.     {
    
12.         cin>>a;
    
13.         m[a]++;
    
14.     }
    
15.     for(it=m.begin();it!=m.end();it++)
    
16.         cout<<it->first<<' '<<it->second<<endl;
    
17.     return 0;
    
18. }
    

复制代码

admin

楼上的做法好巧妙呀。现在我们用这个题来训练BST，Scapegoat Tree，Treap，Splay，等

admin

先来抛转引玉，没有写好的裸的BST，测试数据很值得一看。

1. #include <iostream>
   
2. using namespace  std;
   
3. struct BSTnode
   
4. {
   
5.     int data;
   
6.     int cnt;
   
7.     BSTnode *l,*r;
   
8. } *T;
   
9. void BSTins(BSTnode *&bst, int x) ///把x插入到bst树中
   
10. {
    
11.     if (bst==NULL)   ///
    
12.     {
    
13.         BSTnode *p=new BSTnode;
    
14.         p->data=x;
    
15.         p->cnt=1;
    
16.         p->l=p->r=NULL;
    
17.         bst=p;
    
18.     }
    
19.     else if (x<bst->data) BSTins(bst->l,x);
    
20.     else if (x>bst->data) BSTins(bst->r,x);
    
21.     else if (x==bst->data) bst->cnt++;
    
22. }
    
23. void inorder(BSTnode *bst)
    
24. {
    
25.     if (bst!=NULL)
    
26.     {
    
27.         inorder(bst->l);
    
28.         cout<<bst->data<<' ';///<<bst->cnt<<'\t';
    
29.         inorder(bst->r);
    
30.     }
    
31. }
    
32. BSTnode * BSTfind(BSTnode * bst, int x)
    
33. {
    
34.     if (bst==NULL)  return NULL;
    
35.     else if (bst->data==x) return bst;
    
36.     else if (bst->data>x) return BSTfind(bst->l, x);
    
37.     else if (bst->data<x) return BSTfind(bst->r, x);
    
38. }
    
39. bool BSTdel(BSTnode * & bst,int x)
    
40. {
    
41.     if (bst==NULL) return 0;   ///没有这个数，删除未成功
    
42.     else if (bst->data>x) return BSTdel(bst->l,x);
    
43.     else if (bst->data<x) return BSTdel(bst->r,x);
    
44.     else  if (bst->cnt>1) {bst->cnt--;return 1;}  ///存在这个数，减1
    
45.     {
    
46.         ///BSTnode *p=bst;
    
47.         if (bst->l==NULL)   ///没有左子树就直接把右子树接上来
    
48.         {
    
49.             bst=bst->r;
    
50.             ///del(p);
    
51.             return 1;
    
52.         }
    
53.         else  if (bst->r==NULL)  ///没有右子树就直接把左子树接上来
    
54.         {
    
55.             bst=bst->l;
    
56.             ///del(p);
    
57.             return 1;
    
58.         }
    
59.         else
    
60.         {
    
61.             if (bst->l->r==NULL)   //左儿子没有右儿子
    
62.             {
    
63.                 bst->data=bst->l->data;
    
64.                 bst->cnt=bst->l->cnt;
    
65.                 return BSTdel(bst->l,bst->l->data);
    
66.             }
    
67.             else
    
68.             {  /// 这里有问题 没写好
    
69.                 BSTnode *p1=bst, *p2=bst->l;
    
70.                 while (p2->r==NULL)
    
71.                 {
    
72.                     p1=p2;
    
73.                     p2=p2->r;
    
74.                 }
    
75.                 bst->data=p2->data;
    
76.                 bst->cnt=p2->cnt;
    
77.                 return BSTdel(p1->r,p2->data);
    
78.             }
    
79.         }
    
80. 
    
81.     }
    
82. }
    
83. int main()
    
84. {
    
85.     int x;
    
86.     cin>>x;
    
87.     while (x>0)
    
88.     {
    
89.         BSTins(T,x);
    
90.         cin>>x;
    
91.     }
    
92.     inorder(T);cout<<endl;
    
93.     cin>>x;
    
94.     while (x>0)  /// 删除
    
95.     {
    
96.         BSTdel(T,x);
    
97.         inorder(T);
    
98.         cout<<endl;
    
99.         cin>>x;
    
100.     }
     
101.   return 0;
     
102. }
     
103. /*
     
104. 50 25 75 18 38 66 80 10 16 26 40 62 68 79 90 9 12 15 30 42 93 8 14 41 43 95 6 44 94 99 5 7 0
     
105. 
     
106. */

复制代码

Charleyxiao

输出的顺序错了，不知道为什么

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int SIZE=1e6+9;
   
4. const int inf=1<<30;
   
5. struct Treap{int l,r,val,dat,cnt,size;}a[SIZE];
   
6. int tot,root,n;
   
7. inline int New(int val){
   
8.         a[++tot].val=val;
   
9.         a[tot].dat=rand();
   
10.         a[tot].cnt=a[tot].size=1;
    
11.         return tot;
    
12. }
    
13. inline void Update(int p){
    
14.         a[p].size=a[a[p].l].size+a[a[p].r].size+a[p].cnt;
    
15. }
    
16. inline void Build(){
    
17.         New(-inf),New(inf);
    
18.         root=1,a[1].r=2;
    
19.         Update(root);
    
20. }
    
21. inline void zig(int &p){
    
22.         int q=a[p].l;
    
23.         a[p].l=a[q].r,a[q].r=p,p=q;
    
24.         Update(a[p].r),Update(p);
    
25. }
    
26. inline void zag(int &p){
    
27.         int q=a[p].r;
    
28.         a[p].r=a[q].l,a[q].l=p,p=q;
    
29.         Update(a[p].l),Update(p);
    
30. }
    
31. void Insert(int &p,int val){
    
32.         if(p==0) return p=New(val),void();
    
33.         if(val==a[p].val) return a[p].cnt++,Update(p),void();
    
34.         if(val<a[p].val){
    
35.                 Insert(a[p].l,val);
    
36.                 if(a[p].dat<a[a[p].l].dat) zig(p);
    
37.         }
    
38.         else{
    
39.                 Insert(a[p].r,val);
    
40.                 if(a[p].dat<a[a[p].r].dat) zag(p);
    
41.         }
    
42.         Update(p);
    
43. }
    
44. inline int GetPre(int val){
    
45.         int ans=1;
    
46.         int p=root;
    
47.         while(p){
    
48.                 if(val==a[p].val){
    
49.                         if(a[p].l>0){
    
50.                                 p=a[p].l;
    
51.                                 while(a[p].r>0) p=a[p].r;
    
52.                                 ans=p;
    
53.                         }
    
54.                         break;
    
55.                 }
    
56.                 if(a[p].val<val&&a[p].val>a[ans].val) ans=p;
    
57.                 p=(val<a[p].val)?a[p].l:a[p].r;
    
58.         }
    
59.         return a[ans].val;
    
60. }
    
61. inline int GetNext(int val){
    
62.         int ans=2;
    
63.         int p=root;
    
64.         while(p){
    
65.                 if(val==a[p].val){
    
66.                         if(a[p].r>0){
    
67.                                 p=a[p].r;
    
68.                                 while(a[p].l>0) p=a[p].l;
    
69.                                 ans=p;
    
70.                         }
    
71.                         break;
    
72.                 }
    
73.                 if(a[p].val>val&&a[p].val<a[ans].val) ans=p;
    
74.                 p=(val<a[p].val)?a[p].l:a[p].r;
    
75.         }
    
76.         return a[ans].val;
    
77. }
    
78. int GetRankByVal(int p,int val){
    
79.         if(p==0) return 0;
    
80.         if(val==a[p].val) return a[a[p].l].size+1;
    
81.         if(val<a[p].val) return GetRankByVal(a[p].l,val);
    
82.         return GetRankByVal(a[p].r,val)+a[a[p].l].size+a[p].cnt;
    
83. }
    
84. int GetValByRank(int p,int rank){
    
85.         if(p==0) return inf;
    
86.         if(a[a[p].l].size>=rank) return GetValByRank(a[p].l,rank);
    
87.         if(a[a[p].l].size+a[p].cnt>=rank) return a[p].val;
    
88.         return GetValByRank(a[p].r,rank-a[a[p].l].size-a[p].cnt);
    
89. }
    
90. void Remove(int &p,int val){
    
91.         if(p==0) return;
    
92.         if(val==a[p].val){
    
93.                 if(a[p].cnt>1){
    
94.                         a[p].cnt--,Update(p);
    
95.                         return;
    
96.                 }
    
97.                 if(a[p].l||a[p].r){
    
98.                         if(a[p].r==0||a[a[p].l].dat>a[a[p].r].dat) zig(p),Remove(a[p].r,val);
    
99.                         else zag(p),Remove(a[p].l,val);
    
100.                         Update(p);
     
101.                 }
     
102.                 else p=0;
     
103.                 return;
     
104.         }
     
105.         (val<a[p].val)?Remove(a[p].l,val):Remove(a[p].r,val);
     
106.         Update(p);
     
107. }
     
108. void middle_traval(int x){
     
109.         if(x<=0||x>1500000000) return;
     
110.         cout<<a[x].val<<" "<<a[x].cnt<<'\n';
     
111.         middle_traval(a[x].l);
     
112.         middle_traval(a[x].r);
     
113. }
     
114. int main(){
     
115.         srand((unsigned)time(NULL));
     
116.         ios::sync_with_stdio(0);
     
117.         Build();
     
118.         cin>>n;
     
119.         for(int i=1;i<=n;++i){
     
120.                 int x;
     
121.                 cin>>x;
     
122.                 Insert(root,x);
     
123.         }
     
124.         Remove(root,-inf),Remove(root,inf);
     
125.         middle_traval(root);
     
126. //        while(n--){
     
127. //                int opt,x;
     
128. //                cin>>opt>>x;
     
129. //                if(opt==1) Insert(root,x);
     
130. //                else if(opt==2) Remove(root,x);
     
131. //                else if(opt==3) cout<<GetRankByVal(root,x)-1<<'\n';
     
132. //                else if(opt==4) cout<<GetValByRank(root,x+1)<<'\n';
     
133. //                else if(opt==5) cout<<GetPre(x)<<'\n';
     
134. //                else if(opt==6) cout<<GetNext(x)<<'\n';
     
135. //        }
     
136.         return 0;
     
137. }

复制代码

admin

来一个裸的SPLAY的，用来训练SPALY的插入和旋转

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int inf=9999999;
   
4. const int N=100100;
   
5. struct node
   
6. {
   
7.         int val,cnt;
   
8.         int fa,s[2],sz;  ///s0s1左右儿子
   
9. } a[N];
   
10. int n, tot, root;
    
11. void ArrayPr()   /// 调试监视使用
    
12. {
    
13.         cout<<endl<<"  i ";
    
14.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
15.         cout<<endl<<"val ";
    
16.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
17.         cout<<endl<<"cnt ";
    
18.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
    
19.         cout<<endl<<" s0 ";
    
20.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
    
21.         cout<<endl<<" s1 ";
    
22.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
    
23.         cout<<endl<<" sz ";
    
24.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
25.         cout<<endl;
    
26. }
    
27. 
    
28. void BSTPr(int rt)   ///中序输出以rt为根的BST
    
29. {
    
30.         if (a[rt].s[0]>0)  BSTPr(a[rt].s[0]);
    
31.         cout<<a[rt].val<<' '<<a[rt].cnt<<endl;
    
32.         if (a[rt].s[1]>0)  BSTPr(a[rt].s[1]);
    
33. }
    
34. void pushup(int rt)   ///类似线段树网上调整
    
35. {
    
36.         int l=a[rt].s[0], r=a[rt].s[1];
    
37.         a[rt].sz=a[l].sz+a[r].sz+a[rt].cnt;
    
38. }
    
39. void LR(int rt)/// 左旋 因为有了fa，所以不需要传地址 但是也多了修改fa指针的操作
    
40. {
    
41.         ///cout<<"L\n";
    
42.         int x=a[rt].fa; ///x是rt的爸爸
    
43.         int y=a[x].fa;///y是x的爸爸 rt的爷爷
    
44.         int l=a[rt].s[0];
    
45.         a[x].s[1]=l;///rt的左儿子挂给x当右儿子（本来右儿子是rt）
    
46.         if(l!=0) a[l].fa=x;        //这个要注意空节点没有fa
    
47. 
    
48.         a[rt].fa=y; //rt取代了他的爸爸x
    
49.         a[rt].s[0]=x;//rt的原父节点x成为rt 的左儿子
    
50.         if(y!=0)
    
51.                 {
    
52.                         if(x==a[y].s[0])
    
53.                                 a[y].s[0]=rt;
    
54.                         else a[y].s[1]=rt;
    
55.                 }
    
56.         a[x].fa=rt;
    
57.         pushup(x),pushup(rt);
    
58. }
    
59. 
    
60. void RR(int rt) /// 同上 右旋
    
61. {
    
62.         ///cout<<"R\n";
    
63.         int x=a[rt].fa; ///x是rt的爸爸
    
64.         int y=a[x].fa;///y是x的爸爸 rt的爷爷
    
65.         int  r=a[x].s[0]=a[rt].s[1];
    
66.         if(r!=0) a[r].fa=x;
    
67. 
    
68.         a[rt].fa=y; //rt取代了他的爸爸x
    
69.         a[rt].s[1]=x;
    
70.         if(y!=0)
    
71.                 {
    
72.                         if(x==a[y].s[0])
    
73.                                 a[y].s[0]=rt;
    
74.                         else a[y].s[1]=rt;
    
75.                 }
    
76.         a[x].fa=rt;        pushup(x),pushup(rt);
    
77. }
    
78. 
    
79. void splay(int rt)//伸展操作: 6种情况
    
80. {
    
81.         int x,y;
    
82.         while(a[rt].fa!=0)//反复进行旋转，直至将x节点调整至根部为止
    
83.                 {
    
84.                         x=a[rt].fa;///rt的爸爸
    
85.                         y=a[x].fa;
    
86.                         if(y==0)//在x为根的情况下，若x在左儿子位置，则右旋；否则左旋
    
87.                                 {
    
88.                                         if(rt==a[x].s[0]) RR(rt);
    
89.                                         else LR(rt);
    
90.                                         break;
    
91.                                 }
    
92.                     
    
93.                         if(rt==a[x].s[0])//在x位于左位置的情况下，若x的父节点位于左位置，则分别
    
94.                                 //以x的父节点和x为基准两次右旋；否则以x为基准右旋和左旋
    
95.                                 {
    
96.                                         if(x==a[y].s[0])  ///LLL
    
97.                                                 {
    
98.                                                         RR(x);
    
99.                                                         RR(rt);
    
100.                                                 }
     
101.                                         else  ///LLR
     
102.                                                 {
     
103.                                                         RR(rt);
     
104.                                                         LR(rt);
     
105.                                                 }
     
106.                                 }
     
107.                         else
     
108.                                 {
     
109.                                         if(x==a[y].s[1]) ///RRR
     
110.                                                 {
     
111.                                                         LR(x);
     
112.                                                         LR(rt);
     
113.                                                 }
     
114.                                         else
     
115.                                                 {
     
116.                                                         LR(rt);
     
117.                                                         RR(rt);
     
118.                                                 }
     
119.                                 }
     
120.                 }
     
121.         root=rt;//新根
     
122.         //cout<<rt<<endl;
     
123. }
     
124. void Ins(int rt, int x)   /// 在rt子树中插入x
     
125. {
     
126.         if(rt==0)  /// 新树
     
127.                 {
     
128.                         tot=root=1;
     
129.                         a[1].fa=a[1].s[0]=a[1].s[1]=0;
     
130.                         a[1].val=x;
     
131.                         a[1].cnt=1;
     
132.                 }
     
133.         else if(a[rt].val==x) a[rt].cnt++;
     
134.         else if(a[rt].val<x)
     
135.                 {
     
136.                         if (a[rt].s[1]==0)
     
137.                                 {
     
138.                                         a[rt].s[1]=++tot;
     
139.                                         a[tot].s[0]=a[tot].s[1]=0;
     
140.                                         a[tot].val=x;
     
141.                                         a[tot].fa=rt;
     
142.                                         a[tot].cnt=1;
     
143.                                         splay(tot);
     
144.                                 }
     
145.                         else
     
146.                                 Ins(a[rt].s[1],x);
     
147.                 }
     
148.         else if(a[rt].val>x)
     
149.                 {
     
150.                         if (a[rt].s[0]==0)
     
151.                                 {
     
152.                                         a[rt].s[0]=++tot;
     
153.                                         a[tot].s[0]=a[tot].s[1]=0;
     
154.                                         a[tot].val=x;
     
155.                                         a[tot].fa=rt;
     
156.                                         a[tot].cnt=1;
     
157.                                         splay(tot);
     
158.                                 }
     
159.                         else
     
160.                                 Ins(a[rt].s[0], x);
     
161.                 }
     
162. 
     
163. }
     
164. 
     
165. int main()
     
166. {
     
167.         cin>>n;
     
168.         while(n--)
     
169.                 {
     
170.                         int x;
     
171.                         cin>>x;
     
172.                         Ins(root,x);
     
173. 
     
174.                 }
     
175.         BSTPr(root);
     
176.         return 0;
     
177. }
     

复制代码

admin

第110行左右的输出语句顺序有问题。