AcWing 笔记

该笔记主要整理 AcWing 算法基础课中出现的算法，其中各模块未包含的算法将在模块开始位置指出

高精度算法

高精度加法

将数据读取 string 中，在将 string 中的数据逆序存储到 vector 数组中，逆序存储的好处在于当个位相加后存在进位的情况时，可以直接在 vector 数组之后添加一个 1 即可，用 t 来存储进位的值，当 t 为 1，则说明上个位置的个位相加大于 10。

注意点

t 用来表示进位，在进位前后只有两种可能，0 或 1
运算结束后要判断 t 是否为 1，为 1 则说明当前和已经超过 maxLength（A，B），需要进 1，即 1000·····这种情况

输入格式：1000 12

输出格式：1012

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> add(vector<int> & A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i<A.size() || i<B.size(); i++)
    {
        if(i < A.size()) t += A[i];
        if(i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if(t) C.push_back(1);
    return C;
}

int main()
{
    vector<int> A, B;
    string a, b;
    cin >> a >> b;

    for(int i = a.size() - 1; i>=0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i>=0; i--) B.push_back(b[i] - '0');

    vector<int> C;
    C = add(A, B);

    for(int i = C.size() - 1; i>=0 ;i--) cout << C[i];

    return 0;
}

高精度减法

注意点

一定要大数减小数，无论任何数相减都可转换为大数减小数
t 用来表示借位，t 的取值范围是[-10, 10]

输入格式：1000 12

输出格式：988

#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool MAX(vector<int> &A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size();

    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;
    int t = 0;
    for(int i = 0; i<A.size(); i++)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t+10) % 10);

        t = (t<0) ? 1 : 0;
    }
    while(C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;
}

int main()
{
    vector<int> A, B;
    string a, b;
    cin >> a >> b;

    for(int i = a.size() - 1; i>=0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i>=0; i--) B.push_back(b[i] - '0');

    vector<int> C;
    if(MAX(A, B))
        C = sub(A, B);
    else
    {
        C = sub(B, A);
        cout << '-';
    }

    for(int i = C.size() - 1; i>=0 ;i--) cout << C[i];

    return 0;
}

高精度乘法

限制数据范围（1≤A的长度≤100000 且 0≤B≤10000）
这里的高精度仅限于 B 相对较小
同时该乘法的不同点在于，无论 B 有多少位，我们均将其看做一位来处理
这里的 t 用来存储 a 的个位与 b 相乘后所得到的数

输入格式：1000 12

输出格式：12000

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i<A.size(); i++)//将b始终看做一位，就可以不用考虑b的长度了
    {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while(t)//将剩余的数全部放入数组中
    {
        C.push_back(t % 10);
        t /= 10;
    }
    while(C.size() > 1 && C.back() == 0)
        C.pop_back();

    return C;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;

    vector<int> A;
    for(int i = a.size() - 1; i>=0; i--) A.push_back(a[i] - '0');

    vector<int> C;
    C = mul(A, b);

    for(int i = C.size() - 1; i>=0 ;i--) cout << C[i];

    return 0;
}

仔细观察也可发现代码

    for(int i = 0; i<A.size(); i++)
    {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while(t)
    {
        C.push_back(t % 10);
        t /= 10;
    }

具有重复的地方，也可以进行合并

    for(int i = 0; i<A.size() || t; i++)
    {
        if(i<A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

高精度除法

限制数据范围（1≤A的长度≤100000 且 0≤B≤10000）
为了保持main与以上高精度算法相统一，因此这里仍然使用逆序存储的方式，但是要知道除法运算是先从高位开始进行的，而不同于其他运算

输入格式：1000 12

输出格式：83 4

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> div(vector<int>& A, int& b, int& r)
{
    vector<int> C;
    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());//原本C为正序，现在调整为逆序，之后去除前导0

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

int main()
{
    string a;
    int b;
    cin >> a >> b;

    vector<int> A;
    for(int i = a.size() - 1; i>=0; i--) A.push_back(a[i] - '0');

    vector<int> C;
    int r = 0;
    C = div(A, b, r);

    for(int i = C.size() - 1; i>=0; i--)
        cout << C[i];
    cout << endl << r << endl;
    return 0;
}

前缀和与差分

前缀和

一维前缀和

简介：对于 nums 数组，存在一个 PrefixSum 数组，其中 PrefixSum 数组的每个位置的值代表 nums 数组 0 号位置到该位置的总和，即：

PrefixSum[0] = nums[0]
PrefixSum[1] = nums[0] + nums[1]
PrefixSum[2] = nums[0] + nums[1] + nums[2]
依次类推············
通用公式：PrefixSum[i] = nums[0] + nums[1] + ···· + nums[i] = nums[i] + PrefixSum[i - 1]

当PrefixSum数组与nums数组是同一个数组时可演变为：nums[i] = nums[i] + nums[i-1]
这时会存在下标越界的情况，解决办法就是nums起始下标从1开始，而非0开始，就可以避免i-1下标越界

具体代码：

#include <iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    int *nums = new int[n+1]{0};
    for(int i = 1; i<=n; i++)
    {
        cin >> nums[i];
        nums[i] += nums[i-1];
    }

    int left, right;
    while(q--)
    {
        cin >> left >> right;
        cout << nums[right] - nums[left-1] << '\n';
    }
    return 0;
}

方式二（简写）：

vector<int> sums(n+1, 0);
for(int i = 1; i<=n; i++)
    sums[i] = sums[i - 1] + nums[i - 1];
//sums前缀和数组， nums原始数组

二维前缀和

另设 PrefixSum 数组保存二维前缀和:

输入：
PrefixSum[i][j] = nums[i][j] + PrefixSum[i-1][j] + PrefixSum[i][j-1] - PrefixSum[i-1][j-1];
输出：
cout << PrefixSum[x2][y2] - PrefixSum[x1 - 1][y2] - PrefixSum[x2][y1 - 1] + PrefixSum[x1 - 1][y1 - 1]

#include <iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;

    int **nums = new int*[n+1];
    for(int i = 0; i<=n; i++)
        nums[i] = new int[m+1]{0};

    for(int i = 1; i<=n; i++)
        for(int j = 1; j<=m; j++)
        {
            cin >> nums[i][j];
            nums[i][j] += nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1];
        }

    int x1, y1, x2,y2;
    while(q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << nums[x2][y2] - nums[x1 - 1][y2] - nums[x2][y1 - 1] + nums[x1 - 1][y1 - 1] << '\n';
    }
    return 0;
}

