当前位置:首页 >> 工学 >> ACM竞赛中STL的应用

ACM竞赛中STL的应用


STL 在ACM竞赛中的应用
ACM Matrix_68

目录

1
2 3

泛型程序设计简介与迭代器的介绍

常见的STL容器及其成员函数
相关例题解析

泛型程序设计
? 泛型程序设计,简单地说就是使用模板的程序设计法。 ? 将一些常用的数据结构(比如链表,数组,二叉树)和 算法(比如排序,查找)写成模板,以后则不论数据结 构里放的是什么对象,算法针对什么样的对象,则都不 必重新实现数据结构,重新编写算法。
? 标准模板库 (Standard Template Library) 就是一些常用数据结 构和算法的模板的集合。主要由 Alex Stepanov 开发,于1998 年被添加进C++标准

? 有了STL,不必再从头写大多的标准数据结构和算法,并 且可获得非常高的性能。

迭代器(iterator)
? 可遍历STL容器内全部或部分元素的对象 ? 指出容器中的一个特定位置 ? 所有容器都提供获得迭代器的函数
操作 begin() end() 效果 返回一个迭代器,指向第一个元素 返回一个迭代器,指向最后一个元素之后

begin()

end()

半开区间[beg, end)的好处: 1.为遍历元素时循环的结束时机提供了简单的判断依据(只要未到达end(),循环就可 以继续) 2.不必对空区间采取特殊处理(空区间的begin()就等于end())

常见的STL容器及其函数
准容器类 顺序性容器 vector deque list 关联容器 set multiset map multimap 容器适配器 stack queue priority_queue 说明
从后面快速的插入与删除,直接访问任何元素 从前面或后面快速的插入与删除,直接访问任何元素 双链表,从任何地方快速插入与删除 快速查找,不允许重复值 快速查找,允许重复值 一对多映射,基于关键字快速查找,不允许重复值 一对多映射,基于关键字快速查找,允许重复值 后进先出 先进先出 最高优先级元素总是第一个出列

所有标准库共有成员函数
empty max_size size clear 容器中没有元素时返回true,否则返回false 返回容器中最大元素个数 返回容器中当前元素个数 清除容器中所有元素

insert
swap begin end

插入元素
交换两个容器的元素 该函数两个版本返回iterator或const_iterator,引用容器第一个元素 该函数两个版本返回iterator或const_iterator,引用容器最后一个元素后面一位

operator=
operator< operator<= operator> operator>= operator== operator!=

将一个容器赋给另一个容器
如果第一个容器小于第二个容器,返回true,否则返回false, 如果第一个容器小于或等于第二个容器,返回true,否则返回false 如果第一个容器大于第二个容器,返回true,否则返回false 如果第一个容器大于或等于第二个容器,返回true,否则返回false 如果第一个容器等于第二个容器,返回true,否则返回false 如果第一个容器不等于第二个容器,返回true,否则返回false

Sort
? 例题1:UVA 10474 Where is the Marble

? 题目:题目意思就是给出两个数m和n下面输入m个数,再依次输入n个数, 查找n个数在前面的m个数中是第几大 ? 思路很简单,排序加查找(也可以二分优化)。

? 这里简述sort函数的用法
? ? ? ? ? 头文件: <algorithm> 格式: sort(vect.begin(), vect.end()); sort(vect.begin(), vect.end(), less<int>() ); 第三个参数可以自定义,主要用于自定义类型的排序

常见的STL容器
? STL容器类别
? 序列式容器-排列次序取决于插入时机和位置 ? 关联式容器-排列顺序取决于特定准则
vector deque

set

list

map 序列式容器 关联式容器

序列式容器
? 序列式容器 常

见 的 ? 向量(vector) 容 器 STL

顺序容器包含Vector,deque和list三种容器,其中vector和deque属于 直接访问容器,list属于顺序访问容器。

向量相当于一个动态数组,其可以动态存储元素,并提供对容器元素的随 机访问。为了提高效率,vector并不是随着每一个元素的插入而增长自己, 而是当vector要增长自己的时候,他分配的空间比当前所需的空间要多一 些。这多一些的内存空间使需要添加新元素的时候不必再重新分配内存。 与C++的内置数组相比较,除了动态之外,向量容器支持向对象。

9

Vector(不定长数组)
用法: vector<类型> 名字; 例如 vector<int> ve; vector<string> ve; 自己定义的结构体什么的也可以往里塞 struct POINT { int x, y; }; vector<POINT> ve; 基本操作 ve.push_back(const value_type &val); 作用是在数组后面增加一个元素。括号里填的是ve里装的东西 ve.clear();清空ve里的所有元素。 ve.empty();判断ve是否为空,如果是返回true,否则false ve.size();返回ve的长度。注意这里返回的类型是unsigned int,如果ve是空的ve.size() - 1 就会爆掉。使用的时候一定要小心(做TC的时候被坑了一次) ? ve.pop_back() 删除数组里的最后一个元素。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

