算法竞赛初级杂烩包

未分类

C++

参考网站

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

• cpluscplus
• cppreference
• cppreferne中文

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 > class vector; // generic template

vector<int> arr; 
queue<int> q;
vector<pair<int,int> > ponints; // 注意那个空格
map<string,int> reflect;

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

typedef pair<int,int> pii;
vector<pii> points;

iterator迭代器

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

vector<int> n;
for(vector<int>:: it=n.begin();it!=n.end();it++)
    cout << *it << endl;

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

vector<pair<int,int> > points;
for （vector<pair<int,int> >::iterator = n.begin();it != n.end();it++)
    cout << "x: " <<  it->first << "y: " << (*it).second << endl;

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

vector

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

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

#include <iostream>
#include <vector>
const int MAXN = 100;
vector<int> tab[MAXN+1];
int main()
{
    cin >> N >> M;
    for (int i=1;i<=N;i++)
        tab[i].clear();
    for (int i = 0;i<M；i++)
    {
        int a,b;
        cin >> a >> b;
        tab[a].push_back(b);
    }
}

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

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点所有连接的点

vecotr<int> tab[100]
for (int i = 0;i<tab[a].size();i++)
    cout << tab[a][i] << endl;

注意坑

for (int i = 0;i <= tab[a].size()-1;i++)
    cout << endl;

这样是有可能会跪掉的，因为 vector 的 size() 返回的是一个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 的两个分量类型可以不同，像下面这样。

typedef pair<int,int> point; //藐视一个点
typedef pair<string,int> name_and_id_pair; // 学生姓名和学号
typedef pair<int,double> id_to_height pair; // 学生学号和身高

如何制造 pair

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

pair<int,int> point1 = make_pair(1,1);
pair<double,double> point2 = make_pair(2.0,3.0);
pair<int,int> point3 = pair<int,int>(1.0,2.0);
pair<int,int> point4 = make_pair(1.0,2.0); // 这句会编译失败，因为make出来的是pair<double,double> 却赋值给了pair<int,int>

如何使用 pair

pair 有两个主要成员 first 和 second，类型分别和为pair 里 U，V的类型

pair<int, double> yz = make_pair(1, 179.99999);
cout << yz.first << ":" << yz.second << endl;
cout << sizeof(yz.first) << " " << sizeof(yz.second) << endl;

输出

1:179.999
4 8

sort 的姿势

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

std::sort 需要 #include <algorithm>

基本排序姿势

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

template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);

• 对int数组从大到小排序

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

const int N = 1000;
int arr[N];
sort(arr , arr + N); // 注意arr + N 指向的位置已经越界，但是sort传入的last参数就是指向最后一个元素后的一个位置

• 排序vector

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

vector<int> array;
sort(array.begin(), array.end());

从大到小排序

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

template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

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

vector<double> height;
sort(height.begin(), begin.end(), greater<double>());

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

参见 cplusplus 对 std::greater的介绍

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

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

排序 pair

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

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

vector<pair<int,int> > events;
sort(events.begin(),events.end());

搞定~

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

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

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

struct T_event
{
    int begin_at, end_at;
    bool operator <(const T_event &other)const
    {
        return begin < other.begin；
    }
};
vector<T_event> events;
sort(events.begin(),events.end());

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

双（多）关键字排序

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

struct Three_key
{
    int a, b;
    double c;
    bool opeartor < (const Three_key &other)const
    {
        if (a != other.a)
            return a > other.a;
        if ((int)c != (int)other.c)
            return (int)c < (int)other.c;
        return b > other.b;
    }
};

这样就可以了;

使用比较函数排序

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

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

vector<pair<int,int> > points;
bool cmp_x_inc(const pair<int,int> &p1, const pair<int,int> &p2)
{
    return p1.first < p2.first;
}
bool cmp_y_dec(const pair<int,int> &p1, const pair<int,int> &p2)
{
    return p1.second < p2.second;
}
sort(points.begin(),points.end(),cmp_x_inc);//X 升序
//do something...
sort(points.begin(),points.end(),cmp_y_dec);//Y 降序

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

对字符串排序（使用结构体，不推荐）

首先定义结构体

#include <cstdio> // strcmp 函数在这里
struct T_String
{
    char str[10000];
    bool operator < (const T_String &s)
    {
        return strcmp(str,s.str) < 0;
    }
};
vector<T_String> strs;
sort(strs.begin(),strs.end());

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

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