差分

差分的运用

1、介绍

一般地，差分主要用于让一个序列某一特定范围内的所有值都加上或减去一个常数。

所以差分往往应用于线性的场合，即一维数组的环境，但是除此之外，差分还可以应用于二维数组，但是相比较一维数组，应用的较少。

对由原始数组a生成的差分数组b求前缀和，可以得到原始数组

2、定义

差分可以简单的看成序列中每个元素与其前一个元素的差。

3.与前缀和的关系

const int N = 100010;
int a[N],b[N];  //定义两个一维整形数组 a为原数组，b为差分数组

//根据定义可知
b[i] = a[i] - a[i-1];
//稍微具体
b[1] = a[1];
b[2] = a[2] - a[1];
...
b[i] = a[i] - a[i-1];

//转化一下，求数组b的前缀和,根据上面公式可得
  b[1]+b[2]+b[3]+...+b[i]
= a[1]+(a[2]-a[1])+(a[3]-a[2])+...+(a[i]-a[i-1])
= a[i]

//由此可知，原序列为差分序列的前缀和序列
a[i] = b[1]+b[2]+b[3]+...+b[i];

一般地，我们认为原序列就是差分序列的前缀和，所以把差分看做前缀和的逆运算

一维差分

1、定义

一维差分是指给定一个长度为 n 的序列 a，要求支持操作pro(l,r,c)表示对 a[l]~a[r]区间上的每一个值都加上或减去常数 c，并求修改后的序列 a。

2、作用

让一个序列中某个区间内的所有值均加上或减去一个常数。

可以将对 a 数组任意区间的同一操作优化到 O(1)。

//区间[l,r]中的所有值都加上常数c
b[l] += c;
b[r+1] -= c;

//上边语句实现原理 b相当于a的辅助数组
//把a序列分为[1,l-1],[l,r],[r+1,n]三部分,由差分定义和与前缀和关系可得
a[l-1] = b[1]+b[2]+...+b[l-1];              //b[1]~b[l-1]中所有值都未改变，a[l-1]也不变
a[l] = b[1]+b[2]+...+b[l-1]+b[l];           //b[1] += c,所以a[l] += c
a[l+1] = b[1]+b[2]+...+b[l-1]+b[l]+b[l+1];  //b[1] += c,所以a[l+1] += c
 ...
a[r] = b[1]+b[2]+...b[l]+...+b[r];          //b[1] += c,所以a[r] += c
a[r+1] = b[1]+b[2]+...b[l]+...+b[r]+b[r+1]; //b[l] += c,所以a[r+1]不变

//所以由此可知上面的两个语句（b[l] += c;b[r+1] -= c）可以实现a数组在区间[l,r]内的所有值都加上了常数c

如果 b[1] += c, 那么由 b 数组和 a 数组的关系可以知道，a[0]到a[n]所有的元素都会加上c, 如果只想对a[0]到a[r]（r<n）这个范围的每个元素 +c，那么解决办法应该是对 b[r+1] -= c，这样和 b[1] += c 相互抵消，那么就会使得 a[0]到a[r]所有元素 +c，而 a[r+1]到a[n]之后的元素都不受影响还是原来的值，相应的替换 b[1]为 b[left]，就可以对原始数组[left, right]这个区间的值每个 +c

解题代码一

797. 差分 – AcWing题库

