irai の 知识文档站

Appearance

🔎 基础算法 ​


  • 备注：基于 Acwing 的 irai 个人笔记记录

一、快速排序 ​


c++
#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int a[N];

void quick_sort(int q[], int l, int r){
    //递归边界条件
    if(l >= r) return;
    //确定边界点 (取中点会保证避免当序列已经有序或所有元素相同时退化到 O(n²))
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    while(i < j){
        //确保左边都是小于等于 x 的
        do i ++; while(q[i] < x);
        //确保右边都是大于等于 x 的
        do j --; while(q[j] > x);
        //退出循环就可以做交换
        if(i < j) swap(q[i],q[j]);
    }

    //递归处理左右两段
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

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

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

    quick_sort(a, 0 , n - 1);

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

    return 0;
}

二、归并排序 ​


c++
#include <iostream>

using namespace std;

int n;
const int N = 1e5 + 10;
int q[N], tem[N];

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

    //归并左右两边(已经有序的)
    // k 代表当前合并到第几个下标的元素(0 开始算)，也就是指 tem 的下标
    // i 为左边起点，j 为右边起点
    int k = 0 , i = l, j = mid + 1;
    while(i <= mid && j <= r){ //左右两边都没到终点(任一到了都可以结束循环)
        if(q[i] <= q[j]) tem[ k ++ ] = q[ i ++ ];
        else tem[ k ++ ] = q[ j ++];
    }
    //哪边还有剩余的元素就可以全部放到 tem 尾部 (扫尾)
    while(i <= mid) tem[ k ++ ] = q[ i ++ ];
    while(j <= r) tem[ k ++ ] = q[ j ++ ];

    //最后把 tem 的移动到原数组中 (物归原主)
    for(int i = l , j = 0; i <= r; i ++, j ++) q[i] = tem[j];
}

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

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

    merge_sort(q, 0, n - 1);

    for(int i = 0; i < n; i ++) printf("%d ", q[i]);

    return 0;
}

三、整数二分 ​


c++
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n, q;
int a[N];


// 返回 l - r 区间内，第一个大于等于x的位置
int b_search1(int l, int r, int x){
    while(l < r){
        int mid = (l + r) >> 1;
        if(a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

// 返回 l - r 区间内，第一个小于等于x的位置
int b_search2(int l, int r, int x){
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(a[mid] <= x) l = mid;      // 这里 l = mid 上面要加一
        else r = mid - 1;
    }
    return l;
}

int main()
{
    // 数组长度和询问个数
    cin >> n >> q;

    // 存储 n 个 整数
    for(int i = 0; i < n; i ++ ) cin >> a[i];

    while( q -- ){
        // 接下来 q 行，每行有一个k，表示询问元素
        int k;
        cin >> k;
        // 起始位置
        int start = b_search1(0, n - 1, k);
        // 如果没有这个元素的话 -1 -1 
        if(a[start] != k){
            cout << "-1 -1" << endl;
            continue;
        }
        // 有这个元素再找终止位置
        int end = b_search2(0, n - 1, k);
        cout << start << ' ' << end << endl;
    }

    return 0;
}

四、浮点数二分 ​


c++
#include <iostream>
using namespace std;

int main(){
    double n;
    scanf("%lf", &n);
    // 取最大的数据范围让它自己趋近就不会有问题
    double l = -10000, r = 10000;
    //一般题目精度 1e-6, 那么我们就 1e-8. 精度 1e-4 我们就 1e-6
    while(r - l >= 1e-8){
        double mid = (l + r) / 2;
        if(mid * mid * mid >= n) r = mid;
        else l = mid;
    }
    printf("%lf", r);
    return 0;
}

五、高精度加法 ​


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

const int N = 1e5 + 10;

 
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; // 商是进位
    }
    // 退出循环还有进位的话那么再补一个 1 
    if(t) c.push_back(1);
    
    return c;
}

