STL与基础数据结构

内容参考书籍《算法竞赛入门到进阶》

1.vector。

　　数组是基本数据结构，有静态数组和动态数组，在比赛中如果空间足够，能用静态数组就用数组，在空间紧张的情况下可以使用STL的vector建立动态数组。

　　vector是STL的动态数组，在运行时能根据需要改变数组大小。vector容器是一个模板类，能存放任何类型的对象。

1 vector<int> a;//默认初始化,为空
2 vector<int> b(a);//用a定义b
3 vector<int> a(100);//a有100个值为0的元素
4 vector<int> a(100,6);//100个值为6的元素
5 vector<string> a(10,"null");//10个值为null的元素
6 vector<string> vec(10,"hello");//10个值为hello的元素
7 vector<string> b(a.begin(),a.end());//b是a的复制
8 struct point {int x,y;};
9 vector<point>a;//a用来存坐标(或者向量？？？或者其他东西？)

View Code

　　当然还可以定义多维数组，例如vector<int>a[MAXN];它的一维是固定的MAXN，二维是动态的。用这种方式可以实现图的邻接表的存储。

　　vector常用操作：

 1 赋值 a.push_back(100);//添加到尾部
 2 个数 int size=a.size();//元素个数
 3 空？ bool isEmpty=a.empty();//判断是否为空
 4 打印 cout<<a[0]<<endl;//打印第一个
 5 中间插入 a.insert(a.begin()+i,k);//在第i个元素前插入k;
 6 尾部插入==赋值 或者 a.insert(a.end(),10,5);//插入10个值为5的元素
 7 删除尾部 a.pop_back();//删除末尾元素
 8 删除区间 a.erase(a.begin()+i,a.end()+j);//删除区间[i,j-1];
 9 删除元素 a.erase(a.begin()+2);//删除第3个元素
10 调整大小 a.resize(n);//数组大小变为n;
11 清空 a.clear();
12 翻转 reverse(a.begin(), a.end());//使用reverse函数
13 排序 sort(a.begin(), a.end());//使用sort函数

View Code

hdu4841：http://acm.hdu.edu.cn/showproblem.php?pid=4841

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main(int argc, char const *argv[])
 4 {
 5     vector<int> v;
 6     int n,m;
 7     while(cin>>n>>m){
 8         v.clear();
 9         for (int i = 0; i < 2*n; ++i) v.push_back(i);
10         int pos=0;
11         for (int i = 0; i < n; ++i){
12             pos=(pos+m-1)%v.size();
13             v.erase(v.begin()+pos);
14         }
15         int j = 0;
16         for (int i = 0; i < 2*n; ++i){
17             if(!(i%50)&&i) cout<<endl;
18             if (j<v.size()&&i==v[j]){
19                 j++;
20                 cout<<"G";
21             }
22             else cout<<"B";
23         }
24         cout<<endl<<endl;
25     }
26     return 0;
27 }

View Code

2.stack。

　　先进后出的数据结构。

　　常用操作：

1 stack<Type>s;//定义
2 s.push(item);//将item放到栈顶
3 s.top();//返回栈顶元素但不删除
4 s.pop();//删除栈顶元素但不返回
5 s.size();//返回栈中元素个数
6 s,empty();//检查栈是否为空

View Code