#include<iostream>
using namespace std;
const int N = 1e5+10;
int nums[N], diff[N];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i<=n; i++)
        cin >> nums[i];

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

    while (m -- ){
        int l, r, c;
        cin >> l >> r >> c;
        diff[l] += c, diff[r + 1] -= c;
    }

    for(int i = 1; i<=n; i++){
        diff[i] += diff[i-1];
        cout << diff[i] << ' ';
    }
    return 0;
}

解题代码二

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> nums(n+1, 0), ans(n+2, 0);//一个原始数据数组，一个差分数组
    for(int i = 1; i<=n; i++)
        cin >> nums[i];

    for(int i = 1; i<=n; i++)//求差分数组
        ans[i] = nums[i] - nums[i-1];

    int l, r, c;
    for(int i = 0; i<m; i++)//对差分数组进行处理
    {
        cin >> l >> r >> c;
        ans[l] += c;
        ans[r+1] -= c;//注意r+1可能越界，例如r在最后一个位置时，因此ans数组要加2
    }
    for(int i = 1; i<=n; i++)//差分数组求前缀和得到结果数组
    {
        ans[i] += ans[i-1];
        cout << ans[i] << ' ';
    }
    return 0;
}

二维差分

核心思想：

b[x1][y1] += c; 让整个红色矩形面积的元素都加上了c。
b[x1][y2+1] -= c;让整个绿色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y1] -= c; 让整个橙色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y2+1]+=c; 让整个天蓝色矩形面积的元素再加上c，天蓝色内的相当于被减了两次，再加上一次c，才能使其恢复。

解题思路

二维差分，顾名思义，是前缀和的逆运算，对二位差分数字求前缀和，求差分的方式可以通过找规律得到，例如设一个 3*3 的矩阵，其各个元素均为 1，已知一维差分是 a[i] – a[i-1]，那么二维差分又该如何寻找规律呢？

首先我们知道，对差分数组前 i 项求前缀和可以得到原始数组 a[i]的值，那么只有如下图所示的情况求前缀和可以得到原始数组

由图可得，例如差分矩阵 b[1,1]元素的可以看做由 a[1,1] – a[0,1] – a[1,0] + a[0,0]得到，由此可见，这和前缀和公式有相通之处，例如运算符号是相反的，其他形式并没有发生改变，当我们给其中一个元素加上 4 时，为了不对其后序元素的前缀和造成影响，必须也要对之后的元素进行相减，例如，对原始数组 a[1,1]加上 4 后，那么也要对 a[1,2]和 a[2,1]数组-4，由于减多了一块，还要对 a[2,2]加 4，这样得到的差分数组求前缀和才能得到原始数组

解题代码一

#include<iostream>
#include <vector>
using namespace std;
void insert(vector<vector<int>>&a, vector<vector<int>>&b, int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<int>> a(n+1, vector<int>(m+1, 0));//原始数组
    vector<vector<int>> b(n+2, vector<int>(m+2, 0));//差分数组，注意是n+2和m+2，要保证对最后一个元素处理不会越界

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            insert(a, b, i, j, i, j, a[i][j]);      //构建差分数组
        }

    while (q--)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(a, b, x1, y1, x2, y2, c);
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];  //二维前缀和
            cout << b[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

解题代码二

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<int>> nums(n+1, vector<int>(m+1, 0));//原始数组
    vector<vector<int>> sub(n+2, vector<int>(m+2, 0));//差分数组，注意是n+2和m+2，要保证对最后一个元素处理不会越界

    for(int i = 1; i<=n; i++)
        for(int j = 1; j<=m; j++)
        {
            cin >> nums[i][j];
            sub[i][j] = nums[i][j] - nums[i-1][j] - nums[i][j - 1] + nums[i - 1][j - 1];
        }

    while(q--)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;

        sub[x1][y1] += c;
        sub[x1][y2+1] -= c;
        sub[x2+1][y1] -= c;
        sub[x2+1][y2+1] += c;
    }

    for(int i = 1; i<=n; i++)
    {
        for(int j = 1; j<=m; j++)
        {
            sub[i][j] += sub[i - 1][j] + sub[i][j - 1] - sub[i - 1][j - 1];
            cout << sub[i][j] << ' ';
        }
        cout << '\n';   
    }
    return 0;
}

双指针

题目一

799. 最长连续不重复子序列 – AcWing题库

unordered_map 无序关联容器，和 map 的唯一区别就是无序

题目解析

AcWing 799. 最长连续不重复子序列-从暴力到双指针的详细过程 – AcWing

用一个 st 辅助数组记录双指正 j 到 i 区间的重复元素个数，并记录下来，当存在某个元素大于 1 的时候，更新 j 的位置

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> nums(n);

    for(int i = 0; i<n; i++)
        cin >> nums[i];

    unordered_map<int, int> st;
    int maxLen = 0;
    for(int i = 0, j = 0; i<n; i++)
    {
        st[nums[i]] ++;
        while(st[nums[i]] > 1)
            st[nums[j++]] --;

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

    cout << maxLen;
    return 0;
}

