noip基础算法

枚举

对于一些简单的题目，我们或许不需要用什么太巧妙的方法，只需要把所有的可能性列举出来，然后逐一试验就可以了。

总的来说，枚举就是通过列举所有的可能性进行一一判断检查。

方法

通过事先把各种可能发生的事情都列举一遍，为后面求解提供结果。

总的来说，两种方法：

递归枚举，这种方法往往更直观；

递推（循环）枚举，这种方法往往写起来更简洁。

常见类型

枚举排列

枚举子集

优化

在某些情况下，直接枚举可能会带来较差的效果，在这种时候，我们实际上可以分析题目，根据题目的一些性质或特点去除大部分的列举，减小枚举量，从而提高枚举的效率。

搜索

搜索，某种意义上就是对于枚举算法的一种改进，通过在枚举的过程中，不断排除一些不可能达到的情况，从而达到优化复杂度的效果。

深度优先搜索（DFS）

深度优先搜索的思想就是：从一个顶点沿一条路一直走，如果发现到不了目标节点，则返回上一个节点，沿另一条路一直走到底。

总的来说，DFS就是一个一个处理到底，发现无法得到结果之后，逐步返回寻求其它的出路。

DFS的应用并不局限于一般的图上，其往往用于一些状态图上。

剪枝

指通过过程当中的一些量确定不可行或不符合最优的情况。

宽度优先搜索（BFS）

宽度优先搜索的核心思想在于：首先访问起始节点的所有邻接点，然后再访问较远的区域，逐步扩大范围，直到找到目标节点。

BFS也主要运用于处理状态图，尤其在一些寻求最优方案的题目中有较大的用处。

BFS处理不含边权的图的求解最短路径问题非常有效。

两种方法的优缺点

深度优先搜索，优点在于能较高效地逼近解，缺点在于初始递归方向错误会带来很严重后果；

宽度优先搜索，优点在于能迅速找到答案不算大的解，缺点在于解答案较大时所耗时间与空间都比较大。

迭代加深搜索

在综合以上两种算法之后，出现了一个折中的方法：

通过限定下界k，然后先深度优先搜索k层，如果仍没有找到有效解，则增大下界。

这个方法的优点在于：相对于深度优先搜索并没有大很多的时间开销，但能部分解决深度优先搜索的局限，没有宽度优先搜索一般的大空间需求。

分治

分治算法的基本思想：将一个较大规模的问题分成多个（一般是2个）较小规模的互相独立且与原问题相同的子问题，那么只需要通过对子问题的求解，就可以得到原问题的解。

往往子问题会采取相同的方法继续分治下去，因此分治算法一般会采取递归的方式表现。

步骤

分解：将要解决的问题划分成若干规模较小的同类问题；

求解：当子问题划分得足够小时，用较简单的方法解决；

合并：按原问题的要求，将子问题的解逐层合并构成原问题的解。

应用

二分查找

归并排序

快速幂

贪心

贪心算法指的是在对问题求解过程中，总是做出目前来看最优的选择，也就是说贪心算法不会考虑全局最优解，只会不断考虑局部最优解。

但是，我们需要注意到，局部最优解不一定就是全局最优解。

贪心算法往往可以以较低的代码复杂度与时间复杂度而得到较优的结果，对于求解近似值的作用很大。

而对于相当一部分需要求解最优值的问题，我们会发现通常可以采用动态规划或者网络流的方法取代贪心算法。

考试技巧

STL

STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。

#include<algorithm>

#include<bits/stdc++.h>（推荐）

sort()

sort函数用于给一个数组进行排序,在algorithm库里。

使用方法为sort(v.begin(),v.end(),cmp)),这里的v.begin()是开始的指针位置，v.end()是结束的指针位置（这里的表示是左闭右开，也就是说v.end()并不在排序内容里），cmp可要可不要，如果使用的是自定义类型且没有重载运算符就一定需要。

这个数组的类型可以是自定义类型或者STL中的vector，需要注意的是如果采用的是自定义类型则需要重载运算符（也可以如上面说的一样用cmp）。

