考前知识总结

想到哪写到哪

  • C++ 常用库函数

    lower_bound/upper_bound（可用于二分）

    1
    2
    3
    4
    5

    ```upper_bound```会找出序列中第一个大于x的数

    ```cpp
    lower_bound(a + 1, a + 1 + n, x);

    同样的，lower_bound和upper_bound也是可以加比较函数cmp的：

    1
    lower_bound(a + 1, a + 1 + n, x, cmp);

    它们俩使用的前提是一样的：序列是有序的

    如果要在一个下降序列里寻找一个小于x的数

    只需要把比较器改成”>”：

    1
    2
    3
    4
    lower_bound(a + 1, a + 1 + n, x, cmp);

    bool cmp(const int& a,const int& b){return a > b;}

    或者

    1
    lower_bound(a + 1, a + 1 + n, x, greater <int> () );
    1
    2
    3
    4
    5
    6
    7

    它们的实现方式是二分查找

    返回值为指针，对于返回值我们有两种处理方式：

    ```cpp
    int p = lower_bound(···) - a;

    那么a[p]就是要找的y

    1
    int *p = lower_bound(···);

next_permutation

#include<algorithm>

1.next_permutation 下一个排列

函数模板：next_permutation(arr, arr+size);

数组名 ```size```：数组元素个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

优点：遍历一个**不重数组**的接下来全排列

2.```prev_permutation```上一个排列

函数模板：```prev_permutation(arr, arr+size);```

```arr```： 数组名 ```size```：数组元素个数

优点：遍历一个**不重数组**的之前的全排列



> ## ```sscanf/sprintf```

```sscanf()```的作用是从字符数组中读入

同样也可以利用```sprintf()```将数据输入到```sprintf()```。
    
```sscanf()/sprintf()```的用法与
```scanf()/printf```相同，只是在参数中第一个加个字符数组。

```cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
int day, year;
char weekday[20], month[20], dtm[100];

strcpy( dtm, "Saturday March 25 1989" );
sscanf( dtm, "%s %s %d  %d", weekday,month, &day, &year );

printf("%s %d, %d = %s\n", month, day,year, weekday );
        
return(0);
}

string 类型 基本运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <string>
    
 using namespace std;
    
int main ()
{
string str1 = "runoob";
string str2 = "google";
string str3;
int  len ;
    
// 复制 str1 到 str3
str3 = str1;
cout << "str3 : " << str3 << endl;
    
// 连接 str1 和 str2
str3 = str1 + str2;
cout << "str1 + str2 : " << str3 << endl;

// 连接后，str3 的总长度
len = str3.size();
cout << "str3.size() :  " << len << endl;
    
return 0;
}

当上面的代码被编译和执行时，它会产生下列结果：

1
2
3
str3 : runoob
str1 + str2 : runoobgoogle
str3.size() :  12

string 类型常用函数

1. strcpy(s1, s2);

复制字符串 s2 到字符串 s1。

2. strcat(s1, s2);

连接字符串 s2 到字符串 s1 的末尾。连接字符串也可以用 + 号，例如:

1
2
3
string str1 = "runoob";
 string str2 = "google";
string str = str1 + str2;

3. strlen(s1);

返回字符串 s1 的长度。

4. strcmp(s1, s2);

如果 s1 和 s2 是相同的，则返回 0；如果 s1<s2 则返回值小于 0；如果 s1>s2 则返回值大于 0。

5. strchr(s1, ch);

返回一个指针，指向字符串 s1 中字符 ch 的第一次出现的位置。

6. strstr(s1, s2);

返回一个指针，指向字符串 s1 中字符串 s2 的第一次出现的位置。

  • C++ STL 常用基础数据结构模板

    线性表数据结构(stack ,queue, vector)

    集合数据结构(set , multiset(作为映射表，平衡树))

    树形数据结构(priority_queue)及其重载运算符

  • 基础算法模板

    高精度算法（加法，乘法）结构体封装

    DFS, BFS模板，记忆化搜索

    二分查找，二分答案

  • 进阶优化算法

    前缀和， 差分，（树上）

    离散化

    倍增算法

  • 高阶数据结构模板

    树状数组，ST表，线段树(基础RMQ问题)

    1.ST

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void init(){
        log2[0] = -1;
        for (int i = 1; i <= n;i++)
            log2[i] = log2[i >> 1] + 1;
        for (int j = 1; j <= 21;j++)
            for (int i = 1; i + (1 << j) - 1 <= n;i++)
                f[i][j] = max(f[i][j - 1], f[i + (1 << (j-1))][j - 1]);
    }

    int query(int l,int r){
        int k = log2[r - l + 1];
        return max(f[l][k], f[r - (1 << k) + 1][k]);
    }

    2.树状数组

    (1). 单点修改，区间查询

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
        int lowbit(int x){
        return x & (-x);
    }

    void update_dot(int x,int y){
        for (; x <= n;x+=lowbit(x))
            c[x] += y;
    }

    int sum(int x){     //查询前缀和
        int ans = 0;
        for (; x; x -= lowbit(x))
            ans += c[x];
        return ans;
    }

    int sum_seg(int x,int y){
        if(x == 1)
            return sum(y);
        else
            return sum(y) - sum(x - 1);
    }

    (2). 区间修改，单点查询

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void update_seg(int x,int y,long long k){
        b[x] += k, b[y + 1] -= k;
        update_dot(x, k);
        update_dot(y + 1, -k);
    }

    long long query(int x){
        long long ans = 0;
        for (; x;x-=lowbit(x))
            ans += c[x];
        return ans;
    }

    3.线段树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    LL n, m, op;
    LL a[maxn], d[maxn<<2], b[maxn<<2];
    LL ans[maxn],k;

    //?建树
    void build(LL s, LL t, LL p) {
        //todo 对 [s,t] 区间建立线段树,当前根的编号为 p
        //*递归建树，边界条件为区间长度为1，此时 d[i]=a[s]=a[t]
        if(s==t){
            d[p] = a[s];
            return;
        }
        LL m = (s + t) >> 1;

        //todo 递归对左右区间建树
        //*左儿子序号为p*2，右儿子序号为p*2+1
        build(s, m, p << 1);
        build(m + 1, t, p << 1 | 1);

        //*根节点大小为左右儿子节点之和
        d[p] = d[p << 1] + d[p << 1 | 1];
    }

    //?区间查询
    LL getsum(LL l, LL r, LL s, LL t, LL p) {
        //*[l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
        if(s>=l&&t<=r)
            return d[p];
        //*当前区间为询问区间的子集时直接返回当前区间的和
        
        LL m = (s + t) >> 1;

        LL sum = 0;

        //*如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
        if (b[p]) {
            d[p << 1] += b[p] * (m - s + 1);
            d[p << 1 | 1] += b[p] * (t - m);
            b[p << 1] += b[p];            //*将标记下传给子节点
            b[p << 1 | 1] += b[p];                       
            b[p] = 0;                    //*清空当前节点的标记
        }
        //*如果左儿子代表的区间 [l,m] 与询问区间有交集,则递归查询左儿子
        if(l<=m)
            sum += getsum(l, r, s, m, p << 1);
        //*如果右儿子代表的区间 [m+1,r] 与询问区间有交集,则递归查询右儿子
        if(r>m)
            sum += getsum(l, r, m + 1, t, p << 1 | 1);

        return sum;
    }

    //?区间修改(增加)
    void update(LL l, LL r, LL c, LL s, LL t, LL p) {
        //*[l,r] 为修改区间,c 为被修改的元素的变化量,
        //*[s,t] 为当前节点包含的区间,p为当前节点的编号

        //*当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
        if(s>=l&&t<=r){
            d[p] += (t - s + 1) * c;
            b[p] += c;
            return;
        }

        LL m = (s + t) >> 1;

        //*如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
        if(b[p]&&s!=t){
            d[p << 1] += (m - s + 1) * b[p];
            d[p << 1 | 1] += (t - m) * b[p];
            //*将标记下传给子节点
            b[p << 1] += b[p];
            b[p << 1 | 1] += b[p];
            //*清空当前节点的标记
            b[p] = 0;
        }
        if(l<=m)
            update(l, r, c, s, m, p << 1);
        if(m<r)
            update(l, r, c, m + 1, t, p << 1 | 1);
        d[p] = d[p << 1] + d[p << 1 | 1];
    }

    BST（不必需）

  • 基础图论算法

    邻接表建图

    图上DFS/BFS

  • 进阶图论算法

    拓扑排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void bfs(){
        while(!q.empty()){
            int x = q.front();
            q.pop();
            for (int i = 0; i < e[x].size();i++){
                int next = e[x][i];
                in[next]--;
                if(!in[next])
                    q.push(next);
                cost[next] = max(cost[next], cost[x] + t[next]);
            }
        }
    }

    最小生成树

    1.Kruskal

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    sort(e + 1, e + m + 1, cmp);
    s.build(n);

    for (int i = 1; i <= m;i++){
        int x = s.find(e[i].u);
        int y = s.find(e[i].v);
        if(x==y)
            continue;
        cnt++;
        s.join(x, y);
        ans += e[i].w;
    }

    if(cnt==n-1)
        printf("%d", ans);
    else
        printf("orz");

    最短路（Dijkstra,SPFA,Floyd）

    1. Dijkstra

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #include <queue>
    using namespace std;

    struct node{
        int dis;
        int pos;
        bool operator<(const node &x)const{
            return x.dis < dis;
        }
    };

    priority_queue<node> q;

    void Dijkstra(int start){
        dis[start] = 0;
        q.push((node){0, start});
        while(!q.empty()){
            node tmp = q.top();
            int x = tmp.pos, d = tmp.dis;
            q.pop();
            if(vis[x])
                continue;
            vis[x] = true;
            for (int i = 0; i < e[x].size();i++){
                int t = e[x][i].next;
                if(dis[t]>dis[x]+e[x][i].length){
                    dis[t] = dis[x] + e[x][i].length;
                    if(!vis[t])
                        q.push((node){dis[t], t});
                }
            }
        }
    }

    2. SPFA

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void SPFA(int start){
        q.push(start), vis[start] = true;
        while(!q.empty()){
            int x = q.front();
            q.pop(), vis[x] = false;
            for (int i = 0; i < e[x].size();i++){
                int t = e[x][i].next;
                if(dis[t]>dis[x]+e[x][i].len){
                    dis[t] = dis[x] + e[x][i].len;
                    if(!vis[t])
                        q.push(t), vis[t] = true;
                }
            }
        }
    }

    图的连通性问题（连通分量，强连通分量，缩点，割点，桥，点双连通分量，边双连通分量）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    //*dfn[]:结点u搜索次序的时间戳（固定）
    //*low[]:结点u或u的子树能够到达的最早的*栈中*结点的dfn值（动态更新）
    int dfn[maxn], low[maxn];

    //*记录是否出栈
    bool out[maxn];

    //*防止读入重边
    bool ext[maxn][maxn];

    //*记录点u所属的强连通分量的编号
    int co[maxn];

    void tarjan(int u){
        dfn[u] = low[u] = ++num;
        s.push(u);

        //*遍历点u的邻接表
        for (int i = 0; i < e[u].size();i++){
            int v = e[u][i];
            if(!dfn[v]){
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }
            //*防止使用已经出栈的点更新
            else if(!out[v])
                low[u] = min(low[u],low[v]);
        }

        //*找到强连通分量的根即可输出
        if(dfn[u]==low[u]){
            t++;
            while(s.top()!=u){
                //printf("%d ", s.top());
                out[s.top()] = true, co[s.top()] = t;
                s.pop();
            }
            //printf("%d", s.top());
            out[s.top()] = true, co[s.top()] = t;
            s.pop();
            //printf("\n");
        }
    }

    //*建新图BFS
    void new_graph(){
        for (int i = 1; i <= n;i++)
            A[co[i]] += a[i];

        memset(ext, false, sizeof(ext));
        for (int i = 1; i <= n;i++)
            for (int j = 0; j < e[i].size();j++){
                int x = co[i], y = co[e[i][j]];
                if(x!=y&&!ext[x][y])
                    E[x].push_back(y), ext[x][y] = true, in[y]++;
            }

        for (int i = 1; i <= t;i++)
            if(!in[i]){
                q.push(i);
                dp[i] = A[i];
            }
    }

    void bfs(){
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for (int i = 0; i < E[u].size();i++){
                int v = E[u][i];
                in[v]--;
                if(!in[v])
                    q.push(v);
                dp[v] = max(dp[v], dp[u] + A[v]);
            }
        }
    }

  • 高阶树上算法

    LCA

    1.预处理深度，倍增数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void getDepth_dfs(int u){
        visited[u] = true;
        for (int i = 0; i < T[u].size();i++){
            int v = T[u][i];
            if(!visited[v]){
                parents[0][v] = u;
                depth[v] = depth[u] + 1;
                getDepth_dfs(v);
            }
        }
    }

    void getParents(){
        for (int up = 1; (1 << up) <= n; up++)
            for (int i = 1; i <= n; i++)
                parents[up][i] = parents[up - 1][parents[up - 1][i]];
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29

    int LCA(int u,int v){
        if(depth[u] < depth[v]) // 使满足u深度更大, 便于后面操作
            swap(u, v);

        // i求的是最多能向上跳2的几次幂步 
        int i = -1;
        while((1<<(i+1)) <= depth[u])
            ++i;

        // 平衡深度
        for (int j = i; j >= 0;j--)
            if(depth[u]-(1<<j)>=depth[v])
                u = parents[j][u];

        //特判刚好跳到一起（u，v有直接的祖宗关系）
        if(u==v)
            return u;

        // u和v一起向上跳
        for (int j = i; j >= 0;j--)
            if(parents[j][u]!=parents[j][v]){
                u = parents[j][u];
                v = parents[j][v];
            }

        //此时u已经位于LCA的子结点
        return parents[0][u];
    }

    树的直径，树的重心，树的中心

    1.直径

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void dfs(int u,int fa){
        vis[u] = true;
        for (int i = 0; i < E[u].size();i++){
            int v = E[u][i];
            if(v == fa)
                continue;
            d[v] = d[u] + 1;
            if(d[v]>d[m])
                m = v;
            if(!vis[v])
                dfs(v, u);
        }
    }

    2.重心

    DFS处理子树大小，然后依次与n/2比较

  • 动态规划

    经典例题各一道

  • 字符串

    Trie

    KMP

  • 数论

    快速幂

    1
    2
    3
    4
    5
    6
    7
    8
    void mod(long long b, long long p, long long k) {
        while(p){
            if(p & 1)
                result =(result* b)%k;
            b = (b * b)%k;
            p >>= 1;
        }
    }

    质因数分解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    vector<int> ret;
    vector<int> factor(int x)
    {
        for (int i = 2; i * i <= x; i++)
            while (x % i == 0)
            {
                ret.push_back(i);
                x /= i;
            }
        if (x > 1)
            ret.push_back(x);
        return ret;
    }

    筛法（线性筛，区间筛）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void GetPrime(int n)
    {
        memset(isPrime, 1, sizeof(isPrime));
        isPrime[1] = 0;
        for (int i = 2; i <= n; i++)
        {
            if (isPrime[i])
                prime[++cnt] = i;
            for (int j = 1; j <= cnt && i * prime[j] <= n; j++)
            {
                isPrime[i * prime[j]] = false;
                if (i % prime[j] == 0)
                    break;
            }
        }
    }

    GCD/LCM

    算数基本定理

    同余方程

    欧拉函数，欧拉定理

    费马小定理

    乘法逆元

    中国剩余定理（CRT）

    组合数学（递推式）

  • 考场技巧

    对拍程序

    快读/快写模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    inline int read()
    {
        int x=0,f=1;
        char ch=getchar();
        while (ch<'0'||ch>'9'){
            if (ch=='-') 
                f=-1;
            ch=getchar();
        }
        while (ch>='0'&&ch<='9'){
            x=x*10+ch-48;
            ch=getchar();
        }
        return x*f;
    }

    宏定义（如果需要）