问题一：这里为什么只记录 nums[i]的呢
原因在于，i 指针的每次走动，只会更新 i 指针说指向的那一个元素的个数，所以只要判断该元素的出现个数是否大于 1，那么就能知道该区间是否存在重复元素了，当重复元素存在时，我们将区间缩小，这里的缩小是将 j 指针缩小，i 指针不变，知道 j 指针查找到该重复元素的第一个出现位置时，剔除该元素，该元素的出现次数减 1
问题二：while 循环为什么不需要 j<i 条件

考虑一下最坏情况，即重复元素是相邻的，i 在相邻的后一位，即：1(j) 2 3 4 5 5(i) 那么循环的条件成立，最终是 j 到达第一个 5 的时候，st[nums[i]]的个数重新由 2 恢复为 1，此时退出循环，因此没必要使用 j<i 条件，因为 j>=i 的情况就不可能出现

题目二

800. 数组元素的目标和 – AcWing题库

解题方式一：双指针

复杂度分析，O(n+m)

思路，i 向后遍历 A 数组，J 向前遍历 B 数组，i 首先固定，j 向前移动，直到出现 A【i】+ B【j】< x 时，这时说明，在 A 中最小数的情况下，找到 A【i】+ B【j】< x 在 B 数组中的边界，至此，J 指针固定，i 指针开始向后移动，直到出现一个位置 A【i】+ B【j】 x，

为什么不需要判断 A【i】+ B【j】> x 中 i 的边界出现呢，因为题目已经告诉了有唯一解，即 A【i】+ B【j】 x 一定会出现。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, x;
    cin >> n >> m >> x;

    vector<int> A(n), B(m);
    for(int i = 0; i<n; i++)
        cin >> A[i];
    for(int i = 0; i<m; i++)
        cin >> B[i];

    for(int i = 0, j = m - 1; i<n; i++)
    {
        while(j >=0 && A[i] + B[j] > x)
            j--;
        if(A[i] + B[j] == x)
        {
            cout << i <<' ' << j;
            break;
        }
    }
    return 0;
}

解题方式二：二分搜索

复杂度分析，O(nlogn)

#include <iostream>
#include <vector>
using namespace std;

int binary(vector<int> &B, int target)
{
    int left = 0, right = B.size() - 1, mid = 0;
    while(left < right)
    {
        mid = left + right >> 1;
        if(target <=B[mid])
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, x;
    cin >> n >> m >> x;

    vector<int> A(n), B(m);
    for(int i = 0; i<n; i++)
        cin >> A[i];
    for(int i = 0; i<m; i++)
        cin >> B[i];

    for(int i = 0, j = 0; i<n; i++)
    {
        int target = x - A[i];
        j = binary(B, target);
        if(B[j] == target)
        {
            cout << i << ' ' << j;
            break;
        }
    }
    return 0;
}

lowbit 运算

例题：

什么是 lowbit 运算？

它的作用是求出 n 在表示成二进制的时候，从右向左数的第一个1与右边的0所构成的数。示例如下:

lowbit(4) = lowbit(4(0100)) = 4(0100)  // 括号内表示二进制形式
lowbit(5) = lowbit(5(1001)) = 1(0001)
lowbit(6) = lowbit(6(1010)) = 2(0010)

lowbit 公式

lowbit(n) = n & -n

公式证明

在计算机中，数据的存储是以补码的形式，对于补码来说：

n >= 0： n 的补码就是它本身
-n < 0： -n 的补码为 ~n + 1~，~其中 ~n 为 n 的反码

我们可以通过一个通例来证明，假设 n=101…1000，中间的数字省略，直到展示出最右边的一个 1。

lowbit(n) = n & -n = n & (~n + 1)
n =      101...1000
~n =     010...0111
~n + 1 = 010...1000
因此lowbit(n) = n & -n = n & (~n + 1) = 1000

acwing 解答

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;

    int temp, count;
    for(int i = 0; i<n; i++)
    {
        count = 0;
        cin >> temp;
        while(temp)
        {
            count ++;
            temp -= temp & (-temp);
        }
        cout << count << ' ';
    }
    return 0;
}

小 tips：该题还可以用 bitset 类和暴力方法

leetode 解答

解题分析

观察所有 2 的幂的二进制表现形式可以知道，二进制串都只有一个 1
由上可知，既然只有一个 1，那么 lowbit(n)得到的还是 n

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
};

离散化

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：

原数据：1,999,100000,15；处理后：1,3,4,2；

原数据：{100,200}，{20,50000}，{1,400}；

处理后：{3,4}，{2,6}，{1,5}；

思路是：先排序，再去重，二分查找（就是索引元素离散化后对应的值）。

排序，先将坐标从小到大排列，便于去重操作
去重，用来去除需要离散化的值，重复的坐标离散到同一个值即可
二分查找，用来寻找某一个值经过离散化后对应的坐标

该题解题思路，要知道数轴是无限长，而待加位置 x 和 c，以及求和区间 left 和 right 的相对位置是不会改变的，因此得到如下图所示的数轴