Vector(不定长数组)
? 例题2:UVA101 The Blocks Problem ? 题目:给你n个方块,有四种操作:
? ? ? ? ? ? ? ? ? ? ? 1.move a onto b,把a和b上面的方块都放回原来位置,然后把a放到b上面; 2.move a over b,把a上面的放回原处,然后把a放在b所在的方块堆的上面; 3.pile a onto b,把b上面的放回原来位置,然后把a和a上面的方块整体放到b上面; 4.pile a over b,把a和a上面的方块整体放到b所在堆的上面。 1.将a上面的还原init_place(a); 2.将a和上面的(可以没有上面的)放到b上面pile_a_to_b(a,b)。 那么上述的四组操作就变成下面了: 1.move a onto b,init_place(a);init_place(b);pile_a_to_b(a,b); 2.move a over b,init_place(a);pile_a_to_b(a,b); 3.pile a onto b,init_place(b);pile_a_to_b(a,b); 4.pile a over b,pile_a_to_b(a,b)。

? 定义两个基本操作:

关联式容器
? 关联式容器 常

见 的 容 器

包括set, multiset, map, multimap,内部元素有序排列,新元素插入 的位置取决于它的值,查找速度快。 关联容器是通过键(key)存储和读取元素的 而顺序容器则通过元素在容器中的位置顺序存储和访问元素。

STL

? 集合(Set)
一个集合(set)是一个容器,它其中所包含的元素的值是唯一的。这在收集 一个数据的具体值的时候是有用的。
12

? 用法:

Set(集合)

? set<类型> 名字; ? 例如 set<int> se; set<string> se; ? 自己定义的结构体什么的也可以往里塞 ? struct POINT ? {

?
? };

int x, y;

? set<POINT> se;

? 基本操作对集合a中元素的有
? 插入元素:a.insert(1); ? 删除元素(如果存在):a.erase(1); ? 判断元素是否属于集合:if (a.find(1) != a.end()) ... ? 返回集合元素的个数:a.size() ? 将集合清为空集:a.clear()

Set(集合)
? 例题3:UVA 10815 Andy's First Dictionary ? 题目:给出一串单词,把所有单词改小写去重按字典序输出。 ? 思路:set可以解决去重和排序问题。 ? set中每个元素最多只出现一次 ? set中的元素已经从小到大排序好 ? 如何通过迭代器从小到大遍历所有元素 ? for (set<string>::iterator i = d.begin(); i != d.end(); i++)
? cout << *i << endl;

Map(映射)
? map添加数据; ? map<int ,string> maplive; //第一个是键值,第二个是值 ? 1.maplive.insert(pair<int,string>(102,"aclive"));

? 2. maplive[112]="April";//map中最简单最常用的插入添加!
? map中查找数据: ? 第一种:用count 函数来判定关键字是否出现,其缺点是无法定位数据出现位置,

? 由于map 的特性,一对一的映射关系,就决定了count 函数的返回值只有两个,
? 要么是0,要么是1,出现的情况,当然是返回1 了 ? 第二种:用find 函数来定位数据出现位置,它返回的一个迭代器,当数据出现时,它返回 数据所在位置的迭代器,如果map 中没有要查找的数据,它返回的迭代器等于end 函数返 回的迭代器

? 注意:Map和set内部的元素不可以重复 ? Map中的元素是自动按key升序排序,所以不能对map用sort函数 ? 但可以用迭代器按序遍历(与set类似)

Map(映射)
? 例题4:UVA 156 Ananagrams ? 题目:把每个单词全部转化成小写字母,对每个单词,看它的字母 重排后得到的单词在所有输入的单词中是否出现过,若没有出现, 就输出原单词。所有要输出的单词按字典序排列输出。 ? 思路:构造小写化函数,set可以解决去重和排序问题,用map建 立string与int的映射 ? void string stand_words(string s1); ? 注意要存储原单词! ps:也可以用multimap建立string与string的多重映射,即原单词 与现单词的映射,方便提取原单词操作

Queue(队列)
? ? ? ? ? ? ? ? ? ? ? ?

队列的容器。 用法 和vector一样。 queue<int> qu; queue<POINT> qu; 我一般都用它在BFS的时候存点。 常用操作 qu.push(const value_type &val); 元素入队 qu.pop()元素出队 qu.front() 获得队首元素 qu.empty() 判断qu是否为空,是的话返回true qu.size() 获得qu的大小。

Queue(队列)
? 例题5:UVA 540 Ananagrams ? 题目:题意:有t个团队的人在排队。每次来了一个新人之后,如 果他有队友在排队,那么这个新人会插队到队友的身后。要求支持 三种指令:ENQUEUE x; DEQUEUE(队首出队); STOP。模拟 这个过程,输出出队顺序 ? 思路:模拟题。每个队列在一个大队列排队 ? queue<int> q, q2[maxt]; ? q为总的团队队列,q2为每个团队的队列

