排序：
#include<bits/stdc++.h>
using namespace std;
int a[1000001],n;
int b[1000001],tmp[1000001];
int GetMax(int a[],int n)
{
int max=a[0];
for(int i=1;i<n;i++){
if(a[i]>max) max = a[i];
}
return max;
}
void QuickSort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
QuickSort(q, l, j), QuickSort(q, j + 1, r);
}
int ans;
void MergeSort(int q[],int l,int r)
{
if(l==r)return;
int i=l,mid=(l+r)/2,j=mid+1,k=l;
MergeSort(q,l,mid);
MergeSort(q,mid+1,r);
while(i<=mid&&j<=r)
{
if(q[i]<=q[j]){
tmp[k++]=q[i++];
}
else{
ans=ans+j-k;
tmp[k++]=q[j++];
}
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(int i=l;i<=r;i++)
q[i]=tmp[i];
}
void MergeFindSort( int a[] , int n )
{
int low , high , mid ;
int temp ;
for ( int i=1 ; i<n ; i++ )
{
temp = a[i ];
low = 0 ;
high = i - 1 ;
while ( low <= high )
{
mid = ( low + high ) / 2 ;
if ( a[mid] > temp )
high = mid - 1 ;
else
low = mid + 1 ;
}
for ( int j = i - 1 ; j > high ; j-- )
a[j+1] = a[j] ;
a [high+1] = temp ;
}
}
void ShellSort(int arr[], int len)
{
int i, j, temp, jump=len>>1;
while (jump != 0)
{
for (i = jump; i < len; i++)
{
temp = arr[i];
j = i - jump;
while (j >= 0 && temp < arr[j])
{
arr[j + jump] = arr[j];
j=j-jump;
}
arr[j + jump] = temp;
}
jump/=2;;
}
}
void CountingSort(int a[],int n)
{
int m = GetMax(a,n);
int b[m+1]={0};
for(int j=0;j<n;j++) b[a[j]]++;
for(int i=0,k=0;i<=m||k<n;i++)
{
while(b[i]>0){
a[k++] = i;
b[i]--;
}
}
}
void RadixSort(int*a,int length)
{
int max=a[0];
for(int i=1;i<length;i++)
{
if(a[i]>max)
{
max=a[i];
}
}
int base=1;
int *b=(int*)malloc(sizeof(int)*length);
int i;
while(max/base>0)
{
int t[10]={0};
for(i=0;i<length;i++)
{
t[a[i]/base%10]++;
}
for(i=1;i<10;i++)
{
t[i]+=t[i-1];
}
for(i=length-1;i>=0;i--)
{
b[t[a[i]/base%10]-1]=a[i];
t[a[i]/base%10]--;
}
for(i=0;i<length;i++)
{
a[i]=b[i];
}
base=base*10;
}
}
void InsertSort(int* a, int n)
{
int i = 0;
for (i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
void BubbleSort(int a[],int n)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
}
void SelectSort(int arry[], int len)
{
int i;
int j;
for ( i = 0; i < len-1; i++)
{
int min = i;
for (j = i + 1; j < len; j++)
{
if (arry[j] < arry[min])
{
min = j;
}
}
int temp = arry[min];
arry[min] = arry[i];
arry[i] = temp;
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<endl<<endl;
cout<<"数组a中有";
MergeSort(a,0,n-1);
cout<<ans;
stable_sort(a,a+n);
cout<<"队逆序对";
cout<<endl<<endl;
RadixSort(a,n);
CountingSort(a,n);
ShellSort(a,n);
MergeFindSort(a,n);
InsertSort(a,n);
BubbleSort(a,n);
SelectSort(a,n);
QuickSort(a,0,n-1);
sort(a,a+n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
高精度：
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
**二维前缀和**：
```cpp
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
二维差分：
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
位运算：
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n
双指针：
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
快速幂
long long qmi(long long a,int b,int p)
{
long long res=1;
while(b),
{
if(b&1) res = res *a %p;
b>>=1;
a=a*a%p;
}
return res;
}
KMP：
给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串 P 在模式串 S 中多次作为子串出现。
求出模板串 P 在模式串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。
输出格式
共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。_
#include<iostream>
using namespace std;
const int N=100010,M=1000010;
char q[N],s[M];
int ne[N];//保存next数组
int main()
{
int n,m;
cin>>n>>q+1>>m>>s+1;//下标均从1开始
for(int i=2,j=0;i<=n;i++)
//j表示匹配成功的长度,i表示q数组中的下标,因为q数组的下标是从1开始的,只有1个时,一定为0,所以i从2开始
{
while(j&&q[i]!=q[j+1]) j=ne[j];
//如果不行可以换到next数组
if(q[i]==q[j+1]) j++;
//成功了就加1
ne[i]=j;
//对应其下标
}
//j表示匹配成功的长度,因为刚开始还未开始匹配,所以长度为0
for(int i=1,j=0;i<=m;i++)
{
while(j&&s[i]!=q[j+1]) j=ne[j];
//如果匹配不成功,则换到j对应的next数组中的值
if(s[i]==q[j+1]) j++;
//匹配成功了,那么j就加1,继续后面的匹配
if(j==n)//如果长度等于n了,说明已经完全匹配上去了
{
printf("%d ",i-j);
//因为题目中的下标从0开始,所以i-j不用+1;
j=ne[j];
//为了观察其后续是否还能跟S数组后面的数配对成功
}
}
return 0;
}
Trie树：
const int N = 100010, M=131+26;
int son[N][M], cnt[N], idx;
char str[N];
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串
void insert(char *str)
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i];
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;
}
// 查询字符串出现的次数
int query(char *str)
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i];
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int main()
{
int m;
cin >> m;
while(m--)
{
char op[2];
scanf("%s%s", op, str);
if(*op == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}
并查集：
(1)朴素并查集：
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
(2)维护size的并查集：
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集：
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
堆：
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)
{
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
一般哈希：
(1) 拉链法
int h[N], e[N], ne[N], idx;
// 向哈希表中插入一个数
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}
(2) 开放寻址法
int h[N];
// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}
字符串哈希：
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
邻接表：
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
树与图的遍历：
时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数
(1) 深度优先遍历
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
(2) 宽度优先遍历
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}
拓扑排序：
时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数
bool topsort()
{
int hh = 0, tt = -1;
// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n - 1;
}
朴素dijkstra算法：
时间复杂是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
堆优化版dijkstra：
时间复杂度 O(mlogn)O(mlogn), nn 表示点数，mm 表示边数
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离，second存储节点编号
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
Bellman-Ford算法：
时间复杂度 O(nm)O(nm), nn 表示点数，mm 表示边数
注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
比如：
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, M = 10010;
struct Edge {
int a;
int b;
int w;
} e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边
int bellman_ford() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i++) {//k次循环
memcpy(back, dist, sizeof dist);
for (int j = 0; j < m; j++) {//遍历所有边
int a = e[j].a, b = e[j].b, w = e[j].w;
dist[b] = min(dist[b], back[a] + w);
//使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
else return dist[n];
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
e[i] = {a, b, w};
}
int res = bellman_ford();
if (res == -1) puts("impossible");
else cout << res;
return 0;
}
spfa 算法（队列优化的Bellman- Ford算法）：
时间复杂度 平均情况下 O(m)O(m)，最坏情况下 O(nm)O(nm), nn 表示点数，mm 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
spfa判断图中是否存在负环：
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中
// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
// 不需要初始化dist数组
// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
floyd算法：
时间复杂度是 O(n3)O(n3), nn 表示点数
初始化：
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
朴素版prim算法：
时间复杂度是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数
int n; // n表示点数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == INF) return INF;
if (i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}
return res;
}
Kruskal算法：
时间复杂度是 O(mlogm)O(mlogm), nn 表示点数，mm 表示边数
int n, m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组
struct Edge // 存储边
{
int a, b, w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) // 如果两个连通块不连通，则将这两个连通块合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
染色法判别二分图：
时间复杂度是 O(n+m)O(n+m), nn 表示点数，mm 表示边数
int n; // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (color[j] == -1)
{
if (!dfs(j, !c)) return false;
}
else if (color[j] == c) return false;
}
return true;
}
bool check()
{
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (color[i] == -1)
if (!dfs(i, 0))
{
flag = false;
break;
}
return flag;
}
匈牙利算法：
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过
bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true;
if (match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}
return false;
}
// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}
STL速查手册：
vector,set,string,map,queue,priority_queue,stack,pair,bitset,algorithm
1. vector(动态数组)
vector 是向量类型，它可以容纳许多类型的数据，如若干个整数，所以称其为容器。vector 是C++ STL的一个重要成员，使用它时需要包含头文件：
#include<vector>;
一、vector 的初始化：可以有五种方式,举例说明如下：
(1) vector<int> a(10); //定义了10个整型元素的向量（尖括号中为元素类型名，它可以是任何合法的数据类型），但没有给出初值，其值是不确定的。
（2）vector<int> a(10,1); //定义了10个整型元素的向量,且给出每个元素的初值为1
（3）vector<int> a(b); //用b向量来创建a向量，整体复制性赋值
（4）vector<int> a(b.begin(),b.begin+3); //定义了a值为b中第0个到第2个（共3个）元素
（5）int b[7]={1,2,3,4,5,9,8};
vector<int> a(b,b+7); //从数组中获得初值
二、vector对象的几个重要操作，举例说明如下：
（1）a.assign(b.begin(), b.begin()+3); //b为向量，将b的0~2个元素构成的向量赋给a
（2）a.assign(4,2); //是a只含4个元素，且每个元素为2
（3）a.back(); //返回a的最后一个元素
（4）a.front(); //返回a的第一个元素
（5）a[i]; //返回a的第i个元素，当且仅当a[i]存在2013-12-07
（6）a.clear(); //清空a中的元素
（7）a.empty(); //判断a是否为空，空则返回ture,不空则返回false
（8）a.pop_back(); //删除a向量的最后一个元素
（9）a.erase(a.begin()+1,a.begin()+3); //删除a中第1个（从第0个算起）到第2个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+ 3（不包括它）
（10）a.push_back(5); //在a的最后一个向量后插入一个元素，其值为5
（11）a.insert(a.begin()+1,5); //在a的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4
（12）a.insert(a.begin()+1,3,5); //在a的第1个元素（从第0个算起）的位置插入3个数，其值都为5
（13）a.insert(a.begin()+1,b+3,b+6); //b为数组，在a的第1个元素（从第0个算起）的位置插入b的第3个元素到第5个元素（不包括b+6），如b为1,2,3,4,5,9,8 ，插入元素后为1,4,5,9,2,3,4,5,9,8
（14）a.size(); //返回a中元素的个数；
（15）a.capacity(); //返回a在内存中总共可以容纳的元素个数
（16）a.resize(10); //将a的现有元素个数调至10个，多则删，少则补，其值随机
（17）a.resize(10,2); //将a的现有元素个数调至10个，多则删，少则补，其值为2
（18）a.reserve(100); //将a的容量（capacity）扩充至100，也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才 显得有意义，因为这将避免内存多次容量扩充操作（当a的容量不足时电脑会自动扩容，当然这必然降低性能）
（19）a.swap(b); //b为向量，将a中的元素和b中的元素进行整体性交换
（20）a==b; //b为向量，向量的比较操作还有!=,>=,<=,>,<
三、顺序访问vector的几种方式，举例说明如下：
（1）向向量a中添加元素
vector<int> a;
for(int i=0;i<10;i++)
a.push_back(i);
2、也可以从数组中选择元素向向量中添加
int a[6]={1,2,3,4,5,6};
vector<int> b；
for(int i=1;i<=4;i++)
b.push_back(a[i]);
3、也可以从现有向量中选择元素向向量中添加
int a[6]={1,2,3,4,5,6};
vector<int> b;
vector<int> c(a,a+4);
for(vector<int>::iterator it=c.begin();it<c.end();it++)
b.push_back(*it);
4、也可以从文件中读取元素向向量中添加
ifstream in("data.txt");
vector<int> a;
for(int i; in>>i)
a.push_back(i);
5、【误区】
vector<int> a;
for(int i=0;i<10;i++)
a[i]=i;
//这种做法以及类似的做法都是错误的。下标只能用于获取已存在的元素，而现在的a[i]还是空的对象
（2）从向量中读取元素
1、通过下标方式读取
int a[6]={1,2,3,4,5,6};
vector<int> b(a,a+4);
for(int i=0;i<=b.size()-1;i++)
cout<<b[i]<<" ";
2、通过遍历器方式读取
int a[6]={1,2,3,4,5,6};
vector<int> b(a,a+4);
for(vector<int>::iterator it=b.begin();it!=b.end();it++)
cout<<*it<<" ";
四、几种重要的算法，使用时需要包含头文件：
#include<algorithm>
（1）sort(a.begin(),a.end()); //对a中的从a.begin()（包括它）到a.end()（不包括它）的元素进行从小到大排列
（2）reverse(a.begin(),a.end()); //对a中的从a.begin()（包括它）到a.end()（不包括它）的元素倒置，但不排列，如a中元素为1,3,2,4,倒置后为4,2,3,1
（3）copy(a.begin(),a.end(),b.begin()+1); //把a中的从a.begin()（包括它）到a.end()（不包括它）的元素复制到b中，从b.begin()+1的位置（包括它）开 始复制，覆盖掉原有元素
（4）find(a.begin(),a.end(),10); //在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，若存在返回其在向量中的位置
set
set翻译为集合，是一个内部自动有序且不含重复元素的容器。默认是升序。底层采用红黑树实现。
set的定义：set<’typename’> s，降序的定义方式为set<typename,greater<typename>> s。typename可以是任意类型包括STL容器。Set数组的定义方式为，set<typename> s[size].s[0]…s[size-1]都是set类型。迭代器的定义方式set<typename>::iterator it
set容器内元素的访问：set只能通过迭代器(iterator)访问。
set常用函数
（1） insert(x)可将x插入set容器中，并且自动递增排序和去重，时间复杂度O(logN),其中N是set中元素的数量。
（2） find（x）返回set中对应值为x的迭代器，时间复杂度O(logN),N为set内元素的个数。
（3） erase（），erase有两种用法：删除单个元素，删除一个区间内的所有元素。
删除单个元素有两种方式，erase(it)删除该迭代器对应的元素，时间复杂度O(1),erase(x)删除该元素,时间复杂度O(logN)
删除一个区间的元素，erase(st,ed),删除区间[st,ed)内的元素，时间复杂度O(ed-st)
（4） size(),用来获得set内元素的个数，时间复杂度O(1)
（5） clear(),用来清空set中所有元素，复杂度O(N),其中N为set内元素的个数。
（6） count(x),返回set中x的数量
set<int> st ;
st.insert(3) ;
st.insert(3) ;
st.insert(3) ;
st.insert(1) ;
st.insert(4) ;
st.insert(4) ;
st.insert(4) ;
st.insert(4) ;
st.insert(2) ;
st.insert(2) ;
cout << st.size() << endl ;
cout << st.count(4) << endl ;//set去重了，返回只能是0或1
cout << *st.find(1) << endl ;
st.erase(1) ;
st.erase(st.begin(),st.find(4)) ;
for(auto ele : st) cout << ele << ' ' ;
puts("") ;
st.clear() ;
cout << st.size() << endl ;
set的常见用途：
set最主要的作用是自动去重并且升序排序，因此碰到需要去重但不方便开数组的
时候，可以尝试用set解决。
注意：set中的元素是唯一的，如果需要处理不唯一的情况可以使用multiset。C++11中还增加了unordered_ set,以散列代替set内部的红黑树，unordered_set可以处理需要去重但是不需要排序的情况，速度比set快得多。Multiset和unordered_set的定义和常用函数和set类似。
3.string
C++STL中加入string类型，对字符串常用需求功能进行了封装，使得操作起来更方便，且不易出错。如果要使用string,需要添加string头文件，即#include<string>,注意string.h和string是不一样的头文件。除此之外要想使用string，还要在头文件下面加上一句“using namespace std”，这样就可以在代码中使用string了。
string的定义：
定义方式与基本数据类型相同，只需要在string后面跟上变量名称即可。
eg. string str;如果需要初始化，可以直接给string类型的变量赋值，string str = “hello”。
String中内容的访问：
(1) 通过下标访问，可以直接像字符数组那样去访问string
string str = "hello" ;
for(int i=0;i<str.size();i++){
printf("%c",str[i]) ;
}
输出结果:hello
如果用string读入和输出字符串一般只能用cin和cout，使用printf输出也是可以的，但是要先将string装换为字符数组进行输出
string str ;
cin >> str ;
cout << str << endl ;
printf("%s\n",str.c_str()) ;
return 0 ;
输入：hello
输出：hello
hello
(2) 通过迭代器访问，string的访问一般采用第一种方式，但是string有很多函数要求以迭代器为参数。string迭代器的定义方式为string::iterator it，可以使用*it来访问string中的每一位。String迭代器的使用方法与其他容器的迭代器的使用方法类似，string和vector一样，支持直接对迭代器进行加减某个数字。
示例：
string str = "hello" ;
string::iterator it ;
for(it = str.begin();it!=str.end();it++){
cout << *it ;
}
it = str.begin() ;
cout << endl ;
cout << *(it+1) << "<--->" << str[1] << endl ;
结果： hello
e<--->e
string常用函数：
string提供的函数有很多，这里紧介绍常用的string函数
（1） operator+=拼接
这是string的加法，可以将两个string直接拼接起来。
string str1 = "hello" ;
string str2 = " world" ;
cout << str1 + str2 << endl ;
结果：hello world
（2） compare operator比较
两个string类型可以直接使用==,!=,<,<=,>,>=比较大小，比较规则是字典序。
string str1 = "aa" ;
string str2 = "ab" ;
string str3 = "abc" ;
if(str1 != str2){
cout << "not same" << endl ;
}else{
cout << "same" << endl ;
}
if(str3>str2){
cout << "str3>str2" << endl ;
}
结果：not same
str3>str2
（3） length()/size()取得大小
length()返回string的长度，即string存放的字符数，时间复杂度O(1)。size()和length()基本相同。
string str1 = "hello" ;
cout << str1.size() << ' ' << str1.length() << endl ;
结果：5 5
（4） insert（）插入（原字符串不会被覆盖）
insert()函数有很多种写法，这里列出几个常用的写法，时间复杂度度O(N)。
insert(pos,string)，在pos号位置插入string。
insert(it,it1,it2)，it为原字符串欲插入的位置，it2和it3为待插字符串的首尾迭代器，用来表示串[it1,it2)将被插在it的位置上。
string str1 = "hello world" ;
string str2 = "Maric" ;
str1.insert(str1.begin()+5,str2.begin(),str2.end()) ;
cout << str1 << endl ;
str2.insert(5,"hello") ;
cout << str2 << endl ;
结果：helloMaric world
Marichello
（5） erase()删除
erase()有两种用法，删除单个元素，上出一个区间内所有元素。时间复杂度O(N)。
a． erase(it)用于删除单个元素，it为需要删除的元素的迭代器。
b. 删除一个区间的元素有两种方法：
第一种是erase(st,ed),st，ed为string迭代器，表示删除区间[st,ed)之间的元素。
第二种是erase(pos,len)，其中pos为需要删除的起始位置，len为删除的字符个数。
string str1 = "hello world" ;
str1.erase(str1.begin()) ;
cout << str1 << endl ;
str1.erase(str1.begin()+5,str1.end()) ;
cout << str1 << endl ;
str1.erase(1,2) ;
cout << str1 << endl ;
结果：ello world
ello
eo
（6） clear()清空
clear()函数用来清空string中的数据，时间复杂度O(1)。
string str1 = "hello world" ;
cout << str1.length() << endl ;
str1.clear() ;
cout << str1.size() << endl ;
结果：11
0
（7） substr()截取子串
substr(pos,len)返回的是以pos位开始长度为len的子串，时间复杂度O(len)。
string str1 = "hello world" ;
cout << str1.substr(6,5) << endl ;
结果：world
（8） string::npos
npos 是一个常数，用来表示不存在的位置，类型一般是std::container_type::size_type 许多容器都提供这个东西。取值由具体实现决定，一般是-1，但是由于是unsigned_int类型，也可以认为是unsigned_int类型的最大值，这样做，就不会存在移植的问题了。
不建议将find的返回值作为是否匹配的依据。最好使用示例的使用方式。npos主要是和find()函数搭配使用，用以作为find()函数失配时的返回值，举个例子具体解释一下：
if (a.find(b) != string::npos) {
cout << "Yes!" << endl;
} else {
cout << "No!" << endl;
}
（9） find()查找
str.find(str1),当str1是str的子串时，返回其在str中第一次出现的位置。如果str1不是str的子串，那么返回string::npos
str.find(str1,pos),从str的pos号位开始匹配str1,返回值与上面的相同，时间复杂度为O(nm),其中n和m分别为str和str1的长度。
string str1 = "hello world" ;
string str2 = "world" ;
if(str1.find(str2) != string::npos){
cout << str1.find(str2) << endl ;
cout << str1.find(str2,3) << endl ;
}else{
cout << "match failure" << endl ;
}
结果：6
6
小结：find函数的返回值是整数，假如字符串存在包含关系，其返回值必定不等于npos，但如果字符串不存在包含关系，那么返回值就一定是npos。
（10） replace()
str.replace(pos,len,str1),把str从pos号位开始，长度为len的子串替换为str1。
str.replace(it1,it2,str1)把str的迭代器[it1,it2)替换为str1
string str1 = "hello world" ;
string str2 = "kangkang" ;
cout << str1.replace(6,5,str2) << endl ;
cout << str1.replace(str1.begin()+6,str1.end(),str2) << endl ;
结果：hello kangkang
hello kangkang
map
map翻译成映射，map可以将任何基本类型（包括STL容器）映射到任何基本类。（包括STL容器）。如要使用map，需要添加map头文件，并在头文件底下加上“using namespace std”,这样就可以在代码中使用map了。
map的定义，map[HTML_REMOVED] mp;map和其他STL容器的定义上有点不同，因为map需要确定映射前类型（键key）和映射后类型（值value）,map存储的数据类型是一对K-V结构的数据。如果map是字符串到整型的映射，必须使用string而不能使用char数组。
map的访问，map一般有两种访问方式，通过“下标”访问或者通过迭代器访问。
（1） 通过“下标”访问，和普通数组的访问方式一样。比如，定义了一个map[HTML_REMOVED] mp;的map，可以使用mp[“hello”] = 8的方式向map中添加数据，用mp[“hello”]访问map中键为“hello”的值。map中的键是唯一的，可以观察下面代码的输出。
unordered_map<string,int> um ;
um["hello"] = 8 ;
um["hello"] = 100 ;
cout << um["hello"] << endl ;
输出：100
（2） 通过迭代器访问，与其他STL迭代器有点不同，由于map的数据类型是K-V结构，因此迭代器包含了这两方面的数据。map迭代器的定义方式为map[HTML_REMOVED]::iterator it;可以通过it->first来访问键，it->second来访问值。观察下面的代码，
map<string,int> mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++){
cout << it->first << ' ' << it->second << endl ;
}
输出结果：aloha 666
good 777
hello 100
观察输出结果，很有意思的是map按照键值从小到大排序了，如果是字符串，则按照字典序排序。map是采用红黑树来实现的。
map的常用函数：
（1） find（key），返回键为key的映射的迭代器，时间复杂度为O(logN)，N为map中映射的个数。
map<string,int> mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
auto it = mp.find("good") ;
cout << it->first << ' ' << it->second << endl ;
输出结果：good 777
（2） erase(),erase()有两种用法：删除单个元素和删除一个区间内的元素。
a． 删除单个元素，删除单个元素也有两种方法
mp.erase(it)，it为需要删除的元素的迭代器，时间复杂度O(1)。
map<string,int> mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
mp.erase(mp.find("good"));
for(auto ele : mp){
cout << ele.first << ' ' << ele.second << endl ;
}
输出结果：aloha 666
hello 100
mp.erase(key)，key为欲删除的映射的键。时间复杂度O(logN)。N为map中元素的个数。
map<string,int> mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
mp.erase("good");
for(auto ele : mp){
cout << ele.first << ' ' << ele.second << endl ;
}
输出结果：aloha 666
hello 100
b. 删除一个区间的元素，这里只能用迭代器删除，erase(st,ed),表示删除[st,ed)区间内的元素。
map<string,int> mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
mp.erase(mp.find("good"),mp.find("hello"));
for(auto ele : mp){
cout << ele.first << ' ' << ele.second << endl ;
}
输出结果：aloha 666
hello 100
注意，st的迭代器位置必须在ed之前。
map<string,int> mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
mp.erase(mp.find("good"),mp.find("good"));
for(auto ele : mp){
cout << ele.first << ' ' << ele.second << endl ;
}
输出结果：aloha 666
good 777
hello 100
其实是什么也没有删除。
（3） size(),用来获得map中映射的对数，时间复杂度O(1)。
map<string,int> mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
cout << mp.size() << endl ;
输出结果：3
（4） clear()，用来清空map中所有元素，复杂度为O(N)，其中N为map中元素的个数。
map<string,int> mp ;
mp["hello"] = 8 ;
mp["hello"] = 100 ;
mp["aloha"] = 666 ;
mp["good"] = 777 ;
mp.clear() ;
cout << mp.size() << endl ;
输出结果：0
map的常见用途：
（1） 需要建立字符（或字符串）与整数之间映射的题目，使用map可以减少代码量。
（2） 判断大整数或者其他类型数据是否存在的题目，可以把map当成bool数组用。
（3） 字符串和字符串之间的映射。
补充：map和键和值都是唯一的，而如果一个键需要对应多个值，就只能使用multimap。另外，C++11标准中还增加了unordered_map,以散列代替map内部的红黑树实现，使其可以用来处理映射而不需要按key排序的需求，速度比map快很多。
5. queue
queue就是队列，在STL中是实现了一个先进先出的容器，要使用queue，需要在加上queue这个头文件。
queue的定义，queue<typename> q;其中typename可以为任何类型或容器。
queue的访问，由于队列是一种先进先出的限制性数据结构，因此在STL中只能通过front()来访问队首元素，或是通过back()来访问队尾元素。
queue<`int`> q ;
for(int i=1;i<5;i++){
q.push(i) ;
}
cout << q.front() << endl ;
cout << q.back() << endl ;
输出结果：1
4
Queue常用函数
（1） push(),push(x)将x入队，时间复杂度O(1)
（2） front(),访问队首元素,back()访问队尾元素，时间复杂度O(1)。
（3） pop(),令队首元素出队，时间复杂度O(1)。
queue<int> q ;
for(int i=1;i<5;i++){
q.push(i) ;
}
q.pop() ;
cout << q.front() << endl ;
cout << q.back() << endl ;
输出结果：2
4
（4） empty(),判断队列是否为空，如果是空则返回true，否则返回false。
（5） size(),返回queue内元素的个数，时间复杂度为O(1)。
queue<int> q ;
for(int i=1;i<5;i++){
q.push(i) ;
}
if(!q.empty()){
cout << q.size() ;
}
输出结果：4
Queue的常见用途：
当需要实现广度优先搜索时，可以不用自己手工实现一个队列。在使用front()和pop()函数前，必须使用empty()判断队列是否为空，否则可能因为队空而出现错误。
priority_queue
priority_queue又称优先队列，其底层是用堆来进行实现的。在优先队列中，队首的元素一定是当前队列中优先级最高的那一个。C++中的堆默认是大跟堆。
priority_queue的定义，priority_queue<typename> q,typename可以为任意类型的元素。要使用优先队列，应先添加头文件#include[HTML_REMOVED]。
Priority_queue只能通过top()函数来访问队首元素(堆顶元素)，也就是优先级最高的元素。
priority_queue<int> q ;
q.push(3) ;
q.push(1) ;
q.push(5) ;
cout << q.top() << endl ;
输出结果：5
Priority_queue常用函数
（1） push(x)，时间复杂度O(logN),N是堆中元素的个数。
（2） top(),top()可以获得队首元素，时间复杂度O(1)
（3） pop(),令堆顶元素出队，时间复杂度O(logN),其中N是堆中的元素个数。
priority_queue<int> q ;
q.push(3) ;
q.push(1) ;
q.push(5) ;
cout << q.top() << endl ;
q.pop() ;
cout << q.top() << endl ;
输出结果：5
3
（4） empty(),判断队列是否为空，为空返回true，否则返回false。
（5） size(),返回优先队列中元素的个数，时间复杂度O(1)
priority_queue<int> q ;
q.push(3) ;
q.push(1) ;
q.push(5) ;
if(!q.empty()){
cout << q.size() << endl ;
}
输出结果：3
Priority_queue内元素的优先级设置
如何定义优先队列内元素的优先级是运用好优先队列的关键，下面分别介绍几本数据类型和结构体类型的优先级设置方法。
（1）基本数据类型的优先级设置
基本数据类型的优先级设置方法是类似的，这里用int举例。在C++中默认情况下是大根堆，所以下面两种优先队列的定义是等价的。
Priority_queue<int> q,priority_queue<int,vector<int>,less<int>> q;
可以发现第二种定义方式，后面多了两个参数，一个是vector<int>,另一个是less<int>。其中vector<int>填写的是来承载底层数据结构heap(堆)的容器；第三个参数less<int>则是对第一个参数的比较类，less[HTML_REMOVED]表示数字越大优先级越高，而greater<int>表示数字越小的优先级越大。因此，C++中定义小根堆的方式是,priority_queue<int,vector<int>,greater<int>> q。
priority_queue<int,vector<int>,greater<int>> q ;
q.push(3) ;
q.push(1) ;
q.push(5) ;
cout << q.top() << endl ;
输出结果：1
（2） 结构体的优先级设置
对结构体进行优先级设置有两种方式，第一种是在结构体内部重载小于号“<”，第二种方式是在结构体外部重载“()”,下面对这两种情况分别举个例子来说明
重载小于号“<”
struct fruit{
string name ;
int price ;
friend bool operator < (fruit f1,fruit f2){
return f1.price > f2.price ;
}
};
priority_queue<fruit> q ;
q.push({"apple",8}) ;
q.push({"orange",7}) ;
q.push({"banana",9}) ;
auto ele = q.top() ;
cout << ele.name << ' ' << ele.price << endl ;
输出结果：orange 7
这种情况下优先队列只能采用第一种定义方式。
重载小括号“()”
struct fruit{
string name ;
int price ;
};
struct cmp{
bool operator () (fruit f1,fruit f2){
return f1.price > f2.price ;
}
};
int main(){
priority_queue<fruit,vector<fruit>,cmp> q ;
q.push({"apple",8}) ;
q.push({"orange",7}) ;
q.push({"banana",9}) ;
auto ele = q.top() ;
cout << ele.name << ' ' << ele.price << endl ;
return 0 ;
}
输出结果：orange 7
这里的优先队列只能采用第二种定义方式。
小结，即使是基本数据类型或者STL容器，也可以通过同样的方式来定义优先级。
注意：如果结构体内的数据比较庞大，建议使用引用来提高效率，此时比较类的参数中需要加上“const”和“&”，如下所示：
friend bool operator < (const fruit& f1,cosnt fruit& f2){
return f1.price > f2.price ;
}
bool operator () (const fruit& f1,const fruit& f2){
return f1.price > f2.price ;
}
Priority_queue的常见用途
Priority_queue可以解决一些贪心问题，也可以对dijkstra进行优化(因为优先队列的本质是堆)，在使用top()函数前，必须用empty()判断优先队列是否为空。
stack
Stack翻译为栈，是STL中实现一个后进先出的容器。
Stack的定义，stack<typename> name要使用stack需要加上头文件#include<stack>。
Stack容器内元素的访问，由于栈本身就是一种后进先出的数据结构，在STL的stack中只能通过top()来访问栈顶元素。
stack<int> s ;
s.push(3) ;
s.push(1) ;
s.push(2) ;
s.push(5) ;
s.push(4) ;
cout << s.top() << endl ;
输出结果：4
Stack常用函数
（1） push(x),将x压入栈中，时间复杂度O(1)
（2） top()，获得栈顶元素，时间复杂度O(1)
（3） pop(),将栈顶元素弹出，时间复杂度O(1)
stack<int> s ;
s.push(3) ;
s.push(1) ;
s.push(2) ;
s.push(5) ;
s.push(4) ;
cout << s.top() << endl ;
s.pop() ;
cout << s.top() << endl ;
输出结果：4
5
（4） empty()判断栈是否为空，若为空，返回true，否则返回false，时间复杂度O(1)
（5） size()返回栈中元素的个数，时间复杂度O(1)
stack<int> s ;
s.push(3) ;
s.push(1) ;
s.push(2) ;
s.push(5) ;
s.push(4) ;
if(!s.empty()){
cout << "栈的大小：" << s.size() << endl ;
}
输出结果：栈的大小：5
Stack的常见用途，stack用来模拟实现一些递归，防止程序对栈内存的限制而导致程序运行出错。
pair
pair是个很实用的数据结构，当想要将两个元素绑在一起作为一个合成元素，又不想定义一个结构体的时候，可以使用pair。Pair的本质就是含有两个类型的结构体，这两个类型可以任意指定。
pair的定义，pair<typename,typename> name,要使用pair，需要添加#incldue <utility>的头文件，map的头文件里也包含pair。Pair有两个参数，一个是first，一个是second分别对应pair中的2个元素的类型。
如果想在定义pair的时候初始化pair，只需要跟上一个小括号，里面填写两个想要初始化的元素即可，pair<string,int> name(“hello”,888)。
如果想要临时创建一个pair，可采用下面的两种方式，
Pair<string,int>(“haha”,55),make_pair(“haha”,55)。
Pair中元素的访问，pair中只有两个元素first和second，只需要按照结构体的方式去访问即可。
pair<string,int> p ;
p.first = "haha" ;
p.second = 55 ;
cout << p.first << ' ' << p.second << endl ;
p = make_pair("hehe",66) ;
cout << p.first << ' ' << p.second << endl ;
p = pair<string,int>("wuwu",77) ;
cout << p.first << ' ' << p.second << endl ;
输出结果：haha 55
hehe 66
wuwu 77
pair常用函数
比较操作数
两个pair类型的数据比较可以直接使用==,!=,<,<=,>,>=比较大小，比较的规则是先比较first，在比较second。
pair<string,int> q1,q2,q3 ;
q1 = make_pair("a",88) ;
q2 = make_pair("a",99) ;
q3 = make_pair("b",77) ;
if(q3 > q1) cout << "q3>q1" << endl ;
if(q2 > q1) cout << "q2>q1" << endl ;
输出结果：q3>q1
q2>q1
pair的常见用途
（1） 可以用来代替二元结构体及其构造函数，节省编码时间。
（2） 作为map的键值对来进行插入。
map<string,int> mp ;
mp.insert({"haha",888}) ;
mp.insert(make_pair("hehe",777)) ;
mp.insert(pair<string,int>("wuwu",666)) ;
for(map<string,int>::iterator it = mp.begin();it != mp.end();it++){
cout << it->first << ' ' << it->second << endl ;
}
输出结果：haha 888
hehe 777
wuwu 666
bitset
C++的 bitset 在 bitset 头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。
下面是具体用法
构造函数
bitset常用构造函数有四种，如下
bitset<4> bitset1; //无参构造，长度为４，默认每一位为０
bitset<8> bitset2(12); //长度为８，二进制保存，前面用０补充
string s = "100101";
bitset<10> bitset3(s); //长度为10，前面用０补充
char s2[] = "10101";
bitset<13> bitset4(s2); //长度为13，前面用０补充
cout << bitset1 << endl; //0000
cout << bitset2 << endl; //00001100
cout << bitset3 << endl; //0000100101
cout << bitset4 << endl; //0000000010101
注意：
用字符串构造时，字符串只能包含 ‘0’ 或 ‘1’ ，否则会抛出异常。
构造时，需在<>中表明bitset 的大小(即size)。
在进行有参构造时， 若参数的二进制表示长度比bitset的size小，则在前面用０补充(如上面的栗子)；若比bitsize大，参数为整数时取后面部分，参数为字符串时取前面部分(如下面栗子) ：
bitset<2> bitset1(12); //12的二进制为1100（长度为４），但bitset1的size=2，只取后面部分，即00
string s = "100101";
bitset<4> bitset2(s); //s的size=6，而bitset的size=4，只取前面部分，即1001
char s2[] = "11101";
bitset<4> bitset3(s2); //与bitset2同理，只取前面部分，即1110
cout << bitset1 << endl; //00
cout << bitset2 << endl; //1001
cout << bitset3 << endl; //1110
可用的操作符
bitset对于二进制有位操作符，具体如下
bitset<4> foo (string("1001"));
bitset<4> bar (string("0011"));
cout << (foo^=bar) << endl; // 1010 (foo对bar按位异或后赋值给foo)
cout << (foo&=bar) << endl; // 0010 (按位与后赋值给foo)
cout << (foo|=bar) << endl; // 0011 (按位或后赋值给foo)
cout << (foo<<=2) << endl; // 1100 (左移２位，低位补０，有自身赋值)
cout << (foo>>=1) << endl; // 0110 (右移１位，高位补０，有自身赋值)
cout << (~bar) << endl; // 1100 (按位取反)
cout << (bar<<1) << endl; // 0110 (左移，不赋值)
cout << (bar>>1) << endl; // 0001 (右移，不赋值)
cout << (foo==bar) << endl; // false (0110==0011为false)
cout << (foo!=bar) << endl; // true (0110!=0011为true)
cout << (foo&bar) << endl; // 0010 (按位与，不赋值)
cout << (foo|bar) << endl; // 0111 (按位或，不赋值)
cout << (foo^bar) << endl; // 0101 (按位异或，不赋值)
此外，可以通过 [ ] 访问元素(类似数组)，注意最低位下标为 ０ ，如下：
bitset<4> foo ("1011");
cout << foo[0] << endl; //1
cout << foo[1] << endl; //1
cout << foo[2] << endl; //0
当然，通过这种方式对某一位元素赋值也是可以的，栗子就不放了。
可用函数
bitset还支持一些有意思的函数，比如：
bitset<8> foo ("10011011");
cout << foo.count() << endl; //5 （count函数用来求bitset中1的位数，foo中共有５个１
cout << foo.size() << endl; //8 （size函数用来求bitset的大小，一共有８位
cout << foo.test(0) << endl; //true （test函数用来查下标处的元素是０还是１，并返回false或true，此处foo[0]为１，返回true
cout << foo.test(2) << endl; //false （同理，foo[2]为０，返回false
cout << foo.any() << endl; //true （any函数检查bitset中是否有１
cout << foo.none() << endl; //false （none函数检查bitset中是否没有１
cout << foo.all() << endl; //false （all函数检查bitset中是全部为１
补充说明一下：test函数会对下标越界作出检查，而通过 [ ] 访问元素却不会经过下标检查，所以，在两种方式通用的情况下，选择test函数更安全一些
另外，含有一些函数：
bitset<8> foo ("10011011");
cout << foo.flip(2) << endl; //10011111 （flip函数传参数时，用于将参数位取反，本行代码将foo下标２处"反转"，即０变１，１变０
cout << foo.flip() << endl; //01100000 （flip函数不指定参数时，将bitset每一位全部取反
cout << foo.set() << endl; //11111111 （set函数不指定参数时，将bitset的每一位全部置为１
cout << foo.set(3,0) << endl; //11110111 （set函数指定两位参数时，将第一参数位的元素置为第二参数的值，本行对foo的操作相当于foo[3]=0
cout << foo.set(3) << endl; //11111111 （set函数只有一个参数时，将参数下标处置为１
cout << foo.reset(4) << endl; //11101111 （reset函数传一个参数时将参数下标处置为０
cout << foo.reset() << endl; //00000000 （reset函数不传参数时将bitset的每一位全部置为０
同样，它们也都会检查下标是否越界，如果越界就会抛出异常
最后，还有一些类型转换的函数，如下：
bitset<8> foo ("10011011");
string s = foo.to_string(); //将bitset转换成string类型
unsigned long a = foo.to_ulong(); //将bitset转换成unsigned long类型
unsigned long long b = foo.to_ullong(); //将bitset转换成unsigned long long类型
cout << s << endl; //10011011
cout << a << endl; //155
cout << b << endl; //155
10.algorithm
使用algorithm头文件，需要在头文件下面加一行“using namespace std”，才能使用。
algorithm的常用函数
（1） max(),min(),abs()
max(x,y)和min(x,y)分别返回x和y的最大值和最小值，且参数必须是两个（可以是浮点数），如果要返回三个数x,y,z的最大值，可以使用max(max(x,y),z)的写法。abs(x)返回x的绝对值。注意，x必须是整数，浮点型的绝对值要用math头文件下的fabs。
int x = -1, y = 2 ;
cout << max(x,y) << ' ' << min(x,y) << endl ;
cout << abs(x) << ' ' << abs(y) << endl ;
输出结果：2 -1
1 2
（2） swap()
swap(x,y)用来交换x和y的值
int x = 3, y = 5 ;
swap(x,y) ;
cout << "x = " << x << ",y = " << y << endl ;
输出结果：x = 5,y = 3
（3） reverse()
reverse(it1，it2)可以将数组指针或者容器的迭代器在[it1,it2)范围内的元素进行反转。
int v1[] = {3,1,2,5,4} ;
vector<int> v2(v1,v1+5) ;
reverse(v1,v1+5) ;
reverse(v2.begin(),v2.begin()+2) ;
for(auto ele : v1) cout << ele << ' ' ;
cout << endl ;
for(auto ele : v2) cout << ele << ' ' ;
cout << endl ;
输出结果：4 5 2 1 3
1 3 2 5 4
（4） next_permutation()
next_permutation()给出一个序列全排列中的下一个序列。使用的方式和reverse类似。
例如，当n==3时的全排列为
123,132,213,231,312,321，这样231的下一个序列就是312。
int a[] = {1,2,3} ;
do{
cout << a[0] << a[1] << a[2] << endl ;
}while(next_permutation(a,a+3)) ;
输出结果：123
132
213
231
312
321
注意，这里要用do..while否则输出的结果中会少123这种情况。
（5） fill()
fill()函数可以把数组或者容器中的某一段区域赋为某个相同的值。和memset不同的是，这里的赋值可以是和数组类型对应范围中的任意值。
int a[] = {3,1,2,5,4} ;
fill(a,a+2,888) ;
for(auto e : a) cout << e << ' ' ;
cout << endl ;
输出结果：888 888 2 5 4
（6） sort()
sort()是用来排序的。sort()的使用方式是，sort(首元素地址(必填)，尾元素地址的下一个地址(必填)，比较函数(非必填))。如果不写比较函数，则默认对给出的区间进行递增排序。
int a[] = {3,1,2,5,4} ;
sort(a,a+2) ;
for(auto e : a) cout << e << ' ' ;
puts("") ;
sort(a,a+5) ;
for(auto e : a) cout << e << ' ' ;
cout << endl ;
输出结果：1 3 2 5 4
1 2 3 4 5
实现从大到小排序(char,doubel等基本类型与int类似)
bool cmp(int a,int b){
return a>b ;
}
int main(){
int a[] = {3,1,2,5,4} ;
sort(a,a+2,cmp) ;
for(auto e : a) cout << e << ' ' ;
puts("") ;
sort(a,a+5,cmp) ;
for(auto e : a) cout << e << ' ' ;
cout << endl ;
return 0 ;
}
输出结果：3 1 2 5 4
5 4 3 2 1
结构体的排序，具体看cmp的编写方式。
const int N = 5 ;
struct point{
int x,y ;
}a[N];
bool cmp(point a,point b){
return a.x>b.x ;
}
int main(){
a[0].x = 2 ;
a[0].y = 3 ;
a[1].x = 1 ;
a[1].y = 4 ;
a[2].x = 2 ;
a[2].y = 5 ;
sort(a,a+3,cmp) ;
for(int i=0;i<3;i++){
printf("%d %d\n",a[i].x,a[i].y) ;
}
return 0 ;
}
输出结果：2 3
2 5
1 4
如果要按照x从大到小排序，在x相等的时候按照y从小到大排序。
struct point{
int x,y ;
}a[N];
bool cmp(point a,point b){
if(a.x != b.x) return a.x > b.x ;
else return a.y < b.y ;
}
int main(){
a[0].x = 2 ;
a[0].y = 3 ;
a[1].x = 1 ;
a[1].y = 4 ;
a[2].x = 2 ;
a[2].y = 5 ;
sort(a,a+3,cmp) ;
for(int i=0;i<3;i++){
cout << a[i].x << " " << a[i].y << endl ;
}
return 0 ;
}
输出结果：2 3
2 5
1 4
最后举个很有意思的栗子，怎么样实现按照字符串的长度排序。
bool cmp(string str1,string str2){
return str1.size() < str2.size() ;
}
int main(){
string a[] = {"cccc","zz","bbb","aa"} ;
sort(a,a+4,cmp) ;
for(int i=0;i<4;i++){
cout << a[i] << endl ;
}
return 0 ;
}
输出结果：zz
aa
bbb
cccc
实现了按照字符串的长度排序，但是如果当长度相同按字典序排，如何实现？
bool cmp(string str1,string str2){
if(str1.size() != str2.size()) return str1.size() < str2.size() ;
else return str1 < str2 ;
}
int main(){
string a[] = {"cccc","zz","bbb","aa"} ;
sort(a,a+4,cmp) ;
for(int i=0;i<4;i++){
cout << a[i] << endl ;
}
return 0 ;
}
输出结果：aa
zz
bbb
cccc
（7） lower_bound()和upper_bound()
lower_bound()和upper_bound()需要用在一个有序数组或者容器中。
Lower_bound(st,ed,val)用来寻找在数组或者容器中的[st,ed)范围内第一个值大于等于val的元素的位置，如果是数组，则返回该位置的指针，如果是容器则返回该位置的迭代器。
Upper_bound(st,ed,val)用来寻找在数组或者容器中的[st,ed)范围内的第一个大于val的元素的位置，如果是数组，则返回该位置的指针，如果是容器，则返回该位置的迭代器。
int a[10] = {1,2,2,3,3,3,5,5,5,5} ;
//search -1
int* lp = lower_bound(a,a+10,-1) ;
int* up = upper_bound(a,a+10,-1) ;
cout << lp - a << ' ' << up - a << endl ;
//search 1
lp = lower_bound(a,a+10,1) ;
up = upper_bound(a,a+10,1) ;
cout << lp - a << ' ' << up - a << endl ;
//search 3
lp = lower_bound(a,a+10,3) ;
up = upper_bound(a,a+10,3) ;
cout << lp - a << ' ' << up - a << endl ;
//search 4
lp = lower_bound(a,a+10,4) ;
up = upper_bound(a,a+10,4) ;
cout << lp - a << ' ' << up - a << endl ;
//search 6
lp = lower_bound(a,a+10,6) ;
up = upper_bound(a,a+10,6) ;
cout << lp - a << ' ' << up - a << endl ;
输出结果：0 0
0 1
3 6
6 6
10 10
如果想要获得数组中欲查元素的下标，可以直接令lower_bound()和upper_bound()的返回值减去数组的首地址即可。如果查找的对象是容器，则返回的是对应的迭代器。