hdu1062：http://acm.hdu.edu.cn/showproblem.php?pid=1062

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main(int argc, char const *argv[])
 4 {
 5     int n;
 6     char c;
 7     cin>>n;
 8     getchar();
 9     while(n--){
10         stack<char>s;
11         while(1){
12             c = getchar();
13             if (c==' '||c=='
'||c==EOF){
14                 while(!s.empty()){
15                     printf("%c",s.top());
16                     s.pop();
17                 }
18                 if (c=='
'||c==EOF) break;
19                 printf(" ");
20             }
21             else s.push(c);
22         }
23         printf("
");
24     }
25     return 0;
26 }

View Code

hdu1237：http://acm.hdu.edu.cn/showproblem.php?pid=1237

AC代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 char s[1000];
  4 int main()
  5 {
  6     while(gets(s))
  7     {
  8         if(strcmp(s,"0")==0) break;
  9         int len=strlen(s);
 10         int pos=0;
 11         stack<double> s1;
 12         stack<char> s2;
 13         for (int i = 0; i <= len; ++i)
 14         {
 15             if (s[i]>='0'&&s[i]<='9')
 16             {
 17                 double number=s[i]-'0';
 18                 i++;
 19                 while(s[i]>='0'&&s[i]<='9')
 20                 {
 21                     number=number*10+(s[i]-'0');
 22                     if(i!=len) i++;
 23                     else break;
 24                 }
 25                 s1.push(number);
 26             }
 27             else
 28             {
 29                 if(s[i]=='+'||s[i]=='-') s2.push(s[i]);
 30                 else
 31                 {
 32                     if(s[i]=='*')
 33                     {
 34                         i+=2;
 35                         double number2=s[i]-'0';
 36                         i++;
 37                         while(s[i]>='0'&&s[i]<='9'&&i!=len)
 38                         {
 39                             number2=number2*10+(s[i]-'0');
 40                             if(i!=len) i++;
 41                             else break;
 42                         }
 43                         double ans=(s1.top())*number2;
 44                         s1.pop();
 45                         s1.push(ans);
 46                     }
 47                     else if(s[i]=='/')
 48                     {
 49                         i+=2;
 50                         double number3=s[i]-'0';
 51                         i++;
 52                         while(s[i]>='0'&&s[i]<='9'&&i!=len)
 53                         {
 54                             number3=number3*10+(s[i]-'0');
 55                             if(i!=len) i++;
 56                             else break;
 57                         }
 58                         double ans=(s1.top())/number3;
 59                         s1.pop();
 60                         s1.push(ans);
 61                     }
 62                 }
 63             }
 64         }
 65         stack<double> s11;
 66         stack<char> s22;
 67         int len1=s1.size();
 68         int len2=s2.size();
 69         for (int i = 0; i < len1; ++i)
 70         {
 71             s11.push(s1.top());
 72             s1.pop();
 73         }
 74         for (int i = 0; i < len2; ++i)
 75         {
 76             
 77             s22.push(s2.top());
 78             s2.pop();
 79         }
 80         while(!s22.empty())
 81         {
 82             double x,y,z;
 83             if(s22.top()=='+')
 84             {
 85                 x=s11.top();
 86                 s11.pop();
 87                 y=s11.top();
 88                 s11.pop();
 89                 z=x+y;
 90                 s11.push(z);
 91                 s22.pop();
 92             }
 93             else
 94             {
 95                 x=s11.top();
 96                 s11.pop();
 97                 y=s11.top();
 98                 s11.pop();
 99                 z=x-y;
100                 s11.push(z);
101                 s22.pop();
102             }
103         }
104         printf("%.2f
",s11.top());
105     }
106     return 0;
107 }

View Code

3.queue。

　　先进先出的数据结构。

　　常用操作：

1 queue<Type> q;//定义一个类型为Type的队列
2 q.push(item);//把item放进队列
3 q.front();//返回队首元素，但不会删除
4 q,pop();//删除队首元素
5 q.back();//返回队尾元素
6 q.size();//返回元素个数
7 q.empty();//检查队列是否为空

View Code

hdu1702：http://acm.hdu.edu.cn/showproblem.php?pid=1702

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main(int argc, char const *argv[])
 4 {
 5     int t,n,temp;
 6     cin>>t;
 7     while(t--)
 8     {
 9         string s,s1;
10         queue<int>q;
11         stack<int>ss;
12         cin>>n>>s;
13         for (int i = 0; i < n; ++i)
14         {
15             if (s=="FIFO")
16             {
17                 cin>>s1;
18                 if (s1=="IN")
19                 {
20                     cin>>temp;
21                     q.push(temp);
22                 }
23                 if (s1=="OUT")
24                 {
25                     if (q.empty()) cout<<"None"<<endl;
26                     else
27                     {
28                         cout<<q.front()<<endl;
29                         q.pop();
30                     }
31                 }
32             }
33             else
34             {
35                 cin>>s1;
36                 if (s1=="IN")
37                 {
38                     cin>>temp;
39                     ss.push(temp);
40                 }
41                 if (s1=="OUT")
42                 {
43                     if (ss.empty()) cout<<"None"<<endl;
44                     else
45                     {
46                         cout<<ss.top()<<endl;
47                         ss.pop();
48                     }
49                 }
50             }
51         }
52         
53     }
54     return 0;
55 }

View Code

4.priority_queue。

　　优先队列，按优先级的顺序出队

　　常用操作：

 1 priority_queue<kb> qp;//定义一个kb类型的优先队列
 2 qp.top();//返回优先级最高的元素值，但不删除
 3 qp.pop();//删除优先级最高的元素
 4 qp.push(item);//插入新元素
 5 //重载运算符，自定义优先级
 6 bool operator<(const kb &b) const
 7 {
 8     if ( priority != b.priority)
 9     return priority < b.priority;
10     return index > b.index;
11 }

View Code

hdu1873：http://acm.hdu.edu.cn/showproblem.php?pid=1873

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct kb   
 5 {
 6     int priority;
 7     int index;
 8     bool operator<(const kb &b) const
 9     {
10         if ( priority != b.priority)
11         return priority < b.priority;
12         return index > b.index;
13     }
14 };
15 int main(int argc, char const *argv[])
16 {
17     int n;
18     while(cin>>n)
19     {
20         kb b;
21         int number=1;
22         priority_queue<kb> qq1;
23         priority_queue<kb> qq2;
24         priority_queue<kb> qq3;
25         for (int i = 0; i < n; ++i)
26         {
27             
28             string s;
29             cin>>s;
30             int a;
31             if (s=="IN")
32             {
33                 cin>>a>>b.priority;
34                 b.index=number;
35                 number++;
36                 if (a==1)
37                 {
38                     qq1.push(b);
39                 }
40                 else if (a==2)
41                 {
42                     qq2.push(b);
43                 }
44                 else if (a==3)
45                 {
46                     qq3.push(b);
47                 }
48             }
49             else
50             {
51                 cin>>a;
52                 if (a==1)
53                 {
54                     if (!qq1.empty())
55                     {
56                         cout<<qq1.top().index<<endl;
57                         qq1.pop();
58                     }
59                     else cout<<"EMPTY"<<endl;
60                 }
61                 else if (a==2)
62                 {
63                     if (!qq2.empty())
64                     {
65                         cout<<qq2.top().index<<endl;
66                         qq2.pop();
67                     }
68                     else cout<<"EMPTY"<<endl;
69                 }
70                 else if (a==3)
71                 {
72                     if (!qq3.empty())
73                     {
74                         cout<<qq3.top().index<<endl;
75                         qq3.pop();
76                     }
77                     else cout<<"EMPTY"<<endl;
78                 }
79             }
80         }
81         
82     }
83 
84 
85     return 0;
86 }

View Code

5.list。

　　链表，高效率地在任意地方删除和插入，常数时间。

　　常用操作与vector类似。

hdu1276:http://acm.hdu.edu.cn/showproblem.php?pid=1276

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main(int argc, char const *argv[])
 4 {
 5     int t,n;
 6     cin>>t;
 7     while(t--)
 8     {
 9         cin>>n;
10         int k=2;
11         list<int> l;
12         list<int>::iterator it;
13         for (int i = 1; i <= n; ++i) l.push_back(i);
14         while(l.size()>3)
15         {
16             int num=1;
17             for (it = l.begin();it != l.end();)
18             {
19                 if(num++ % k == 0) it = l.erase(it);
20                 else it++;
21             }
22             k==2?k=3:k=2;
23         }
24         for (it = l.begin();it!=l.end();it++){
25             if(it!=l.begin()) cout<<" ";
26             cout<<*it;
27         }
28         cout<<endl;
29     }
30     return 0;
31 }

View Code

6.set。

　　集合。

　　常用操作：

1 set<Type>a;
2 a.insert(item);//定义
3 a.erase(item);//把item放进set
4 a.clear();//删除元素item
5 a.empty();//清空set
6 a.size();//判断是否为空
7 a.find(k);//返回一个迭代器,指向键值k
8 a.lower_bound(k);//返回一个迭代器,指向键值不小于k的第一个元素
9 a.upper_bound(k);//返回一个迭代器,指向键值大于k的第一个元素

View Code

hdu2094：http://acm.hdu.edu.cn/showproblem.php?pid=2094

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main(int argc, char const *argv[])
 4 {
 5     set<string>a,b;
 6     string s1,s2;
 7     int n;
 8     while(cin>>n&&n)
 9     {
10         for (int i = 0; i < n; ++i)
11         {
12             cin>>s1>>s2;
13             a.insert(s1);
14             a.insert(s2);
15             b.insert(s2);
16         }
17         if (a.size()-b.size()==1) cout<<"Yes"<<endl;
18         else cout<<"No"<<endl;
19         a.clear();b.clear();
20     }
21     return 0;
22 }

View Code

7.map

　　map是关联容器，它实现从键值（key）到值（value）的映射。

　　简单操作：

1 map<string,int>student//学生姓名和学号
2 student["Tom"]=15//直接查找

View Code

hdu2648：http://acm.hdu.edu.cn/showproblem.php?pid=2648

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main(int argc, char const *argv[])
 4 {
 5     int n,m,p;
 6     map<string,int> shop;
 7     while(cin>>n)
 8     {
 9         string s;
10         for (int i = 0; i < n; ++i) cin>>s;
11         cin>>m;
12         while(m--)
13         {
14             for (int i = 0; i < n; ++i)
15             {
16                 cin>>p>>s;
17                 shop[s]+=p;
18             }
19             int rank = 1;
20             map<string,int>::iterator it;
21             for (it=shop.begin();it != shop.end(); ++it) if(it->second>shop["memory"]) rank++;
22             cout<<rank<<endl;
23         }
24         shop.clear();
25     }
26     return 0;
27 }

View Code

8.sort

　　排序函数，可以写自定义排序。

　　排序后可以用unique返回不同元素个数。

9.next_permutation

　　求全排列。

hdu1027:http://acm.hdu.edu.cn/showproblem.php?pid=1027

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[1010];
 4 int main(int argc, char const *argv[])
 5 {
 6     int n,m;
 7     while(cin>>n>>m)
 8     {
 9         for (int i = 1; i <= n; ++i) a[i]=i;
10         int b = 1;
11         do
12         {
13             if (b == m) break;
14             b++;
15         }while(next_permutation(a+1,a+n+1));
16         for (int i = 1; i < n; ++i) cout<<a[i]<<" ";
17         cout<<a[n]<<endl;
18     }
19     return 0;
20 }

View Code

hdu1716：http://acm.hdu.edu.cn/showproblem.php?pid=1716

此题PE了n发，格式要求很严，最后改不过来，参考网上的AC代码推倒重写了！！！（别人的代码就是要简洁些~）

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main(int argc, char const *argv[])
 4 {
 5     int a[4],k=0;
 6     cin>>a[0]>>a[1]>>a[2]>>a[3];
 7     while(1)
 8     {
 9         if (a[0]+a[1]+a[2]+a[3]==0) break;
10         sort(a,a+4);
11         int k=a[0];
12         if (a[0]!=0) cout<<a[0]<<a[1]<<a[2]<<a[3];
13         while(next_permutation(a,a+4))
14         {
15             if (a[0]==k&&a[0]!=0) cout<<" "<<a[0]<<a[1]<<a[2]<<a[3];
16             else
17             {
18                 if (a[0]!=0)
19                 {
20                     if (k!=0) cout<<endl;
21                     cout<<a[0]<<a[1]<<a[2]<<a[3];
22                 }
23                 k=a[0];
24             }
25         }
26         cout<<endl;
27         cin>>a[0]>>a[1]>>a[2]>>a[3];
28         if (a[0]+a[1]+a[2]+a[3]!=0) cout<<endl;
29     }
30     return 0;
31 }

View Code