第一次接触算法,只是照着自己的方法学习的,总结写的可能不是会很好,但我会努力改进。
#STL容器包括顺序式容器和关联式容器。
顺序式容器:
·vector:动态数组,从末尾能快速插入与删除,直接访问任何元素。
·list:双链表,从任何地方快速插入与删除。
·deque:双向队列,从前面或后面快速插入与删除,直接访问任何元素。
·queue:队列,先进先出
·priority_queue:优先队列,最高优先级元素总是第一个出列。
·stack:栈,先进后出。
关联式容器:
·set:集合,快速查找,不允许重复值
·multiset:快速查找,允许重复值
·map:一对多映射,基于关键字快速查找,不允许重复值
·multimap:一对多映射,基于关键字快速查找,允许重复值
1.vector
vector是STL的动态数组,在运行时能根据需要改变数组大小。
vector容器是一个模板类,能存放任何类型的对象。
·定义:
功能 例子 说明
定义int型数组 vector<int>a; 默认初始化,a为空
vector<int>b(a); 用a定义b
vector<int>a(100); a有100个值为0的元素
vector<int>a(100,6); 100个值为6的元素
定义string型数组 vector<string>a(10,"null"); 10个值为null的元素
vector<string>vec(10,"hello"); 10个值为hello的元素
vector<string>b(a.begin(),a.end()); b是a的复制
定义结构型数组 struct point{int x,y;}; a用来存坐标
vector<point>a; 同上
用户还可以定义多维数组,例如定义一个二维数组:
vector<int>a[MAXN];
它的第一维大小是固定的MAXN,第二位是动态的。用这个方式可以实现图的邻接表存储,细节见:https://oi-wiki.org/lang/csl/sequence-container/
常用操作等等,详见https://oi-wiki.org/lang/csl/sequence-container/
例子:hdu4841 “圆桌问题” https://vjudge.net/contest/337673#problem
题目大意:类似约瑟夫环问题
解题思路:利用vector容器解题,删除坏人,留下好人,对于好人输出G,对于坏人输出B
代码:
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int main(){
vector<int>table;
int n,m;//模拟圆桌
while(cin>>n>>m){
table.clear();//清空圆桌
for(int i=0;i<2*n;i++) table.push_back(i);//初始化
int pos=0; //记录当前位置
for(int i=0;i<n;i++){//赶走n个人
pos=(pos+m-1)%table.size();//圆桌是个环,做取余处理
table.erase(table.begin()+pos);//删除坏人,让人数减一
}
int j=0;
for(int i=0;i<2*n;i++){//打印预先安排座位
if(!(i%50)&&i) cout<<endl; //50字母一行
if(j<table.size()&&i==table[j]){//table留下来的都是好人
j++;
cout<<"G";
}
else
cout<<"B";
}
cout<<endl<<endl;//留一个空行
}
return 0;
}
2.栈和stack
栈:先进后出
栈的有关操作:
stack<Type>s; //定义栈,Type为数据类型,例如int,float,char等
s.push(item); //把item放到栈顶
s.top(); //返回栈顶的元素,但不会删除
s.pop(); //删除栈顶的元素,但不会返回.在出栈时需要进行两步操作,即先top()获得栈顶元素,再pop()删除栈顶元素
s.size(); //返回栈中元素的个数
s.empty(); //检查栈是否为空,如果为空,返回true,否则返回false
爆栈问题:https://blog.csdn.net/weixin_34342905/article/details/93207342
更多详见:https://oi-wiki.org/ds/stack/
例子:hdu1062”Text Reverse“ https://vjudge.net/contest/337673#problem/B
题目大意:反转字符串
解题思路:利用栈特性,进行储存,再输出。
代码:
#include<iostream>
#include<stack>
using namespace std;
int main(){
int n;
char ch;
scanf("%d",&n); getchar();
while(n--){
stack<char>s;
while(true){
ch=getchar();//一次读入一个字符
if(ch==' '||ch=='\n'||ch==EOF){
while(!s.empty()){
printf("%c",s.top()) ;//输出栈顶
s.pop();//清除栈顶
}
if(ch=='\n'||ch==EOF) break;
printf(" ");
}
else s.push(ch);//入栈
}
printf("\n");
}
return 0;
}
例子:hdu1237“简单计算器” https://vjudge.net/contest/337673#problem/C
题目大意:如上
题目思路:利用栈的操作,中间用2个栈导了一下
代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[4],hash1[4],vis[4],hash2[10000];
int flag,temp,cnt;
void Show(){
int num = hash1[0] * 1000 + hash1[1] * 100 + hash1[2] * 10 + hash1[3];
if(hash2[num]) return;
else{
hash2[num] = 1;
if(temp != hash1[0]){
cnt = 0;
temp = hash1[0];
flag++;
if(flag) printf("\n");
}
if(cnt != 0) printf(" ");
for(int i = 0;i < 4;i++){
printf("%d",hash1[i]);
}
cnt++;
}
return ;
}
void Dfs(int x){
if(x == 4){
Show();
return ;
}
for(int i = 0;i < 4;i++){
if(x == 0 && a[i] == 0)continue;
if(!vis[i]){
hash1[x] = a[i];
vis[i] = 1;
Dfs(x + 1);
vis[i] = 0;
}
}
}
int main(){
int k = 0;
while(~scanf("%d%d%d%d",&a[0],&a[1],&a[2],&a[3])){
if(!a[0] && !a[1] && !a[2] && !a[3]) break;
if(k)printf("\n");
sort(a,a+4);
memset(hash1,0,sizeof(hash1));
memset(hash2,0,sizeof(hash2));
memset(vis,0,sizeof(vis));
temp = -1,flag = -1,cnt = 0;
Dfs(0);
printf("\n");
k++;
}
return 0;
}
3.队列和queue
队列:先进先出
队列的有关操作:
queue<Type>q; //定义队列,Type为数据类型,例如int,float,char等
q.push(item); //把item放进队列
q.front(); //返回队首元素,但不会删除
q.pop(); //删除队首元素
q.back(); //返回队尾元素
q.size(); //返回元素个数
q.empty(); //检查队列是否为空
详情见:https://oi-wiki.org/ds/queue/#_4
例子:hdu1702“acboy needs your help again!” https://vjudge.net/contest/337673#problem/D
题目大意:利用站和队列的特性,输出东西
题目思路:定义站和队列,利用循环结构和判断条件,将符合要求的数据push进站和队列,然后按要求输出
代码:
#include<iostream>
#include<stack>
#include<queue>
#include<string>
using namespace std;
int main(){
int t,n,temp;
cin>>t;
while(t--){
string str,str1;
queue<int>Q;
stack<int>S;
cin>>n>>str;
for(int i=0;i<n;i++){
if(str=="FIFO"){
cin>>str1;
if(str=="IN"){
cin>>temp; Q.push(temp);
}
if(str1=="OUT"){
if(Q.empty()) cout<<"None"<<endl;
else{
cout<<Q.front()<<endl;
Q.pop();
}
}
}
else{
cin>>str1;
if(str1=="IN"){
cin>>temp; S.push(temp);
}
if(str1=="OUT"){
if(S.empty()) cout<<"None"<<endl;
else{
cout<<S.top()<<endl;
S.pop();
}
}
}
}
}
return 0;
}
优先队列,顾名思义就是优先级最高的先出队。
有关操作如下:
q.top(); //返回具有最高优先级的元素值,但不删除该元素
q.pop(); //删除最高优先级元素
q,push(item); //插入新元素
可以用优先队列对数据排序,设定数据小的优先级高,把所有数push进优先队列后一个个top出来,就得到了从小到大的排序,其总复杂度时O(nlog以2为底的n)
详见:自己搜索吧,良莠不齐的
例子:hdu1873“看病要排队” https://vjudge.net/contest/337673#problem/E
题目大意:
解题思路:
代码:
#include<iostream>
#include<stack>
#include<queue>
#include<string>
using namespace std;
int main(){
int t,n,temp;
cin>>t;
while(t--){
string str,str1;
queue<int>Q;
stack<int>S;
cin>>n>>str;
for(int i=0;i<n;i++){
if(str=="FIFO"){
cin>>str1;
if(str=="IN"){
cin>>temp; Q.push(temp);
}
if(str1=="OUT"){
if(Q.empty()) cout<<"None"<<endl;
else{
cout<<Q.front()<<endl;
Q.pop();
}
}
}
else{
cin>>str1;
if(str1=="IN"){
cin>>temp; S.push(temp);
}
if(str1=="OUT"){
if(S.empty()) cout<<"None"<<endl;
else{
cout<<S.top()<<endl;
S.pop();
}
}
}
}
}
return 0;
}
4.链表和list
STL的list是数据结构的双向链表,它的内存空间可以是不连续的,通过指针来进行数据的访问,它可以高效率的在任意地方删除和插入,插入和删除操作是常数时间的。
list和vector的优缺点正好相反,他们的应用场景不同:
(1)vector:插入和删除操作少,随机访问元素频繁。
(2)list:插入和删除频繁,随机访问较少。
详见:https://oi-wiki.org/ds/linked-list/
list例子:hdu1276“士兵队列训练问题” https://vjudge.net/contest/337673#problem/F
题目大意:轮流进行1-2,1-3报数,出列
解题思路:构建list,利用循环结构,取余,求人
代码:
#include <iostream>
#include <list>
using namespace std;
int main(){
int t,n;
cin>>t;
while(t--){
cin>>n;
int k=2;
list<int>mylist;
list<int>::iterator it;
for(int i=1;i<=n;i++)
mylist.push_back(i);
while(mylist.size()>3){
int num=1;
for(it=mylist.begin();it!=mylist.end();){
if(num++%k==0)
it=mylist.erase(it);
else
it++;
}
k==2?k=3:k=2;
}
for(it=mylist.begin();it!=mylist.end();it++){
if(it!=mylist.begin())
cout<<" ";
cout<<*it;
}
cout<<endl;
}
return 0;
}
5.set
set和map在竞赛题中的应用很广泛,特别是需要用二叉搜索树处理数据的题目,如果用set和map实现,能极大地简化代码。
set的有关操作:
set<Type>A //定义
A.insert(item); //把item放进set
A.erase(item); //删除元素item
A.clear(); //清空set
A.empty(); //判断是否为空
A.size(); //返回元素个数
A.find(k); //返回一个迭代器,指向键值K
A.lower_bound(k); //返回一个迭代器,指向键值不小于k的第一个元素
A.upper_bound(); //返回一个迭代器,指向键值大于k的第一个元素
详见:https://oi-wiki.org/lang/csl/associative-container/
例子:hdu2094“产生冠军” https://vjudge.net/contest/337673#problem/G
题目大意:判断冠军
题目思路:定义集合A和B,把所有人放进集合A,把所有有失败记录的放进集合B,如果A-B=1,则可以判断存在冠军,否则不能。
代码:
#include<iostream>
#include<string>
#include<set>
using namespace std;
int main(){
set<string>A,B;
string s1,s2;
int n;
while(cin>>n&&n){ //若输入为0则退出,若不是0则循环
for(int i=0;i<n;i++){
cin>>s1>>s2;
A.insert(s1); A.insert(s2);
B.insert(s2);
}
if(A.size()-B.size()==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
A.clear(); B.clear();
}
return 0;
}
6.map
map是关联容器,它实现从键(key)到值(value)的映射。map效率高的原因是他用平衡二叉搜索树来存储和访问。
map在例子中具体操作如下:
(1)定义,map<string,int>student,存储学生的name和id
(2)赋值:例如stduent["Tom"]=15。这里把”Tom“当成普通数组的下标来使用。
(3)查找:在找学号时,可以直接使用student["Tom"]表示他的id,不再去搜索所有的姓名。
详见:https://oi-wiki.org/lang/csl/associative-container/
例子:hdu2648"Shopping" https://vjudge.net/contest/337673#problem/H
题目大意:得知商店排行
题目思路:如下
代码:
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
int n,m,p;
map<string,int>shop;
while(cin>>n){
string s;
for(int i=1;i<=n;i++) cin>>s;//输入商店名字,实际上用不着处理
cin>>m;
while(m--){
for(int i=1;i<=n;i++){
cin>>p>>s;
shop[s]+=p;//用map直接操作商店,加上价格
}
int rank=1;
map<string,int>::iterator it;//迭代器,,遍历数据,判断是否集合中有数据,
//有则取出,然后不断执行
for(it=shop.begin();it!=shop.end();it++)
if(it->second>shop["memory"])
rank++;
cout<<rank<<endl;
}
shop.clear();
}
return 0;
}
7.sort
注意:它排序的范围是[first,last),包括first,不包括last
<1>sort()的比较函数
sort()可以用自定义的比较函数进行排序,也可以用系统的种函数排序,即less(),greater(),less_equal(),greater_equal()。在默认情况下,程序是按从大到小的顺序排序的,less()可以不写。 例子详见P34
sort()还可以对结构变量进行排序,例子详见P35
<2>相关函数
stable_sort():当排序元素相等时,保留原来的顺序。在对结构体排序时,当结构体中的排序元素相等时,如果需要保留原序,可以用它。
partial_sort():局部排序。例如有10个数字,求最小的5个数。如果用sort(),需要先全部排序,再输出前5个;而用它可以直接输出前5个。
8.next_permutation()
返回值:如果没有下一个排列组合,返回false,否则返回true。每执行它一次,就会把新的排列放到原来的空间里去。
它的排列范围时[first,last),包括first,不包括last
例子:hdu1027”Ignatius and the Princess II“ https://vjudge.net/contest/337673#problem/I
题目大意:如题
题目思路:利用它生成一个一个小的序列,直到m小
代码:
#include<iostream>
#include<algorithm>
using namespace std;
int a[1001];
int main(){
int n,m;
while(cin>>n>>m){
for(int i=1;i<=n;i++) a[i]=i;//生成一个字典序最小的序列
int b=1;
do{
if(b==m) break;
b++;
}while(next_permutation(a+1,a+n+1));
for(int i=1;i<n;i++)//注意第一个是a+1,最后一个是a+n
cout<<a[i]<<" ";//输出第m大的字典序
cout<<a[n]<<endl;
}
return 0;
}
例子:hdu"排列2” https://vjudge.net/contest/337673#problem/J
题目大意:如题
题目思路:
代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[4],hash1[4],vis[4],hash2[10000];
int flag,temp,cnt;
void Show(){
int num = hash1[0] * 1000 + hash1[1] * 100 + hash1[2] * 10 + hash1[3];
if(hash2[num]) return;
else{
hash2[num] = 1;
if(temp != hash1[0]){
cnt = 0;
temp = hash1[0];
flag++;
if(flag) printf("\n");
}
if(cnt != 0) printf(" ");
for(int i = 0;i < 4;i++){
printf("%d",hash1[i]);
}
cnt++;
}
return ;
}
void Dfs(int x){
if(x == 4){
Show();
return ;
}
for(int i = 0;i < 4;i++){
if(x == 0 && a[i] == 0)continue;
if(!vis[i]){
hash1[x] = a[i];
vis[i] = 1;
Dfs(x + 1);
vis[i] = 0;
}
}
}
int main(){
int k = 0;
while(~scanf("%d%d%d%d",&a[0],&a[1],&a[2],&a[3])){
if(!a[0] && !a[1] && !a[2] && !a[3]) break;
if(k)printf("\n");
sort(a,a+4);
memset(hash1,0,sizeof(hash1));
memset(hash2,0,sizeof(hash2));
memset(vis,0,sizeof(vis));
temp = -1,flag = -1,cnt = 0;
Dfs(0);
printf("\n");
k++;
}
return 0;
}