priority_queue(优先队列):默认从大到小排列。
? priority_queue<int> pqu; ? 如果要装结构体的话,要重载结构体的小于号,或者自己写一个cmp函数。 ? struct cmp ? { operator bool ()(int x, int y) { return x > y; // x小的优先级高 } ? }; ? priority_queue<int, vector<int>, cmp>q;//第二个参数为容器类型。第三个参数为比较函数。

? priority_queue<vector<int>, less<int>> pq1; // 使用递减less<int>函数对象排序
? priority_queue<deque<int>, greater<int>> pq2; // 使用递增greater<int>函数对象排序 ? 常用操作

? push(),top(),pop(),empty();

priority_queue(优先队列)
? 例题6:UVA 136 Ugly Number ? 题目:把只包含因子2、3和5的数称作丑数(Ugly Number)。例 如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当 做是第一个丑数。求出第n个丑数。 ? 思路:利用优先队列 ? //最后不要挨到一起,默认为位运算 ? priority_queue<LL,vector<LL>,greater<LL> >pq; ? 注意用long long!

next_permutation(全排列):要包含头文件<algorithm>
? 与之完全相反的函数还有prev_permutation ? a[0]=1;a[1]=2;a[2]=3; ? do{cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;}while (next_permutation(a,a+3)); ? 输出: ? 123 ? 132

? 213
? 231 ? 312

? 321
? 如果改成 while(next_permutation(a,a+2)); ? 则输出: ? 123 ? 213 ? 只对前两个元素进行字典排序

next_permutation(全排列):
? 例题7:HDU 1027 Ignatius and the Princess II ? 题目:求N个数全排列,顺着数第M个 ? 思路:利用next_permutation ? while(m--) ?{
next_permutation(num,num+n);

?} ? 例题9:HDU 1716 排列2 ? 思路同理

灵活练习
? 例题8:Codeforces 501B - Misha and Changing Handles ? 题目:有一些人改名字,输出每个人的原名和改了之后的名字. ? 思路:用map记录每个人换过的名字,用set记录是不是一个新的 ? 人,如果是的话就放到数组里。

结合使用
? 例题10:HDU 4277 - USACO ORZ ? 题目:给定一些一定长度的线段,要求全部利用这些线段能拼成多 少种三角形(如果两个三角形至少有一条边长度不等那么二者视为 两种) ? 思路:DFS,对于所有满足情况的三角形加入set中,这样就去重 了,最后set的大小就是答案

谢谢观看
ACM Matrix_68 2015/8/30


更多相关文档:

STL+in+ACM

ACM中STL的应用 29页 1下载券 ACM竞赛与STL 31页 1下载券 ACM竞赛辅导之STL...2. 算法(algorithm): #inlcude <algorithm> STL 中算法的大部分都不作为某些...

STL in ACM

ACM竞赛辅导之STL 27页 免费 C++ 标准模板库(STL) 20页 免费 ACM中STL的应用 29页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议...

STL_in_ACM

STL in ACM 3页 1财富值 ACM中STL的应用 29页 2财富值 ACM竞赛与STL 31页 2财富值 ACM竞赛辅导之STL 27页 免费 06_ACM数据结构与STL 28页 2财富值 STL...

STL常用总结

STL常用总结_计算机软件应用_IT/计算机_专业资料。ACM资料 STL 常用总结 Last Update (July. 2014) by WING ACM/ICPC 竞赛STL 简介 一、关于 STL STL(...

STL in ACM

3页 1财富值 ACM中STL的应用 29页 2财富值 ACM竞赛辅导之STL 27页 免费 ...06_ACM数据结构与STL 28页 2财富值如要投诉违规内容,请到百度文库投诉中心;如...

ACM竞赛模板

ACM竞赛模板_计算机软件应用_IT/计算机_专业资料。一、最短路 ①DJK #define...p2,p4)) return 1; return 0;//两线段不相交返回 false } 五、STL 函数 ...

ACM竞赛平台在计算机专业教学中的应用研究

ACM 竞赛平台在计算机专业教学中的应用研究 摘要:本文分析了目前高校计算机专业教学中存在的一些问题,探讨了 ACM 竞赛平台在解决这些问题和学生创新能力培养中的重要...

acm常用STL函数库

} Set 常用函数:跟其他容器的函数差不多,好像都通 用 c++ stl 容器 set ...STL in ACM 24页 5下载券 ACM中STL的应用 29页 1下载券 ACM竞赛辅导之...

2011年ACM大赛真题试题

2011年ACM大赛真题试题_电脑基础知识_IT/计算机_专业资料。重庆市第二届大学生...假设内存中有 M 个单元,每单元能存放一个单词和译义。每当软件将一个新单词...

acm竞赛的题型分析

在线互动式文档分享平台,在这里,您可以和千万网友分享自己手中的文档,全文阅读其他用户的文档,同时,也可以利用分享文档获取的积分下载文档
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com