算法竞赛初级杂烩包

这篇文章实际上是我 2014 年暑假给南理工ACM集训队的新成员介绍基础的内容的一个 markdown文档,帮助同学快速了解最算法竞赛中最常用的东西。

最近发现有的人需要,于是把他放出来。

C++

参考网站

推荐大家去这些网站查询自己需要的东西

STL中有很多好用的容器和算法,非常好用。 简单介绍一下

  • vector 向量(可以理解成可变长数组)
  • utility (pair)
  • algorithm (sort)
  • queue 队列(queue,priority_queue)
  • list (链表)
  • map (key-value映射)
  • bitset(用int各位表示的数组)

C++ 模板简单介绍

我们来看看cplusplus上对vector的介绍

template < class T, class Alloc = allocator<T> > class vector; // generic template

使用typedef 可以缩短代码长度,但是会降低可读性

iterator迭代器

迭代器是C++的重要组成部分,但是这里不细讲,只是很多STL容器的方法都返回迭代器,不对迭代器有些了解是不行的 比如遍历一个vector,可以这么做

访问iterator指向的内容可以直接用 *it访问,如果访问其成员的话,也可以用->访问

当然,我们平常是不会这么遍历数组的,这里只是演示下iterator的用法

vector

vector 是 C++ 中最常用的数据结构,相当于可变长数组,效率和使用数组没有明显差别

cpluscplus上对vector的介绍

常见用法,建立邻接表样例

我们来看一看上面发生了什么

  1. 声明:vector<int> arrary;声明了一个vector,而vector<int> tab[101] 则声明了一个vector的数组,访问5点能引出的第0条边使用tab[5][0]就可以了
  2. tab[i].clear 是将一个vector清空。 这一句在这个程序里是没有用的,但是很多题目需要多组输入输出,上一个Case的邻接表没有清空是要死得很惨的。
  3. tab[a].push_back(b) 在vector tab[a] 最后添加一个元素,值为b

如何使用这张邻接表呢

遍历a点所有连接的点

注意坑

这样是有可能会跪掉的,因为 vectorsize() 返回的是一个size_t 也就是 unsigned int ,即32位无符号数 类型,这样如果vector为空的话,size() 返回0 ,然而32位无符号数 0 – 1 = 4294967295,这样会导致访问越界然后开心的RE掉

其他重要的成员

  • vector::resize() 如果你想立即得到一个长度为100的数组而不想一个一个push_bakc进去的话,直接xxx.resize(100)就好了
  • vector::begin() 返回首个元素的迭代器
  • vector::end() 返回终止位置的迭代器,注意并非指向最后一个元素,而是比最后一个元素还要往后一个元素的位置

pair

使用 pair 需要 #include <utility>

pair 代表的是数据对,可以用来表示二维坐标(x,y),图中的边之类的东西,pair 的两个分量类型可以不同,像下面这样。

如何制造 pair

常用的方式有构造函数法和make_pair

如何使用 pair

pair 有两个主要成员 firstsecond,类型分别和为pair<U,V> 里 U,V的类型

输出

1:179.999 4 8

sort 的姿势

cplusplus上关于srot的页面 sort 是 STL里面一个非常重要的算法函数,排序效率非常高,几乎在任何时候都不会需要手敲,所以,需要排序的时候,用sort吧!

std::sort 需要 #include <algorithm>

基本排序姿势

第一种用法原型如下,传入两个RandomAccessIterator,对[first,last) 区间的元素进行排序,注意区间左闭右开,也就是传入的last迭代器指向的位置不会参与排序

  • 对int数组从大到小排序

因为指针也是RandomAccessIterator的一种,所以sort 直接传入指针就好了

  • 排序vector

vector 直接能返回迭代器,很方便

从大到小排序

我们来看看 sort 的第二个原型

这里出现了第三个参数Compare comp comp 是一个比较器,可以有很多种玩法 如果我们想从大到小排序,把greater比较器传给sort就行了

注意:比较器的使用方法,比较器std::greater是一个使用模板结构体

参见 cplusplus 对 std::greater的介绍

greater的原型为template <class T> struct greater;

我们需要传入的实际上是是一个greater<double> 类型的变量,所以需要调用greater<double> 的构造函数,最后写成greater<double>()

排序 pair

排序pair 非常容易,直接sort的时候默认以first为第一关键字,second为第二关键字排序

比如我们要对一系列事件已开始时间为第一关键字,结束时间为第二关键字排序

搞定~

对自定义结构体进行排序(重载运算符方案)

我们只需要重载结构体的<运算符即可

例如,对事件以开始时间排序

注意:比较重载运算符的两处const,和引用 &const T_event &other 防止比较函数对 other 进行修改,第二个 const 是限制比较函数不得修改所在的结构体的成员。如果不加这两个const限定就会爆满屏幕的编译错误。而比较的时候,另一个变量必须以引用方式&传递

双(多)关键字排序

比如我们要对一个结构体vector 排序,要求很复杂,首先按照a降序,然后按照c升序,再按照b降序,而且c是double值,排序的时候认为如果两个结构体的c下去正一样就算c一样,怎么搞?

这样就可以了;

使用比较函数排序

有的时候我们需要对一个数组进行多次排序,每次排序标准还不一样,怎么搞?

比如坐标,第一次按照X坐标升序排序,搞点什么,然后再按照Y坐标降序排序,那么可以这样写

向sort传入比较函数的函数指针就可以了~