stack

模拟栈，在<stack>里。

stack <Type> A;

常用函数

A.push(a)；

入栈

A.pop()；

出栈

A.top()；

返回栈顶元素（但不出栈）

queue

模拟队列，在<queue>里。

queue <Type> A;

常用函数

A.push(a)；

入队

A.pop()；

出队

A.front()；

返回队首元素（但不出队）

deque

双端队列

priority queue

优先队列，一个类似于堆的数据结构,在<queue>里。

默认是大根堆，如果想让他是小根堆的话有两种办法，其中一种是重载小于号。

能以O(logN)复杂度完成插入元素，删除最值，寻找最值。

Priority_queue <Type> A;

常用函数

A.push(a)；

插入

A.pop()；

删除最值（默认为最大值）

A.top()；

返回最值（但不删除）

pair

一个包含两个可以不同的数据值的类型。

pair <Type1,Type2> A;

往往Type1,Type2都是标准类型，但如果是自定义类型，需要重定义运算符；

常用函数

赋值:make_pair(t1,t2)；

返回对应的值:A.first,A.second；

vector

向量（Vector）是一个封装了动态大小数组的顺序容器。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的不定长的动态数组，在vector库里。

定义方式:vector <Type> A；

容器特性

顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

动态数组

支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。提供了在序列末尾相对快速地添加/删除元素的操作。

能够感知内存分配器的（Allocator-aware）

容器使用一个内存分配器对象来动态地处理它的存储需求。

相当于是个动态数组，每次可以往末端插入一个元素，下标从0开始。

实现方式是每次不够大的时候暴力倍长，可以发现均摊是线性的。

常用操作

A.clear()；

清空

A.push_back(a)；

尾部添加元素

A.pop_back()；

尾部删除元素

A.empty()；

检查是否为空，空返回true

v.size()

这个一个unsigned int类型。也就是说对空的vector的size()-1会得到2^32-1。因此写代码的时候应带尽量避免这种写法。（或者强制类型转化成int）

v.resize()

其复杂度是O(max(1, resize()中的参数-原来的size()))的。

如果是大小变大的resize()，且可以指定新扩展的位置的值。若未指定则调用其默认构造函数，例如int之类的会默认是0。

v.clear()和vector<int>().swap(v)的区别。

前者是假装清空了，实际内存没有被回收。

后者是真的回收了，不过需要和v.size()的大小成正比的时间。

后者的意思是使用vector<>()这句话调用无参的构造函数生成一个vector<>类型的对象，然后和v交换，之后其生存期结束被销毁会自动调用其~vector<>()析构函数。注意<>里面要写v一样的类型（例如int）

set

一个存储集合的容器，在set库里。

map相当于是一个下标可以是任何数值的数组，如果访问时没有赋值就会返回零。

内部使用红黑树（一种平衡树）实现。

当set<>中的第一个参数是自定义类型的时候需要重新定义小于号。

复杂度基本上是O(log(当前大小))。

定义方式:set <Type> A；

常用函数

A.insert(a)；

插入a

A.erase(a)；

删除a:

A.find(a)；

查找a，如果查找成功，返回对应指针，查找失败返回尾指针

A.begin(),A.end()；

返回头指针与尾指针，尾指针不存储具体内容

map

存储一个从key到value的映射。某种意义上就是“广义”数组，在map库里。

map相当于是一个下标可以是任何数值的数组，如果访问时没有赋值就会返回零。

内部使用红黑树（一种平衡树）实现。

当map<,>中的第一个参数是自定义类型的时候需要重新定义小于号。

复杂度基本上是O(log(当前大小))

map <Type1,Type2> A;Type1是key类型，Type2是value类型。

可以通过A[B]=C这种形式赋值，B为Type1，C为Type2。

常用函数

A.clear()；

清空

A.empty()；

判断是否为空

A.insert(pair<Type1，Type2> (C,D))；

插入（不建议这么写）

A.erase(B)；

删除，B可以是key值也可以是指针

