高精度：

// 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;
}

一维前缀和：

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和：

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]

一位差分：

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

二维差分：

给以(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) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

单链表：

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

双链表：

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a    
void remove(int a)
{   
      l[r[a]] = l[a];
    r[l[a]] = r[a];
}

快速幂

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树：

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        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] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

并查集：

(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 ++ ;
} 

树

树：有n个点，只有n-1条边，且没有自环。任意两个点联通，且只有唯一一条路径。
根：在树中位于最上方，并且没有祖先。
儿子：由父亲的节点。

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()的返回值减去数组的首地址即可。如果查找的对象是容器，则返回的是对应的迭代器。 

优化

#pragma GCC target("avx")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

模板

/*
#pragma GCC target("avx")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
*/

#include<bits/stdc++.h>
#define ULL unsigned long long
#define dd double
#define int long long
using namespace std;



template<typename type>
inline void read(type &x){x=0;bool flag(0);char ch=getchar();while(!isdigit(ch)) flag=ch=='-',ch=getchar();while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();flag?x=-x:0;}
template<typename type>
inline void write(type x,int flag){x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);do Stack[++top]=x%10,x/=10; while(x);while(top) putchar(Stack[top--]|48);if(flag==0);else if(flag==1){putchar(' ');}else {puts("");}}
/*
template<typename T> inline T read() {T X = 0; bool flag = 1; char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') flag = 0; ch = getchar();}while (ch >= '0' && ch <= '9') {X = (X << 1) + (X << 3) + ch - '0'; ch = getchar();}if (flag) return X;return ~ (X - 1);}
template<typename T> inline void write(T X) {if (X < 0) {putchar('-'); X = ~ (X - 1);}int s[50], top = 0;while (X) {s[++top] = X % 10; X /= 10;}if (!top) s[++top] = 0;while (top) putchar(s[top--] + '0');putchar('\n');return;}
*/

signed main()
{
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);



    return 0;
}