一般不推荐使用

对字符串排序（使用char* 数组）

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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int N = 0;
char strs[1000][1000];
vector<char *> strs_sorted;
bool char_ptr_cmp(const char *a, const char *b)
{
    return strcmp(a,b) < 0;
}
int main()
{
    while (scanf("%s", strs[N++]) != EOF);
    for (int i = 0; i < N; i++)
        strs_sorted.push_back(strs[i]);
    sort(strs_sorted.begin(), strs_sorted.end(), char_ptr_cmp);
    printf("sorted strs are:\n");
    for (vector<char*>::iterator it = strs_sorted.begin(); it != strs_sorted.end(); it++)
        printf("%s\n", *it);
    return 0;
}

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

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

struct T_arr
{
    int arr[10];
};
vector<T_arr> array;

我们需要对array进行10次排序，每次分别以其中一个下标（arr[0],arr[1],...）为关键字进行排序，怎么办？

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

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

template <class T> struct greater : binary_function <T,T,bool> {
  bool operator() (const T& x, const T& y) const {return x>y;}
};

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

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct T_arr
{
    int arr[4];
};
vector<T_arr> to_sort;
struct T_arr_cmp
{
    int index;
    T_arr_cmp(int index): index(index) {} // 构造函数
    bool operator ()(const T_arr &a, const T_arr &b)
    {
        return a.arr[index] < b.arr[index];
    }
};
int main()
{
    int N;
    scanf("%d", &N);
    to_sort.resize(N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < 4; j++)
            scanf("%d", &to_sort[i].arr[j]);
    for (int j = 0; j < 4; j++)
    {
        sort(to_sort.begin(), to_sort.end(), T_arr_cmp(j)); // 传入比较器,以数组的第j位为关键字
        printf("the to_sort sort by arr[%d] is:\n", j);
        for (int i = 0; i < N; i++)
            printf("%4d %4d %4d %4d\n", to_sort[i].arr[0], to_sort[i].arr[1], to_sort[i].arr[2], to_sort[i].arr[3]);
    }
    return 0;
}

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

T_arr_cmp cmp(j);
sort(array.begin(), array.end(), cmp);

可以用下面的数据测试

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标准）

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct T_arr
{
    int arr[4];
};
vector<T_arr> to_sort;
int main()
{
    int N;
    scanf("%d", &N);
    to_sort.resize(N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < 4; j++)
            scanf("%d", &to_sort[i].arr[j]);
    for (int j = 0; j < 4; j++)
    {
        sort(to_sort.begin(), to_sort.end(), [&j](const T_arr &a, const T_arr &b)->bool
        {
            return a.arr[j] < b.arr[j]; 
        }); 
        printf("the to_sort sort by arr[%d] is:\n", j);
        for (int i = 0; i < N; i++)
            printf("%4d %4d %4d %4d\n", to_sort[i].arr[0], to_sort[i].arr[1], to_sort[i].arr[2], to_sort[i].arr[3]);
    }
    return 0;
}

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

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

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

sort(to_sort.begin(), to_sort.end(), [&j](const T_arr &a, const T_arr &b)->bool
{
    return a.arr[j] < b.arr[j]; 
}); 

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

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

sort(strs_sorted.begin(), strs_sorted.end(), [](const char *a, const char *b)->bool
{
    return strcmp(a,b) < 0;
});

lambda真好用有没有！！！！

queue

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

std::queue 需要 #include <queue>

queue 的主要成员

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

简单的演示

queue<int> q;
q.push(0);
while (!q.empty())
{
    int h = q.front();
    q.pop();
    if (h < 100)
        q.push(h+1)
    printf("%d\n",h);
}

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

priority_queue

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

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

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

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

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

struct State
{
    int point,dis;
    bool operator < (const State &s)const
    {
        return dis > s.dis;
    }
};
priority_queue<State> q;

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

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

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

我们先来看看priority_queue的原型

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

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

struct pair_cmp
{
    bool operator()(const pair<int, int> &a, const pair<int, int> &b)
    {
        return a.second > b.second;
    }
};
priority_queue<pair<int, int>, vector<pair<int, int> >, pair_cmp> q;

set

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

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

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

cplusplus上对set的介绍

声明一个set

set<int> iset;

常用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（没有），可以用来判断元素是否存在