A.begin(),A.end()；

头指针，尾指针

m[x]

哪怕你什么也不干只写一个m[x];也会新建一个点。

因此当你想知道map中是否存在这个映射的时候最好使用m.count(x)。

很多时候可以有效卡常。

multiset和multimap

是可重集合和可重映射。

有两个注意的：第一个是count函数复杂度变成了O(lg(集合大小)+答案)的，也就是如果有很多相同元素，那么count函数代价很大。

第二个是删除x的话，使用s.erase(x)会把所有权值为x的删除。

如果只想删掉一个需要s.erase(s.find(x))。

unordered_set和unordered_map

基于哈希实现的集合和映射。

基本上里面的类型只能是int,long long,double这种非自定义类型。 因为其基于哈希）

在c++11及以后存在，之前没有，乱用可能会CE。

空间常数比较大，时间常数不小，比数组访问慢很多，慎用。

不能顺序遍历，不支持lower_bound。

迭代器

只介绍set/map的迭代器。

bitset

高精度压位二进制。

一个用于处理二进制串的“数组”,在<bitset>里。

所有时间复杂度是线性的操作，常数都是1/32大概。

下标从0开始。

bitset <n> A;//n为长度；

支持所有位运算： << , >> , & , | , ^ ；

常用函数

A.count()；

统计1的个数

A.reset()；

清0

A.set()；

全赋为1

A.size()；

返回位数

lower bound()/upper bound()

lower_bound(v.begin(),v.end(),c)可以在一个有序数组当中找出刚好大于或等于c的数，在algorithm库里,可以使用自定义类型，用法与sort相类似。

upper_bound函数类似，这个函数则是在有序数组中找出刚好大于c的数。

next permutation/prev permutation(全排列算法)

algorithm头文件中包含了next_permutation(v.begin(),v.end())和prev_permutation(v.begin(),v.end())两个全排列函数，分别给出一个序列在全排列中的下一个和上一个序列(按字典序)，如果存在这样的序列则返回true，不存在则返回false，但仍会得到一个序列。

对于一个任意元素不相同的序列来说，正序排列是最小的排列方式，相应的逆序排列是最大的排列方式，以整数序列{1,2,3}为例，{1,2,3}是第一个排列，{3,2,1}则是最后一个排列，因此序列{1,2,3}没有上一个序列，{3,2,1}没有下一个序列。

pq.swap(pq2)

优先打暴力

考试中经常会遇到想到正确解法却由于写错导致分数挂零的现象，为了应付这种情况，我们可以优先写暴力程序，一来做分数保障，二来可以为对拍做准备。

多贪心原则

当一些题目的正解想不出来，并且一个贪心原则效果不好的情况下，可以采取多个贪心原则同时用，然后取最优的方案。（时间问题一般不用贪心，因为贪心算法时间复杂度往往比较小）

特判

有些时候在想不到正解的情况下，可以通过判断一些特殊情况得到部分分；有些情况虽然想到了正解，却忽略了一些特殊情况，也无法得全分。

打表

有一些题目，看上去非常复杂，但是我们实际上可以通过打表看出规律或者可能性不多，可以直接通过打表得到答案。

补充

基本位运算

位与（&）

给定两个长度相同的二进制串A、B（不同则在前面补0），A与B的结果的每一位由A与B的对应位决定，如果A与B的对应位均为1，则结果的那一位为1，否则为0。

位或（|）

A或B的结果的每一位同样由A与B的对应位决定，如果A或B的对应位为1，则结果的那一位为1，否则为0。

位异或（xor）

A异或B的结果的每一位同样由A与B的对应位决定，如果A与B的对应位不相同，则结果的那一位为1，否则为0。

左移（<<）

a<<b,左移，b以10进制表示。表示将a的最右边（最低位）加上b个0。（相当于乘上了2ⁿ）。

右移（>>）

a>>b,右移，b以10进制表示。表示将a最右面（最低位）的b位删掉。（相当于整除2ⁿ）。

并非原创，仅是整理，请见谅