而题目可知，数轴之间相差的位置是巨大的例如 x4 = 1， x2 = 5，x3 = 999， x1 = 1000000，那么直接使用前缀和，显而易见，是非常困难的，但是也可以知道，不同的x的位置之间、left和right位置之间相对关系没有发生改变，因此，我们可以将其位置分别拿出，然后额外用一个数组来保存他们的相对位置，也就是映射

其实我们完全没有必要对其进行映射，只要我们对我们要操作的坐标排序后，其相对位置自然而然也就出来了，而下标不正好就是他们之间相互映射的位置吗？由此在额外开一个数组，该数组用于存储我们对不同的 x 位置所加的数 c，得到如下的数组

之后求前缀和后，我们分别访问在映射关系中 L1,R1 所对应的下标 0 和 3，然后再在前缀和数组中由 0 下标和 3 下标这个区间计算得到 L1 和 R1 这个区间全部值和。

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

using namespace std;
typedef pair<int, int> PII;

vector<int>::iterator unique(vector<int> &alls)//该函数在algorithm中有，只不过这里具体实现出来了
{
    int j = 0;
    for(int i = 0; i<alls.size(); i++)
    {
        if(i != 0 || alls[i] != alls[i-1])
            alls[j++] = alls[i];
    }
    return alls.begin() + j - 1;
}

int find(vector<int> &alls, int target)//找到target所在位置
{
    int left = 0, right = alls.size(), mid = 0;
    while(left < right)
    {
        mid = (left + right) >> 1;

        if(target <= alls[mid])
            right = mid;
        else
            left = mid + 1;
    }
    return left + 1;//为什么要加1呢？要知道，我们之后要做前缀和运算，而前缀和运算最好从1开始，因此这里整体加1，方便做运算
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;

    vector<int> alls;//离散化，需要操作的所有坐标
    vector<PII> add, query;//add，用于存储对那个位置的坐标进行操作，query，需要询问的区间


    for(int i = 0, x = 0, c = 0; i<n; i++)//记录左坐标
    {
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }

    for(int i = 0, l = 0, r = 0; i < m; i++)//记录右坐标
    {
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }

    //去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls), alls.end());

    vector<int> sum(alls.size() + 1, 0);//数轴映射后的长度

    for(auto item : add)
    {
        int x = find(alls, item.first);
        sum[x] += item.second;
    }

    for(int i = 1; i<=sum.size(); i++)//求前缀和，不要忘记等于
        sum[i] += sum[i - 1];

    for(auto item : query)//标准求前缀和完事
    {
        int l = find(alls, item.first), r = find(alls, item.second);
        cout << sum[r] - sum[l - 1] << '\n';
    }

    return 0;
}

解法二：使用 map

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;

    map<int, int> ret;
    for(int i = 0, x = 0, c = 0; i<n; i++)
    {
        cin >> x >> c;
        ret[x] += c;
    }

    vector<pair<int, int>> query;
    for(int i = 0, left = 0, right = 0; i<m; i++)
    {
        cin >> left >> right;
        query.push_back({left, right});
        ret[left] += 0;
        ret[right] += 0;
    }

    int sum = 0;
    for(auto &item : ret)//求前缀和
    {
        item.second += sum;
        sum = item.second;
    }

    for(auto &item : query)
    {
        auto query_left = ret.find(item.first), query_right = ret.find(item.second);

        if(query_left == ret.begin())//起始区间在第一个位置
            cout << query_right->second << '\n';
        else//非第一个位置
        {
            --query_left;
            cout << query_right->second - query_left->second << '\n';
        }   
    }
    return 0;
}

区间合并

几个知识点

对 pair 数据进行 sort 排序，优先以 first 为关键字，当 first 相同时，以 second 为关键字排序，且升降序的方式与 first 的方式相同
排序后，区间能否合并，有三种情况，其中只有第三种情况无法合并，而一二种可以合并处理。
不要忘记最后一个区间没有可以对比的区间了，当循环结束后，也要将该区间加入到最终结果中去

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

using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> segs;

    for(int i = 0, left = 0, right = 0; i<n; i++)
    {
        cin >> left >> right;
        segs.push_back({left, right});
    }
    sort(segs.begin(), segs.end());

    vector<pair<int, int>> ret;

    int left = segs[0].first, right = segs[0].second;//以第一个区间作为对比
    for(auto & item : segs)
    {
        if(right < item.first)//依次同其他区间进行比较
        {
            ret.push_back({left, right});//当存在新的不可合并区间时，将该不可合并区间取出并入栈
            left = item.first, right = item.second;//并将下一个区间作为对比区间
        }
        else
            right = max(right, item.second);
    }
    ret.push_back({left, right});//当循环结束后，还要一个区间未入栈，因为最后一个区间没有可对比的区间了，需要手动入栈
    cout << ret.size();
    return 0;
}

树的重心