int main()
{
    string a, b;
    vector<int> 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');
    
    // 高进度加法
    auto C = add(A , B);
    
    // 逆序输出回来
    for(int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
    
    return 0;
}

六、高精度减法 ​


c++
#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

// 判断是否有 a >= b
bool cmp(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;
    for(int i = 0, t = 0; i < a.size(); i ++){
        t = a[i] - t;
        // a 的位数是大于等于b的位数的，要保证b还有才减
        if(i < b.size()) t -= b[i];
        C.push_back((t + 10) % 10);
        if(t < 0) t = 1; // 有借位
        else t = 0;
    }
    
    //去除前导 0 
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main()
{
    string a , b;
    vector<int> A, B;
    cin >> a >> b; // "123456"
    
    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');
    
    // cmp : 确保做的是大数减小数
    if(cmp(A , B)){
        auto C = sub(A, B);
        for(int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
    }
    else{
        auto C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
    }

    return 0;
}

七、高精度乘低精度 ​


c++
#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
vector<int> A;

//高精度乘低精度
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; // 位数还没超过 A
        C.push_back(t % 10); // 余数为该位结果
        t /= 10;	// 商为进位
    }
    
    // 去除前导 0
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main()
{
    int b;
    string a;
    cin >> a >> b;
    // 对于 a 的大整数存储
    for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    
    auto C = mul(A, b);
    
    for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    
    return 0;
}

八、高精度除低精度 ​


c++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
vector<int> A;

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());
    
    //去除前导0
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main()
{
    int b;
    string a;
    cin >> a >> b;
    for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    int r= 0;
    auto C = div(A, b, r);
    
    for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl << r << endl;
    
    return 0;
}

九、一维前缀和 ＆ 区间和 ​


微信截图_20251122164120

  • 黄色部分为 s[r] , 绿色部分为 s[l - 1] , 其中下标 0 和下标 1 为 先黄色再被绿色减去

    那么计算出来的区间和就是黄色部分 ：12 - 2 = 10 ==> 6 + 3 + 1 = 10


  • 示例代码：
c++
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n, m;
int a[N], s[N];

int main()
{
    cin >> n >> m;
    // 读入整数数列( 从 1 开始  [1,n] 左闭右闭 )
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    //求前缀和数组
    for(int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
    while( m -- ){
        // m 次询问区间和
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    
    return 0;
}

十、二维前缀和 ＆ 子矩阵和 ​


微信截图_20251122165436

  • 要计算左侧 (2,3) 的前缀和 ， 对应是 右边的 21

  • 先给公式：s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]

  • 解释：s[i - 1][j] 为浅绿色部分的前缀和， s[i][j - 1] 为黄色部分前缀和

    那么如果加上这两部分会发现图中粉色部分被加了两次，那么需要减去一次即 s[i - 1][j - 1]

    前面的部分就获取到了左边原矩阵 粉色黄色和浅绿色部分,那么加上 a[i][j] 就是 s[i][j]

  • 对应样例：21 = 17 + 10 - 8 + 2


  • 容斥原理求解子矩阵和：
微信截图_20251122170156

  • 假设要求解原矩阵中粉色部分的子矩阵和 【(x1,y1) 为子矩阵左上角坐标，(x2,y2) 为右下角坐标】

  • 先给公式：s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

  • 也就是图中 子矩阵右下角 (3,3) 的前缀和减去橙色部分的前缀和再减去浅绿色部分的前缀和

    发现有紫色部分被多减了一次， 那么再加上紫色部分前缀和，那么就剩粉色部分子矩阵和

  • 对应样例：6 + 2 + 1 + 2 = 11 = 26 - 6 - 10 + 1 = 11


  • 示例代码：
c++
#include <cstdio>

const int N = 1010;
int a[N][N];    // 存储原矩阵
int s[N][N];    // 存储前缀和矩阵
int n, m, q;

int main()
{
    // n 行 m列 q次询问
    scanf("%d %d %d", &n, &m, &q);
    // 读入原矩阵并计算前缀和
    // 前缀和的问题还是从下标为 1 开始, 可以避免边界问题
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
        {
            scanf("%d", &a[i][j]);
            // 容斥原理计算前缀和
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }

    // q 次询问，返回子矩阵的和
    while( q -- ){
        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]);
    }
    return 0;
}

十一、差分 ​


c++
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N],b[N];

// 对 [l,r] 这个范围加上 c
void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    int n,m;
    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 -- ){ // 处理 m 次操作
        int l, r, c;
        scanf("%d %d %d", &l, &r, &c);
        insert(l, r, c);
    }

    // 求出 差分数组 b 的前缀和
    for(int i = 1; i <= n; i ++) b[i] += b[i - 1];

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

    return 0;
}

十二、二维差分 ​


c++
#include <iostream>
using namespace std;
const int N = 1010;

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

// 在范围 【x1, y1】 ~ 【x2, y2】 这个子矩阵统一 做 + c 操作
void insert(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()
{
    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]);
    // 处理 q 次操作
    while( q -- ){
        int x1, y1, x2, y2, c;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    // 求出差分矩阵 b 的前缀和
    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];
    // 输出矩阵
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            printf("%d ", b[i][j]);
        }
        puts("");
    }
    
    return 0;
}

十三、双指针 ​



十四、位运算 ​


  • 核心操作：

    • ❓ ​某个十进制数 n 的二进制表示中第 k 位是什么

      • 1). 先把第 k 位移到最后一位 n >> k
      • 2). 看个位是什么 x & 1
      • ➡️ 则 ：n >> k & 1

    • ❓ 某个十进制数的二进制表示的最后一位 1 及其后面的 0 对应是十进制数是什么

      • 上面的描述对应一个函数 lowbit(int x)

      • 如十进制数 10 的二进制是 1010 , 那么 lowbit(10) 就是 10 就是十进制 2

      • 思路：在计算机系统中数值一律用 补码 来表示和存储，而正数的补码与原码相同，

        负数的补码是反码加一。那么也就是说 : -x => (~ x + 1) , （~ 是取反的意思）

        那么如果我们做 x & -x 也就是 x & (~ x + 1) 的话。自己简单验证可以发现

        结果就是返回上面问题的描述

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

  • 模板题：801. 二进制中1的个数

  • 示例代码：

c++
#include <iostream>
using namespace std;

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

int main()
{
    int n;
    cin >> n;
    while( n -- ){
        int x;
        cin >> x;
        int res = 0;
        while(x){
            x -= lowbit(x);
            res ++;
        }
        cout << res << ' ';
    }
    
    return 0;
}

十五、离散化 ​


十六、区间合并 ​


Copyright © 2025 irai. All rights reserved | 粤ICP备2024313367号-1