基础算法

基础算法

排序

快速排序

• 思想：分治策略
• 稳定性：不具有稳定性(因为值可能相同)。可以将pair<a[i], i>作为二元组排序就可以使其具有稳定性
• 步骤：
  • 1. 确立分界点： l, r, (l + r) / 2, 随机对应下标的数组里的值作为x
    2. 调整：分为两段，第一段<=x，第二段>=x
    3. 递归处理左右两段

模板：无需考虑边界问题

void quick_sort(int q[], int l, int r)
{
    //判断边界，只有一个元素或没有元素必然有序直接返回。
    if (l >= r) return;

    //先移动再判断，所以初始化要多一格。
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < 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);
}

归并排序

• 思想：分治策略
• 稳定性：具有稳定性
• 步骤：
  • 1. 确定分界点：mid = (l + r) / 2，下标的值
    2. 递归排序left和right
    3. 归并(合二为一) \(O(n)\) 重复 \(log(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);
	
    //归并的过程，注意下标与上面的对应
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
	//继续处理剩下的没排完的,只会运行一个
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
	
    //将临时数组复制回q
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

二分

整数二分

• 条件：有单调性的一定能二分，能二分的不一定有单调性。二分的本质不是单调性。
• 本质：边界。存在某种性质，可以把整个区间一分为二，二分就可以寻找这个性质的边界。
• 边界：该性质将区间一分为二后，左边区间的右端点和右边区间的左端点分别对应两种模板。
• 有解性：二分一定有解，但题目不一定有解，最后需要判断是否符合题意
• 步骤：
  • 1. 如何选择模板，先写出check(mid)函数
    2. 思考如何根据这个函数更新区间，满足性质的时候，边界在右面还是在左面，保证区间内一定有答案
    3. l = mid 或者 r = mid，前者在mid初始化时需要+1。使其离边界“更近”，防止死循环

模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分

• 特点：不需要处理边界，标准的二分
• 结束标志：区间长度足够小，即 r - l <= 1e-6 等类似数字。或直接循环指定迭代的次数N，相当于精度\(\frac{区间长度}{2^N}\)
• 经验值：题目要求保留n位小数，那么r - l <= 1e-(n+2)

模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

练习1

Acwing785-790.

高精度

高精度加法

• vector<int>存储大整数的每一位，个位在前（方便进位）
• 步骤：
  • 1. 从个位开始遍历
    2. 设置进位位，初始为t = 0
    3. 按位加上两个整数每一位的值（需判断下标是否在两个整数各自的大小内），若结果大于10，则判断发生进位t = 1
    4. 循环结束后，还要判断t的值，如果为1，需要加上一位1在数组末尾，表示最终的进位。

模板

// C = A + B, A >= 0, B >= 0
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(t);
    return C;
}

高精度减法

• 存储方式与加法一致
• 大小判别放到使用时判断
• 步骤：
  • 1. 从个位开始遍历
    2. 设置借位位，初始为t = 0
    3. 先减去上一位的t，按位加上两个整数每一位的值（需判断减数下标是否在其大小内）
    4. 合并处理减完后大于零小于零的情况。若小于零，还要令t = 1，表明需要借位。
    5. 循环结束后，去掉前导零，同时令位数不少于1

模板

// C = A - B, 满足A >= B, A >= 0, B >= 0
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);	//合并处理减完后大于零小于零的情况
        if (t < 0) t = 1;
        else t = 0;
    }

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

高精度乘低精度

• 与加法类似
• 大数乘相对小的数，并且实现时将小的数作为整体，按位处理大数的值
• 防止数据存在乘0的情况，要加入处理前导零的步骤
• 从个位开始遍历

模板

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

高精度除以低精度

• 为了方便与其他运算结合，存储方式仍然采用之前的
• 从最高位开始遍历，与之前不同
• 答案的存储方式不同，返回前要使用algorithm中的reverse方法将元素倒转
• 注意顺序：先倒转再去前导零

模板

// 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\)：

\[ S_i=a_1+a_2+\cdots+a_i , S_0=0 \]

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

注意：下标一定从1开始，避免边界判断条件

• 作用：快速求出任意区间的和[L,R]->\(S_R-S_{L-1}\)

二维前缀和

\[ S[i, j] = 第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] + s[i-1][j] + a[i][j];
	}
}

• 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：

\[ S[x_2, y_2] - S[x_1 - 1, y_2] - S[x_2, y_1 - 1] + S[x_1 - 1, y_1 - 1] \]

差分

• 构造\(b_i\)，一般不需要，以0数组为基准进行增减操作，最后再处理成原数组的增减即可。

\[ b_i=a_i-a_{i-1} \]

• 与前缀和互为逆运算
• 作用：对区间增减一个值，可由复杂度\(O(n)\)变为\(O(1)\)
• 例如，要使期间[L,R]每个数都+c，则可使b[L]+c且b[R+1]-c