定义一：给定一棵树，如果删除某个节点，剩余各个连通块中，每个连通块含有的个数的最大值最小，那么这个节点被称为树的重心。

定义二：对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。

‍

数论

分解质因数

五分钟掌握一个小学数学知识点——分解质因数（苏教版五年级下册）_哔哩哔哩_bilibili

基本思路就是使用短除法，枚举 [0~sqrt(n)] 内的每一个质数，并且记录可以被这个数整除多少次。思路如上视频

同时根据算术基本定理，可以验证所有大于1的数都可以被分解为质因数的乘积。

int divide(int n){
    for(int i = 2; i<=n/i; i++){ // 枚举每一个因数
        if(n % i == 0){ // 如果该数是质因数
            int cnt = 0;
            while(n % i == 0) // 计数n可以被当前质因数i整除的次数
                n /= i, cnt++;
            cout << i << " " << cnt << endl; // 输出
        }
    }
    if(n > 1) // 短除法结束，判断当前数是否大于1，如果大于，那么一定是质数
        cout << n <<  " " << 1 << endl;
    cout << endl;
}

最大公约数和最小公倍数

最大公约数和最小公倍数 – 简书 (jianshu.com)

最大公约数

greatest common divisor(gcd)，使用欧几里得算法（也称之为辗转相除法）解题

int gcd(int a, int b){
    if(b)
        a = gcd(b, a % b);
    return a;
}

最小公倍数

lowest common multiple(lcm)，最小公倍数n和最大公约数m的关系，$n = (a * b ) \div m$

int lcm(int a, int b){
    int m = gcd(a, b);
    return a * b / m;
}

(101条消息) C++求解N个数的最大公约数、最小公倍数_Krasjet_Yu.的博客-CSDN博客_c++求多个数的最大公约数

算术基本原理

算术基本定理

$$
N = \prod\limits_{i=1}^k p_i^{a_i}=p_1^{a_1}\cdot p_2^{a_2}… p_k^{a_k}
$$

约数个数

$$
约数个数：\prod\limits_{i=1}^k(a_i+1)=(a_1+1)(a_2+1)…(a_k+1)
$$

每个数可以选[0, ai]次（ai + 1次），共k个数

约数之和

$$
\begin{aligned}约数之和：\prod\limits_{i=1}^k \sum\limits_{j=0}^{a_i} p_i^j & = \prod\limits_{i=1}^k (p_i^0+p_i^1+…+p_i^{a_i})
\ & = (p_1^0+p_1^1+…+p_1^{a_1})(p_2^0+p_2^1+…+p_2^{a_2})…(p_k^0+p_k^1+…+p_k^{a_k})\end{aligned}
$$

对公式做进一步拆分，即可得到形如$p_1^ap_2^bp_3^c…p_4^d$的每一个等式

欧拉函数

互质：当两个数的公因数只有1，我们称为这两个数互质

1~N中与N互质的数的个数，称为欧拉函数，记为$ϕ(N)$

若在算术基本定理中：$N=p^{a_1}_1 p^{a2}_2…p^{am}_m$，那么有

$$
ϕ(N) = N×\frac{p_1 − 1}{p1} × \frac{p_2−1}{p2} × … × \frac{p_m−1}{p_m}
$$

AcWing 873. 欧拉函数-数论-C++(详细) – AcWing

简单证明：

从N个数中去除质因子$p_1$到$p_m$的所有倍数
在去除$p_1$到$p_m$的倍数的过程中，$p_1$和$p_m$的乘积$p_1p_m$被去除了两次，因此我们需要加上$p_1p_m$
如下图，集合相交部分，被pi、pj、pk都减掉了一次，又被他们的两两乘积加了一次，最终得到的效果是没有加没有减掉，但是我们需要减掉他们相交的部分，于是我们还要减去$p_ip_jp_k$

筛法求欧拉函数

线性筛 + 欧拉函数的相关性质

对于任意一个数$N$的欧拉函数$ϕ(N)$有：

$i$是质数，那么$ϕ(i) = i – 1$

$i$不是质数，那么给定一个1~N范围内的质数表p，i与质数表的每一个质数$P_i$相乘积

如果i % p[i] == 0那么说明$P_i$是$N$的一个质因数，$ϕ(i * P_i) = ϕ(i) * P_i$

如果i % p[i] != 0那么$ϕ(i * P_i) = ϕ(i) *({P_i – 1 \over P_i }) * P_i= ϕ(i) * (P_i – 1)$