对字符串排序(使用结构体,不推荐)

首先定义结构体

这种方法虽然简单,但是有很多缺陷,比如

  • 因为字符串存储在结构体中,造成结构体很大,交换结构体的开销很大
  • 不能对常量字符串排序

一般不推荐使用

对字符串排序(使用char* 数组)

由于交换字符串开销很大,但是字符串本身是不会改变的,我们并不需要交换字符串本身,最终只需要能顺字典序访问所有字符串就行了,那么,可以对每个字符串建立一个指针,然后采用上面的比较函数方法对指针进行排序即可。

(拓展) 使用自定义比较器(伪函数)

如果我们定义了一个结构体,里面有一个长度为10的int数组

我们需要对array进行10次排序,每次分别以其中一个下标(arr[0],arr[1],…)为关键字进行排序,怎么办?

写10个比较函数?听起来好靠谱的样子~~ 才怪!

还记得我们刚才提到的greater吗,std::greater 是一个结构体,我们来看看他的实现

能够看到,greater 重载了一个奇怪的运算符(),sort比较两个值的时候会使用这个运算符来对两个元素进行比较,我们也可以这么写

上面的代码 给sort函数传入了一个结构体,结构体有一个成员变量index,表示用arr[index] 为关键字进行比较,而这个index,这个index是在结构体构造的时候由构造函数传进去的 相当于

可以用下面的数据测试

5 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 1 2 3 4

(拓展)使用lambda函数进行排序(C++11)

每次都要定义一个排序函数太麻烦了有木有! 看代码的时候找比较函数往上滚滚轮都快疯了,还打断思路有木有!! 写比较器好多行好麻烦有木有!!!

然而C++11标准提供了 lambda函数(匿名函数,现声明现调用),写出的代码就好看多了

参见:Lambda函数(C++11 起)

上面的使用比较器对数组多处排序可以改成这样,注意使用 g++ xxx.cpp -std=c++11 来编译(启用C++11标准)

我们看看cppreference中给出的第一种lambda函数语法

[ capture ] ( params ) mutable exception attribute -> ret { body }

再看看我们在sort最后一个参数写了什么?

首先我们用[&j]捕获了j,这样排序函数内部就可以直接使用lambda外面的j啦,不用构造难用的比较器再传入index啦。 剩下的和之前说的使用函数比较没什么区别,只是把函数定义放在调用位置而且没起名而已~

我们再来看看使用指针排序字符串的程序,使用lambda函数可以改成这样

lambda真好用有没有!!!!

queue

queue 是STL提供的一个队列类,比手写队列有很多优势

std::queue 需要 #include <queue>

queue 的主要成员

  • push(const value_type& val) 向队列压入一个元素
  • pop() 将队头弹出
  • front() 取出队头
  • empty() 判断队列是否为空

简单的演示

注意,要及时判断queueempty(),你只有一次机会,如果队列为空再pop() 的话之后empty() 八成是返回false,因为size变成$2^{32} – 1$了,然后什么奇怪的事情都有可能发生

##priority_queue

顾名思义,优先队列,是算法竞赛中的非常重要数据结构,Dijkstra等算法 少不了它。 可以参考 cplusplus中的 priority_queue它的构造函数

priority_queue的使用方法和queue基本一致,和主要区别是front() 换成了 top() ,因为priority_queue 使用实现的

注意,priority_queue 默认是大根堆,也就是大的元素先出队,想让小的元素先出队则应当给出比较器

重载结构体运算符实现“小根堆”

我们经常会遇到想要所有元素以某种优先方法出队,比如Dijkstra算法中,想要当前距离小的点先出队,我们可以这样做

无论你使用怎样的方法,都不能改变priority_queue 是一个大根堆的事实,我们只是重载了运算符让小的元素比较起来大了而已,事实上,这是算法竞赛中非常常用的一种写法,一般来说足够用了。

(拓展)自定义priority_queue的比较方法

上面那个例子,明明可以用pair<int,int> 存下来的嘛,如果我强行要使用pair<int,int>这种不能重载运算符的怎么办? 或者有的时候我们不能重载某个结构体的<运算符怎么办?

我们先来看看priority_queue的原型

可以看到,模板参数有三个,不过后面两参数已经有默认值了,如果我们想自定义比较器,那么三个参数都要填。还记得上面sort里面讲的比较器(仿函数)嘛,第三个参数填入一个仿函数就好了

set

set是有序集合,使用set需要#include <set>

set是使用平衡树实现的,可以在$O(Log(N))$的时间内完成插入删除修改操作。

set常用来进行各种判重,比如搜索判重,状态判重等等。

cplusplus上对set的介绍

声明一个set

常用API有:

  • set::insert(val) 插入一个元素
  • set::empty() 判定set是否为空
  • set::clear() 清空set
  • set::size() 取得set大小
  • set::erase() 删除元素(有三只牛股用法)
  • set::find(val) 返回指定元素迭代器,不存在的话返返回end()
  • set::lower_bound(val)
  • set::upperbound(val)
  • set::begin() 返回从左开始的迭代器(从小到大)
  • set::end() 返回
  • set::rbegin,set::rend()
  • set::count(val) 返回set指定val的个数

显然只能返回1(有)或者0(没有),可以用来判断元素是否存在

原创文章,转载请注明(最好把图片带走): 转载自Comzyh的博客

本文链接地址: 算法竞赛初级杂烩包

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据