历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

整理自己在Acwing上的问题

作者：

JasonQ1an , 2021-04-21 08:44:50 , 所有人可见 , 阅读 680

3

6

$\color{#E9967A}{配合Ctrl + F搜索使用，效果更佳}$

$\color{#E9967A}{摘自《算法基础课》《算法提高课》}$

算法基础课{:target=”_blank”}
算法提高课{:target=”_blank”}

$\color{#0000FF}{算法小tip}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

比赛时候选择类型

$\color{#FF4500}{比赛时候都用long long防止爆int}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

时空复杂度分析

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

64M

1 Byte = 8 bit

1 KB= 1024 Byte

1 MB=1024*1024 Byte

1 GB=1024 * 1024 * 1024 Byte

int  4 Byte

char 1 Byte

double, long long   8Byte

bool 1 Byte

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

memcpy

$\color{#FF7F50}{}$
$\color{#FF4500}{}$
定义：void memcpy(void destin, void *source, unsigned n)；

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

运算符

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF4500}{按位与运算符}$(&)

参加运算的两个数据，按二进制位进行“与”运算。

运算规则：0&0=0;  0&1=0;   1&0=0;    1&1=1;

$\color{#FF4500}{按位或运算符}$(|)

参加运算的两个对象，按二进制位进行“或”运算。

运算规则：0|0=0；  0|1=1；  1|0=1；   1|1=1；

比如在线段树中会使用到
3 << 1 | 1 == (3 << 1) | 1;
3 << 1 ==(11)(二进制) << 1 == (110)(二进制)
    110 | 1 
==  110
    |
    001
   =111
   =7

$\color{#FF4500}{取反运算符}$(~)

参加运算的一个数据，按二进制位进行“取反”运算。

运算规则：~1=0；  ~0=1；

$\color{#FF4500}{异或运算符}$(^)

用于比较两个二进制数的相应位。在执行按位异或运算时，
如果两个二进制数的相应位都位1或两个二进制数的相应位都位0，则返回0；
如果两个二进制数的相应位其中一个为1，另一个为0，则返回 1；

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

sort的降序排序

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{利用谓词进行降序}$

int arr[n];

bool compare(int a, int b)
{
    return a > b;
}

sort(arr, arr + n, compare);

$\color{#0000FF}{第五章：动态规划(闫式DP分析法)}$

背包问题

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF4500}{背包问题的思想就是选择性问题，一般第一维是有多少个物品，或者多少种选择，第二维是约束条件，比如说重量，体积，价值}$
$\color{#FF4500}{背包问题的一般优化方式就是删除维度，将n维变成n - 1维空间。}$
$\color{#FF4500}{比如:以下面的01背包问题举例：}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{①01背包问题}$
朴素写法

#include<iostream>
using namespace std;

int q[1010][1010];//第一个表示第i件物品，第二个表示当前物品的重量

int v[1010], w[1010];

int main()
{
    int N, V;
    cin >> N >> V;

    for(int i = 1; i <= N; i++)
    {
        cin >> v[i] >> w[i];
    }

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= V; j++)
        {

            if(j < v[i])
            q[i][j] = q[i - 1][j];
            else
            q[i][j] = max(q[i - 1][j], q[i - 1][j - v[i]] + w[i]);
        }
    cout << q[N][V];
}

优化写法

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int f[N];
int v[N], w[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);

    for(int i = 1; i <= n; i ++ )
        for(int j = m; j >= v[i]; j -- )
        //为什么此处是从大到小：因为第二层循环结束后，此时的f[j]就是相当于原来二维数组的
        //f[i - 1][j]，是属于i - 1层的数据。由于又要进行第二层循环，若从小到大，则数据跟
        //新就会覆盖掉i - 1层的数据，使得更后面的数据会使用当前 i 层的数据。为了避免这种
        //情况，则从大到小开始遍历
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            //f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);

    cout << f[m] << endl;
}

$\color{#FF4500}{言而总之：如果要使用上一维的状态就从大到小，如果使用当前维的状态就从小到大}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{②完全背包问题}$
朴素版写法(n^3)TLE

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1010;

int f[N][N];
int n, m;
int v[N], w[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);

    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int k = 0; k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

    cout << f[n][m] << endl;
    return 0;
}

优化版n^2

f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, f[i - 1][j - 3v] + 3w, ...)
f[i][j - v] = max(         f[i - 1][j - v]    , f[i - 1][j - 2v] + w,  f[i - 1][j - 3v] + 2w, ...)

将f[i][j - v] + w == f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, f[i - 1][j - 3v] + 3w, ...}

即只用做一次判断即可
f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1010;

int f[N][N];
int n, m;
int v[N], w[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);

    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }    
    cout << f[n][m] << endl;
    return 0;
}

优化版(使用一维数组)

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1010;

int f[N];
int n, m;
int v[N], w[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);

    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            if(j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}

$\color{#FF4500}{这里没有01背包问题（从大到小）是因为当前使用的是第i层，就是当前这一层，}$
$\color{#FF4500}{而01背包问题是使用的i - 1层，使用的上一层}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{③多重背包问题}$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int v[N], w[N], s[N];
int f[N][N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++ ) scanf("%d%d%d", &v[i], &w[i], &s[i]);

    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )   //  为什么j可以取0？
                                        //  因为f[i][0]代表一种状态，即为体积容量为0的情况下的选法
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

    cout << f[n][m] << endl;
    return 0;
}

$\color{#FF4500}{由于多重背包问题每个物品有个数限制，所以不能用完全背包的优化方式}$

二进制优化

基本思路：将一个数字转化为二进制数，从而进行分组。比如数字7可以分组为1， 2， 4
即2^0, 2^1, 2^2。 
当需要1的时候就可以选择2^0
当需要2的时候就可以选择2^1
当需要3的时候就可以选择2^0 + 2^1
当需要4的时候就可以选择2^2
当需要5的时候就可以选择2^0 + 2^2
当需要6的时候就可以选择2^1 + 2^2
当需要7的时候就可以选择2^0 + 2^1 + 2^2

而在需要一个数字的时候2^0, 2^1, 2^2只考虑使用或者不使用（即只选择一次），就可以使用01背包来进行优化

多重背包问题将所有的数据按照二进制分类，所以一个物品选择使用几次就可以由O(n)优化至O(logn),大大减少了时间

$\color{#FF4500}{利用二进制转化为01背包问题(选或者不选)}$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 13000, M = 1010;

int w[N], v[N];
int f[N];
int n, m;

int main()
{
    cin >> n >> m;

    int cnt = 0;//计数分了多少组
    for(int i = 1; i <= n; i ++ )
    {
        int k = 1;
        int a, b, c;
        cin >> a >> b >> c;
        while(k <= c)
        {
            cnt ++;
            v[cnt] = k * a;
            w[cnt] = k * b;
            c -= k;
            k *= 2;
        }

        if(c > 0)
        {
            cnt ++;
            v[cnt] = c * a;
            w[cnt] = c * b;
        }
    }

    for(int i = 1; i <= cnt; i ++ ) //  从cnt中物品中选择
        for(int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

线性DP

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF4500}{线性DP:数组的维数就是限制条件，比如在二维数组中的第几位，在一维数组中前i位的最长上升子序列为多少}$
$\color{#FF4500}{一般都是求最大值，最小值}$

$\color{#FF7F50}{①数字三角形}$
$\color{#FF4500}{f[i][j] : 在第s[i][j]处的最大值是多少}$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int f[N][N], a[N][N];
int n;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= i; j ++ )
            scanf("%d", &a[i][j]);

    for(int i = 0; i <= n; i ++ )//处理边界问题，防止越界
        for(int j = 0; j <= i + 1; j ++ )//max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j])
                                         //判断这个时候，当到最右边的数据的，由于右上角无数据，会越界
                                         //所以j <= i + 1使得最右边数据得右上角初始化
            f[i][j] = -INF;

    f[1][1] = a[1][1];

    for(int i = 2; i <= n; i ++ )
        for(int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

    int res = -INF;

    for(int i = 1; i <= n; i ++ )
        res = max(res, f[n][i]);

    cout << res << endl;
    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{②最长上升子序列}$
$\color{#FF4500}{f[i] : 前i个字符串中最大的上升子序列是多少}$
朴素版

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int f[N], a[N];
int n;

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for(int i = 1; i <= n; i ++ )
    {
        f[i] = 1;
        for(int j = 1; j < i; j ++ )
            if(a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }

    int res = 0;
    for(int i = 1; i <= n; i ++ ) res = max(res, f[i]);

    printf("%d", res);
    return 0;
}

贪心版
$\color{#FF4500}{q[i] : 长度为i，且最后一个字符为q[i] 的序列}$
$\color{#FF4500}{每次更新的时候找到q数组中小于a[i]的第一个元素记为q[mid]}$
$\color{#FF4500}{用q[mid]的位置更新len 以及 q[r + 1] (q[mid]的下一个元素)}$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int len = 0;
    q[0] = -2e9;//设置哨兵，防止越界

    for(int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }

        len = max(len, r + 1);
        q[r + 1] = a[i];
    }

    printf("%d\n", len);
    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{③最长公共子序列}$
$\color{#FF4500}{由 i 控制的a[]数组中的每一个字符去与b[]数组中的 1 ~ j 中每一个字符匹配}$
$\color{#FF4500}{f[i][j]:a[]数组前i个字符，与b[]数组前j个字符组成的最大公共子序列的长度}$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);

    for(int i = 1; i <= n ; i ++ )
        for(int j = 1; j <= m; j ++ )
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j])
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }

    printf("%d\n", f[n][m]);
    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{④最短编辑距离}$
$\color{#FF4500}{f[i][j]表示a数组中前i个字符变换到b数组中前j个字符所需要的最小操作次数}$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010, INF = 1e9;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    scanf("%s", a + 1);
    scanf("%d", &m);
    scanf("%s", b + 1);

    for(int i = 0; i <= m; i ++ ) f[0][i] = i;  //  初始化，当a中一个字符都没有时，变换为b时，需要进行i次操作(注意i <= m)
    for(int i = 0; i <= n; i ++ ) f[i][0] = i;  //  初始化，当b中一个字符都没有时，变换为b时，需要进行i次操作(注意i <= n)

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
        {
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;    //  f[i - 1][j]:在a数组中删除一个字符
                                                            //  f[i][j - 1]:在a数组中添加一个字符
            if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);   //  f[i - 1][j - 1]:在a数组中替换一个字符
                                                                        //  若a[i] == b[j],则看a[i - 1][j - 1]的方案数
                                                                        //  若a[i] != b[j],则看a[i - 1][j - 1] + 1的方案数
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }

    printf("%d\n", f[n][m]);
    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

区间DP

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF4500}{在[l, r]范围中求得最大值或者最小值}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{①石子合并}$
$\color{#FF4500}{f[i][j] : 从i到j这个区间中合并石子需要的最小代价}$

为什么最后一步要去前缀和相差？

举个例子：1 3 5 2
组合方式有1 3， 5 2                           1 3， 5 2                        
           4    5 2                            4    5 2                
              9   2                            4     7
                11                                11
所求的的代价总和为4 + 9 + 11 = 24  所求的的代价总和为4 + 7 + 11 = 22                  
注意，每一次组合方式中的最后一步都是加上了11，说明最后一次就是1 加到 2的代价，即1 + 3 + 5 + 2 = 11。
所以需要s[r] - s[l - 1]。

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

f[l][k] + f[k + 1][r] + s[r] - s[l - 1]什么意思？

每次求f[l][r] 的状态都是由f[l][k] + f[k + 1][r] + s[r] - s[l - 1]转化而来的。
当中的f[l][k] + f[k + 1][r]就是求区间中分成两部分l, k 和k + 1, r的代价和为最小。举个例子
比如说要求f[1, 5]这个区间中的最小值，它就有可能是f[1, 2] + f[3, 5], 
或者是f[1, 3] + f[4,5]的来的（区间一定是连续的，这与题目有关系）。
此时还需要加上前缀和s[r] - s[l - 1]的值，
加上前缀和是由于需要将 端点l 搬运到 端点r 的代价求出，将端点包含进去

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

int s[N];
int n;
int f[N][N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);

    for(int i = 1; i <= n; i ++ ) s[i] += s[i - 1];

    for(int len = 2; len <= n; len ++ )//枚举每一种区间长度
    {
        for(int i = 1; i + len - 1<= n; i ++ )//枚举区间长度
        {
            int l = i, r = i + len - 1;
            f[l][r] = 1e9;
            for(int k = l; k < r; k ++ )
            f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    }
    printf("%d", f[1][n]);
    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

计数类DP

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF4500}{求的属性是方案数的DP规划}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{①整数划分}$
$\color{#FF4500}{f[i][j]:从前i个物品中选且总体积恰好等于j的方案数}$
$\color{#FF4500}{由于每个数字(物品)可以无限次选择，所以可以用完全背包问题优化}$

f[i][j] = max(f[i - 1][j],  f[i - 1][j - i], f[i - 1][j - 2*i], f[i - 1][j - 3*i], ...,                    f[i - 1][j - s*i]);
f[i][j - i] =           max(f[i - 1][j - i], f[i - 1][j - 2*i], f[i - 1][j - 3*i], f[i - 1][j - 3*i], ..., f[i - 1][j - s*i]);

f[i][j] = max(f[i - 1][j], f[i][j - 1])
进而优化空间为
f[j] = max(f[j], f[j - 1]);

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N];

int main()
{
    cin >> n;
    f[0] = 1;
    for(int i = 1; i <= n; i ++ )
        for(int j = i; j <= n; j ++ )
            f[j] = (f[j] + f[j - i]) % mod;

    cout << f[n] << endl;
    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

数位统计DP

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

状态压缩DP

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

树形DP

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

记忆化搜索

$\color{#0000FF}{第一章：基础算法}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

快排

void quick_sort(int q[], int l, int r)  //  快排的范围为(0, n - 1)
{
    if(l >= r)
    return;

    int t = q[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j)  //  此处不能 <=  因为当数组只有一位数字的时候就会发生死循环
    {
        do i ++; while(q[i] < t);
        do j --; while(q[j] > t);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

归并排序

void merge_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int mid = l + r >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;  //  j = mid + 1平均分为两份

    while(i <= mid && j <= r)
        if(q[i] > q[j]) temp[k ++ ] = q[j ++ ];
            else temp[k ++ ] = q[i ++ ];

    while(i <= mid) temp[k ++ ] = q[i ++ ];  //  待到前面while循环全部结束后，才判断i, j是否走完
    while(j <= r) temp[k ++ ] = q[j ++ ];
    for(int i = l, k = 0; i <= r; i ++, k ++ ) 
        q[i] = temp[k];
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

二分(后续补充证明)

方法一
注意：$\color{#FF0000}{l + r >> 1}$

    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(q[mid] >= x) r = mid;
        else l = mid + 1;
    }

方法二
注意：$\color{#FF0000}{l + r + 1 >> 1}$

    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(q[mid] >= x) l = mid;
        else r = mid - 1;
    }

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

高精度模板

高精度加法

vector<int> add(vector<int> &A, vector<int> &B)
{
    int k = 0;
    vector<int> C;
    for(int i = 0; i < A.size() || i < B.size(); i ++)
    {
        if(i < A.size()) k += A[i];
        if(i < B.size()) k += B[i];

        C.push_back(k % 10);
        k /= 10;
    }
    if(k)C.push_back(1);  //  因为k∈[0, 18]，可能循环结束时，k == 1
    return C;
}

高精度减法

bool cmp(vector<int> &A, vector<int> &B)  //  用于比较两个容器的大小(主函数中使用)
{
    if(A.size() != B.size())
        return A.size() > B.size();
    else
    {
        for(int i = A.size() - 1; i >= 0; i --)
        {
            if(A[i] != B[i])return A[i] > B[i];
        }
    }
    return true;
}

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

高精度除法

vector<int> div(vector<int> &A, int b, int &c)
{
    vector<int> C;
    c = 0;

    for(int i = A.size() - 1; i >= 0; i --)
    {
        c = A[i] + c * 10;
        C.push_back(c / b);
        c %= b;
    }
    reverse(C.begin(), C.end());

    while(C.size() > 1 && C.back() == 0)C.pop_back();

    return C;
}

高精度乘法

vector<int> mul(vector<int> A, int b)
{
    vector<int> C;
    for(int i = 0, t = 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;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

前缀和

一维前缀和

#include<iostream>
using namespace std;

const int N = 10e5 + 10;

int q[N], s[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)scanf("%d", &q[i]);
    for(int i = 1; i <= n; i ++)s[i] = s[i - 1] + q[i];

    while(m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
}

二维前缀和

#include<iostream>
using namespace std;

const int N = 1010;

int q[N][N];
int s[N][N];

int main()
{
    int n, m, t;
    cin >> n >> m >> t;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d", &q[i][j]);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + q[i][j];
    while(t--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

差分

$\color{#FF4500}{可以快速修改区间内的值}$

一维差分

#include<iostream>
using namespace std;

const int N = 100010;

int a[N], b[N];

int n, m;

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i ++)
    scanf("%d", &a[i]);

    for(int i = 1; i <= n; i ++)
    insert(i, i, a[i]);

    while(m--)
    {
        int l, r, c;
        cin >>l >> r >> c;
        insert(l, r, c);
    }

    for(int i = 1; i <= n ; i ++)
    {
        b[i] = b[i] + b[i - 1];
        printf("%d ", b[i]);
    }
}

二维差分矩阵

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);

    int x1, y1, x2, y2, c;    
    while(q -- )
    {
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];

    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= m; j ++ )
            printf("%d ", a[i][j]);
        puts("");
    }
    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

双指针算法

$\color{#FF4500}{控制两个指针，一个快指针，一个慢指针}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{①最长连续不重复子序列}$
$\color{#FF4500}{i每次都自增，j当有重复元素出现时才自增。每求一次i就要跟新一下res}$
$\color{#FF4500}{res = max(res, i - j + 1);}$

#include<iostream>
using namespace std;

const int N = 100010;

int a[N], s[N];

int n;

int main()
{
    cin >> n;
    int res = 0;

    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);

    for(int i = 0, j = 0; i < n; i ++)
    {
        s[a[i]] ++;
        while(s[a[i]] > 1)
        {
            s[a[j]] --;
            j ++;
        }

        res = max(res, i - j + 1);
    }

    cout << res << endl;
    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{②数组元素的目标和}$
$\color{#FF4500}{i从a[]前面开始，j从b[]后面开始}$
$\color{#FF4500}{利用此语句控制j的自减}$
while(j >= 0 && a[i] + b[j] > x) j –;

代码：

#include<iostream>
using namespace std;

const int N = 100010;

int n, m, x;

int a[N], b[N];

int main()
{
    scanf("%d%d%d", &n, &m, &x);

    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i ++) scanf("%d", &b[i]);

    for(int i = 0, j = m - 1; i < n; i ++)
    {
        while(j >= 0 && a[i] + b[j] > x) j --;  //若使用if则会跳过a数组，得不到答案
        if(a[i] + b[j] == x)
        {
            printf("%d %d\n", i, j);
            break;
        }
    }
    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{③判断子序列}$
$\color{#FF4500}{i控制a[]数组，j控制b[]数组}$

#include <iostream>

using namespace std;

const int N = 100010;
int n, m;
int a[N], b[N];

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for(int i = 0; i < m; i ++ ) scanf("%d", &b[i]);

    int i = 0, j = 0;
    while(i < n && j < m)
    {
        if(a[i] == b[j]) i ++ ;
        j ++ ;
    }

    if(i == n) puts("Yes");
    else puts("No");

    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

位运算

$\color{#FF4500}{利用了lowbit原理}$

x 假设为 (1000101000)
-x    为 (0111010111)
-x + 1为 (0111011000)

x 与 -x + 1相& 就能得到第一个1出现的位置。
再经过函数返回值，使x -= lowbit(x) 就可以将
第一个x出现位置减去

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{①二进制中1的个数}$

#include <iostream>

using namespace std;

int n;

int lowbit(int x)
{
    return x & -x;
}

int main()
{
    scanf("%d", &n);

    while(n -- )
    {
        int x, res = 0;
        scanf("%d", &x);
        while(x)
        {
            x -= lowbit(x);
            res ++;
        }
        printf("%d ", res);
    }

    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

离散化

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

区间合并

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{区间合并}$
$\color{#FF4500}{运用了贪心的思想，将所有pair类型元素，按照左端点从小到大排序}$

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

typedef pair<int, int> PII;

int n;

void merge(vector<PII> &segs)
{
    sort(segs.begin(), segs.end());

    vector<PII> res;

    int st = -2e9, ed = -2e9;

    for(auto seg:segs)
    {
        if(ed < seg.first)
        {
            if(st != -2e9) res.push_back({st, ed});
            st = seg.first;
            ed = seg.second;
        }
        else ed = max(ed, seg.second);
    }

    if(st != -2e9)res.push_back({st, ed});  //防止输入数组中没有任何元素，防止为空

    segs = res;
}

int main()
{
    vector<PII> segs;
    cin >> n;

    while(n --)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#0000FF}{第二章：数据结构}$

单链表

双链表

栈

队列

单调栈

单调队列

KMP(淦！)

Trie

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

树状数组

$\color{#FF4500}{树状数组的核心操作lowbit原理}$

int lowbit(int x)
{
    return x & -x;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{①动态求连续区间和}$
$\color{#FF4500}{}$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int a[N], tr[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int v)  //  运用了前缀和的思想
{
    for(int i = x; i <= n; i += lowbit(i) ) tr[i] += v;
}

int query(int x)
{
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)) sum += tr[i];
    return sum;
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++ ) add(i, a[i]);

    while(m -- )
    {
        int k ,x, y;
        scanf("%d%d%d", &k, &x, &y);
        if(k == 0) printf("%d\n", query(y) - query(x - 1));
        else add(x, y);
    }
    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

线段树

$\color{#FF4500}{对于四个操作}$
$\color{#FF4500}{①pushup:用子节点信息更新当前结点信息}$
$\color{#FF4500}{②build：在一段区间上初始化线段树}$
$\color{#FF4500}{③modify：修改}$
$\color{#FF4500}{④query：查询}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{①动态求连续区间和}$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int w[N];
struct Node
{
    int l, r;
    int sum;
}tr[4 * N]; //  常识来说开4倍

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;//u << 1 | 1 == u / 2 + 1;
}

void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, w[r]};//w[r] == w[l] (r == l)
    else
    {
        tr[u] = {l, r}; //初始化
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);//跟新后求和
    }
}

int query(int u, int l, int r)  //求区间和
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;  //当前区间已经包含了u的区间
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if(l <= mid) sum = query(u << 1, l, r);
    if(r > mid) sum += query(u << 1 | 1, l, r);//为什么不取=？ 因为r == mid + 1
    return sum;
}

void modify(int u, int x, int v)
{
    if(tr[u].l == tr[u].r) tr[u].sum += v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);

    int k, a, b;
    while(m -- )
    {
        scanf("%d%d%d", &k, &a, &b);
        if(k == 0) printf("%d\n", query(1, a, b));
        else modify(1, a, b);
    }
    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

并查集

$\color{#FF4500}{适用场合}$

1.将两个集合合并
2.查询两个元素是否在一个集合中

$\color{#FF4500}{优化：路径压缩}$

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

堆

哈希表

$\color{#0000FF}{第三章：搜索与图论}$

1.优化版dijkstra会出现的问题

注意priority_queue一定是小顶堆，语法:priority_queue<PII, vector<PII>, greater<PII>> heap;
heap里面存的pair类型，第一个一定一定是距离，因为每次要取出最小距离。第二个是位置编号(idx)

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

DFS

$\color{#FF4500}{利用函数进行递归操作}$
$\color{#FF4500}{注意条件：}$
$\color{#FF4500}{1.进入下一层递归的条件要考虑完整，清楚！}$
$\color{#FF4500}{2.注意每一次递归结束后都要恢复现场！}$
$\color{#FF4500}{3.一般用于求方案数}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

BFS

$\color{#FF4500}{利用队列进行递归操作}$
$\color{#FF4500}{注意条件}$
$\color{#FF4500}{1.注意入队的条件要考虑完整，清楚！}$
$\color{#FF4500}{2.考试个数要求不是很多，可以用stl<queue>来写。}$
$\color{#FF4500}{3.一般用于求最短路径}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

树与图的深度优先遍历

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010, M = 2 * N;

int n;
int h[N], e[M], ne[M], idx;//因为是无向图(有两个方向),所以e，ne要开两倍空间
bool walked[N];

int ans = N;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

//以u为子树中点的数量
int dfs(int u)
{
    walked[u] = true;

    int sum = 1, res = 0;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!walked[j])
        {
            int s = dfs(j);
            res = max(res, s);  //  为什么用最大值？因为ans求的是每个点中联通的最大值这个集合中的最小值
            sum += s;
        }
    }

    res = max(res, n - sum);

    ans = min(ans, res);

    return sum;
}

int main()
{
    memset(h, -1, sizeof h);

    cin >> n;

    for(int i = 0; i < n - 1; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);//创建无向图，使每2个结点之间可以来回
    }

    dfs(2);//任意一个1~n的数字都可以，可以从任意位置开始遍历

    cout << ans << endl;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

树与图的广度优先遍历

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

int n, m;

int h[N], e[N], ne[N], idx;

int d[N], q[N];//d代表每个数字距离开始的距离

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs()
{
    int hh = 0, tt = 0;
    q[0] = 1;//初始化队列第一个元素,起点为1

    memset(d, -1, sizeof d);

    d[1] = 0;//初始化第一个位置元素,下标为1，因为输入没有0开始的数字,同时起始位置就是1

    while(hh <= tt)
    {
        int u = q[hh ++];

        for(int i = h[u]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(d[j] == -1)
            {
                d[j] = d[u] + 1;
                q[++ tt] = j;
            }
        }
    }
    return d[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    while(m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    cout << bfs() << endl;

    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

拓扑排序

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

图论注意事项：

$\color{#FF4500}{dist[]数组初始化，一般为0x3f3f3f3f}$
$\color{#FF4500}{h[]数组初始化，一般为-1}$
$\color{#FF4500}{st[]数组的初始化，有些题目要重复使用st，记得每次使用之前初始化为0}$
$\color{#FF4500}{注意数组开的大小，不确定可以多开一些}$

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

稠密图和稀疏图的区别

$\color{#FF4500}{数据结构中对于稀疏图的定义为：有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图（sparse graph），使用邻接表。}$
$\color{#FF4500}{反之边的条数|E|接近|V|²，称为稠密图（dense graph）。使用邻接矩阵}$
$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{①邻接表}$
$\color{#FF4500}{邻接表的创建}$

在全局变量中需要定义

const int N = MAX;

(有向图的定义)
int h[N], e[N], ne[N], w[N](附加条件,比如：权重，距离), idx;

(无向图的定义)
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;

由a向b连接一条距离为c的边(利用了单链表头插的原理)

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; 
}

(有向图的添加)
add(a, b, c);

(无向图的添加)
add(a, b, c), add(b, a, c); //  加两条边

$\color{#FF7F50}{②邻接矩阵}$
$\color{#FF4500}{邻接矩阵的创建}$

在全局变量中需要定义

const int N = MAX;
int g[N][N];    //  g[i][j]:从i走到j的距离

由a向b连接一条距离为c的边

(有向图)
g[a][b] = c;

(无向图)
g[a][b] = g[b][a] = c;

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

Dijkstra

$\color{#FF7F50}{Dijkstra求最短路朴素版(边一定是正权边！)}$
$\color{#FF4500}{每次找到图中未被标记的距离最短的点，将其标记，并用这个点来更新其他所有点}$

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510;

int g[N][N];//邻接矩阵g[a][b]:代表从a走到b的距离
int dis[N];//记录该点的最小距离

bool st[N];

int n, m;

int dijkstra()
{
    memset(dis, 0x3f, sizeof dis);

    dis[1] = 0;//初始化起始位置距离为0

    for(int i = 0; i < n; i ++ )//代表迭代n次  使用int i = 1; i <= n也是可以的
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ )
            if(!st[j] && (t == -1 || dis[t] > dis[j])) //如果dis[t] > dis[j]，即dis[t]不是最小值，需要交换
                t = j;

        st[t] = true;

        for(int j = 1; j <= n; j ++ )
            dis[j] = min(dis[j], dis[t] + g[t][j]);
    }

    if(dis[n] == 0x3f3f3f3f) return -1;
    else return dis[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);

    while(m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }

    int ans = dijkstra();

    printf("%d", ans);

    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#FF7F50}{Dijkstra堆优化版(边一定是正权边！)}$
$\color{#FF4500}{由于每次都是找未被标记的距离最小的点，所以可以用小根堆来优化}$

$\color{#FF4500}{注意pair第一个存储的是距离，第二个存储的位置。因为需要按照距离排序}$
$\color{#FF4500}{所以第一个一定一定一定是距离！！！}$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 1000010;

typedef pair<int, int> PII;
int e[N], ne[N], w[N], h[N], idx;
bool st[N];
int dist[N];
int n, m;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    heap.push({0, 1});

    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;
    else return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    int a, b, c;
    while(m -- )
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    printf("%d\n", dijkstra());

    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

bellman_ford

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

spfa

$\color{#FF7F50}{spfa求最短路}$
$\color{#FF4500}{用当前的点更新它能够到达的点的距离，也就是说用更新过后的点来更新其他点}$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int e[N], ne[N], w[N], h[N], idx;
bool st[N];
int dist[N];
int n, m;

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

int spfa()
{
    queue<int> q;
    q.push(1);
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    st[1] = false;

    while(q.size())
    {
        int 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])
                {
                    st[j] = true;   //  记录以及存在这个点，不需要重复加入
                    q.push(j);
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while(m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    int ans = spfa();

    if(ans == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", ans);

    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

Floyd

$\color{#FF7F50}{Floyd求最短路}$
$\color{#FF4500}{}$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 210, INF = 1e9;

int d[N][N];
int n, m, q;

void floyd()
{
    for(int k = 1; k <= n; k ++ )   //  将其分为[i, k]和[k, j]两段，基于动态规划
        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]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    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;

    while(m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);  //  解决重边
    }

    floyd();

    while(q -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(d[a][b] > INF / 2) puts("impossible");   //注意此处必须大于INF，有可能INF会减去一个小的数字，于是就小于INF，但不会小于INF / 2(相对INF很小的数字)
        else printf("%d\n", d[a][b]);
    }

    return 0;
}

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

Prim

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

Kruskal

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

染色法判定二分图

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

匈牙利算法

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

$\color{#0000FF}{第四章：数学知识}$

1.最小公倍数和最大公约数

int gcd(int a, int b)   //  最小公倍数
{
    return b ? gcd(b, a % b) : a;
}

int lcd(int a, int b)   //  最大公约数
{
    return a * b / gcd(a, b);
}

质数

约数

欧拉函数

快速幂

扩展欧几里得算法

中国剩余定理

高斯消元

求组合数

容斥原理

博弈论

$\color{#0000FF}{第六章：贪心}$

区间问题

Huffman树

排序不等式

绝对值不等式

推公式

0 评论

App 内打开