long long get(int n){
    phi[1] = 1; // 1和任何正整数都是互质的数，包括自身
    for(int i = 2; i<=n; i++){
        if(!st[i]){
            perimes[cnt++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; perimes[j] <= n / i; j++){
            st[perimes[j] * i] = true;
            if(i % perimes[j] == 0){
                phi[i * perimes[j]] = phi[i] * perimes[j];
                break;
            } else {
                phi[i * perimes[j]] = phi[i] * (perimes[j] - 1);
            }
        }
    }
    long long res = 0;
    for(int i = 1; i<=n; i++){
        res += phi[i];
    }
    return res;
}

取整

向下取整

向下取整非常简单，运用编程语言的截断机制即可(int)x / (int)y

向上取整

一种比较装的方法，x/y向上取整等价于(x + (y - 1)) / y的下取整，举例：8 / 3 = 2.666 取上整为 3，(8 + (3 - 1)) / 3 = 3

使用库函数

函数名称	函数说明	举例
`floor()`	向下取整，不大于自变量的最大整数，朝负无穷方向取整	`floor(-1.3) = -2; floor(1.3) = 1`
`ceil()`	向上取整，不小于自变量的最大整数，朝正无穷方向取整	`ceil(-1.3) = -1; ceil(1.3) = 2`
`round()`	四舍五入到最邻近的整数	`round(-1.3) = -1; round(-1.52) = -2; round(1.3) = 1; round(1.52) = 2`
`fix()`	朝零方向取整	`fix(-1.3) = -1; fix(1.3) = 1`

中国剩余定理

扩展中国剩余定理

中国剩余定理给出的解要求m1、m2、m3、···、mn两两互质。那么就会有一种情况出现，如果不两两互质，那么x又应该如何求解？

AcWing 204. 表达整数的奇怪方式 – AcWing

AcWing 204. 表达整数的奇怪方式 – AcWing

AcWing 204. 表达整数的奇怪方式-数论-C++(含推导) – AcWing

高斯消元法

通过初等行变换把 增广矩阵 化为 阶梯型矩阵 并回代得到方程的解

适用于求解包含n 个方程，n 个未知数的多元线性方程组

前置知识：初等行（列）变换

把某一行乘一个非0的数 (方程的两边同时乘上一个非0数不改变方程的解)

交换某两行 (交换两个方程的位置)

把某行的若干倍加到另一行上去（把一个方程的若干倍加到另一个方程上去）
接下来，运用初等行变换，把增广矩阵，变为阶梯型矩阵

高斯消元的步骤分为以下四步：

枚举每一行找到当前行(包括当前行)下面的，当前列的绝对值最大的一个数。

将其绝对值最大的一行移到上面

将改行的第一个数变成1

将下面所有的行的当前列都清成0

线性方程组的解有以下三种情况：

无解（转换得到的阶梯型矩阵存在某一行$a_{ij}$为0，但是$b_{i}$不为0的情况）

有无穷多个解（阶梯型矩阵存在某一行全为0，n个方程解n个未知数，当方程数少时，有无数个解）

有唯一解（阶梯型矩阵不存在$a_{ij}$全为0的行）

#include <bits/stdc++.h>
using namespace std;
vector<vector<double>> g(110, vector<double>(110, 1));
int n;
double eps = 1e-8;

int gauss(){
    int c, r; // col列，row行
    for(c = 0, r = 0; c < n; c++){
        int t = r;
        for(int i = r; i<n; i++)
            if(fabs(g[i][c]) > fabs(g[t][c]))
                t = i;

        if(fabs(g[t][c]) < eps)
            continue;

        swap(g[t], g[r]);

        for(int i = n; i>=c; i--)
            g[r][i] /= g[r][c];

        for(int i = r + 1; i<n; i++){
            if(fabs(g[i][c]) < eps)
                continue;
            for(int j = n; j>=c; j--)
                g[i][j] -= g[i][c] * g[r][j];
        }
        r++;
    }

    if(r < n){
        for(int i = r; i<n; i++){
            if(fabs(g[i][n]) > eps)
                return 2;
        }
        return 1;
    }

    for(int i = r-1; i>=0; i--){
        for(int j = i + 1; j<n; j++){
            g[i][n] -= g[i][j] * g[j][n];
        }
    }

    return 0;
}

int main(){
    cin >> n;
    for(int i = 0; i<n; i++){
        for(int j = 0; j<=n; j++)
            cin >> g[i][j];
    }

    int t = gauss();

    if(t == 0){
        for(int i = 0; i<n; i++){
            if(fabs(g[i][n]) > eps)
                printf("%.2lf\n", g[i][n]);
            else
                printf("0.00\n");
        }
    } else if(t == 2)
        printf("No solution\n");
    else
        printf("Infinite group solutions\n");

    return 0;
}

求组合数

组合数性质

巧记：$C_n^2 = {n * (n – 1)\over 2} = 1 + 2 + 3 + ··· + (n – 1)$

组合数性质

组合数的求法有很多种，但是具体要根据数据量大小来求

0 < a, b < 2000，可以使用公式$C_a^b = C_{a-1}^b + C_{a-1}^{b-1}$预处理这个范围内的$C_a^b$
0 < a, b < 1e5，且要求模一个定数p，范围较大，使用公式的定义整理好任何数的阶乘，两者相除即可，这里除法可以使用乘法逆元来优化
0 < a, b < 1e18，0 < p < 1e5，要求对每组C_a^b都模以特定p，范围更大，使用卢卡斯（lucas）定理来优化到较小范围，之后在使用普通组合数计算方法即可
0 < a, b < 5000，不取模，范围不大，但是要求不取模，因此得到的结果会很大，我们可以尝试分解质因数 + 高精度乘法来解决

Lucas定理

543 求组合数卢卡斯定理_哔哩哔哩_bilibili

Lucas（卢卡斯）定理用于求解大组合数取模的问题，其中模数必须为素数。正常的组合数运算可以通过递推公式求解（详见排列组合），但当问题规模很大，而模数是一个不大的质数的时候，就不能简单地通过递推求解来得到答案，需要用到 Lucas 定理。

观察上述表达式，可知 $n\bmod p$ 和 $m\bmod p$ 一定是小于p的数，可以直接求解，$C^{\left\lfloor n/p \right\rfloor}_{\left\lfloor m/p \right\rfloor}$可以继续用 Lucas 定理求解。这也就要求p的范围不能太大，一般在$10^5$左右

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int p;
LL qmi(LL a, LL b){
    LL res = 1;
    while(b){
        if(b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

// 使用组合数的常规手算方法
LL C(LL a, LL b){
    LL res = 1;
    for(int i = 1, j = a; i<=b; i++, j--){
        res = res * j % p;
        res = res * qmi(i, p - 2) % p;
    }
    return res;
}

// 核心代码
LL lucas(LL a, LL b){
    if(a == 0)
        return 1;
    return C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main(){
    int n;
    cin >> n;
     while (n -- ){
         LL a, b;
         cin >> a >> b >> p;
         cout << lucas(a, b) << endl;
     }
    return 0;
}

Catalan数

548 卡特兰数_哔哩哔哩_bilibili

Catalan（卡特兰）数的几何意义

卡特兰数就是一个有规律的数列，在坐标图中可以表示为：从原点(0,0)出发，每次向x轴或者y轴正方向移动1个单位，直到到达(n,n)点，且在移动过程中不越过第一象限平分线的移动方案总数。

总共移动了2n步，其中向上n步，向右n步。

暂且先不考虑移动过程中不越过第一象限平分线这个约束条件，那么从(0,0)到(n,n)就是从2n步中选择n步向右（上）移动，方案数有$C_{2n}^n$种

现在，我们来看看如何解决不越过第一象限平分线这个问题。仔细想想，不越过第一象限平分线也就等价于不触碰到y = x + 1这条直线。而我们如果把触碰到了直线y = x + 1的路线的第一个与y = x + 1的触碰点之后的路线关于直线y = x + 1对称，并画出对称后的路线，我们会发现触碰到了直线y = x + 1的路径的终点都变成了点(n-1,n+1)。

也就是说，从(0,0)点到(n,n)点的路线当中触碰了直线y = x + 1的路线条数与从(0,0)点到(n-1,n+1)点的路线条数的数量是相等的。

于是从(0,0)点到(n,n)点的非法路径条数为$C_{2n}^{n+1}$（2n步中向上走n+1步，或者2n步中向右走n-1步）

综上所述，从(0,0)点到(n,n)点满足条件的路径数为$C_{2n}^n – C_{2n}^{n+1}$，公式化简如下：

扩展：

#include <iostream>
using namespace std;
const int N = 1e5+10, mod = 1e9 + 7;

long long qmi(long long a, long long b, long long p){
    long long res = 1;
    while(b){
        if(b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

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

    int a = 2 * n, b = n;
    long long res = 1;
    for(int i = a; i> a - b; i--)
        res = res * i % mod;
    for(int i = b; i>=1; i--)
        res = res * qmi(i, mod - 2, mod) % mod;

    cout << res * qmi(n+1, mod - 2, mod) % mod << endl;
    // 商的余数不能直接通过 分子的余数 和 分母的余数 来计算，所以一般把除法转化成乘法来处理。因此除以n+1需要乘以n+1的乘法逆元

    return 0;
}

‍

一	二	三	四	五	六	日
				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

AcWing 笔记

高精度算法

高精度加法

高精度减法

高精度乘法

高精度除法

前缀和与差分

前缀和

一维前缀和

二维前缀和

差分

差分的运用

1、介绍

2、定义

3.与前缀和的关系

一维差分

1、定义

2、作用

解题代码一

解题代码二

二维差分

解题思路

解题代码一

解题代码二

双指针

题目一

题目二

解题方式一：双指针

解题方式二：二分搜索

lowbit 运算

什么是 lowbit 运算？

lowbit 公式

公式证明

acwing 解答

leetode 解答

离散化

区间合并

树的重心

数论

分解质因数

最大公约数和最小公倍数

最大公约数

最小公倍数

算术基本原理

约数个数

约数之和

欧拉函数

筛法求欧拉函数

取整

向下取整

向上取整

中国剩余定理

扩展中国剩余定理

高斯消元法

求组合数

Lucas定理

Catalan数

Catalan（卡特兰）数的几何意义

发送评论 编辑评论

推荐文章

发送评论编辑评论