第一讲基础算法¶

一道题重复三到五次就能有很好的记忆了，课上主要理解思想

排序¶

快速排序¶

快速排序的只要实现方法是同一个数组之内大小数的直接互相交换

主要思想：分治

确定分界点：q[l], q[(l+r)/ 2], q[r]
调整区间，使得第一个区间里的数都小于等于x，使得右边区间的数都大于等于x
递归：递归处理左右两段

优美的做法：不需要开辟额外空间

使用双指针：swap两边同时向中间读取的那个不符合的数字

想法：任意时刻，i指针左边的值都是小于i的（必须是小于），j指针后边的值都是大于j的；分别移动，等到他们两个互相越过，就能使整个数组排列完整

凡是要处理边界问题的算法，最好都背过一个模板即可，这样可以保证没有问题

考试的时候没有充足的时间去考虑边界问题的

785. 快速排序代码模板¶

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int x = q[l + r >> 1], i = l - 1, j = 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); 
} 

int main () {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++) printf("%d ", q[i]);
    return 0;
}

面试的时候会手写快排，包括学长也提到了面试的时候会写快速排序

快速选择算法¶

AcWing 786. 第k个数¶

使用快速选择算法，快速选择算法的时间复杂度是On

边界法则：

由于除法的位运算是向下取整，所以在递归的时候，(l, j)对应两种int x写法即int x = q[l + r >> 1]和int x = q[l]

而(l, i - 1)只能对应int x = q[r]

// 快速选择的时间复杂度是On
// 快速选择是在快速排序的基础上改进的
#include <iostream>
using namespace std;
const int N = 100010;
int n, k;
int q[N];

int quick_sort(int l, int r, int k) {
    if (l == r) return q[l];
    int x = q[l], i = l - 1, j = r + 1;
    while (i < j) {
        while (q[++i] < x);
        while (q[--j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    int sl = j - l + 1;
    if (k <= sl) return quick_sort(l, j, k);
    return quick_sort(j+1, r, k - sl);
}

int main () {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> q[i];
    cout << quick_sort(0, n-1, k) << endl;
    return 0;
}

归并排序¶

归并排序的主要实现方法是将两个数组中的数按大小依次放到第三个数组当中去，合并链表也是这个思想

归并排序的算法是稳定的：指原序列中两个相同的值在排序后顺序不会发生变化，快排是不稳定的

归并排序的主要思想也是分治

快排是以一个数来分的，而归并是按照整个数组的最中间来分的（归并是下标的中间值，而快排是数组里随机一个值都行）

快排是先排序再递归，归并是先递归，因为需要保证上层归并的时候两个数组必须要从小到大排列

快排和归并的时间复杂度都是n longn

每层都是n，然后一共log2n层

787. 归并排序代码模板¶

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N], tmp[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++];
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[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;
}

归并排序、快速排序和sort库函数差不多快

788. 逆序对的数量¶

//主要思想是右边的数一旦比左边的某个数小，那么左边后面的数一定会大于右边的那个数
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int q[N], temp[N];

long long merge_count (int q[], int l, int r) {
    if (l == r) return 0;
    int mid = (l + r) >> 1;
    long long ans = merge_count(q, l, mid) + merge_count(q, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) temp[k++] = q[i++];
        else { 
            ans += mid - i + 1;
            temp[k++] = q[j++];
        }
    }
    while (i <= mid) temp[k++] = q[i++];
    while (j <= r) temp[k++] = q[j++];
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
    return ans;
}

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

    cout << merge_count(q, 0, n- 1) << endl;
    return 0;
}

二分¶

整数二分¶

有很多边界问题，写得不好会发生死循环

二分的本质并不是单调性，而是边界

定一个分界线（无重合点），两边的性质不一样即可

二分可以寻找性质的边界

如果有单调性的话，一定可以二分；但是可以二分的题目，不一定需要单调性

找到一个性质将区间一分为二，左半边不符合，有半边符合，而二分可以寻找这个性质的边界

做二分问题，先写一个check，(l = mid时前面mid+1即可)

二分模板一共有两个，分别适用于不同情况。算法思路：假设目标值在闭区间[l, r]中，每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

二分问题模板的选择是通过先写check函数来决定的

对于是否要加1的思考是通过看r只比l大1的情况下，是否会发生死循环

版本1¶

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本2¶

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

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

即：(l = 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; // 这个+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;
}

为什么要补上+1？：

c++整数除法是下取整
假设l只比r小1， l = r - 1，那么看(l+r) / 2 = l
如果check成功那么l = mid = l，等于没变，会陷入死循环

二分是用来求边界的，这道题的特征是寻找左右两个边界

二分一定会出一个结果，但是结果并不一定谁题目要求的

789. 数的范围¶

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int q[N];

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    while (m--) {
        int x;
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (r + l) >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1; // 这个+1是因为判断时是单纯的小于，没取到等号
        }
        // 循环到最后l 一定等于 r，而如果没有二分出来，取出的值也肯定不是x
        if (q[l] != x) cout << "-1 -1" << endl;
        else {
            cout << l << ' ';
            int l = 0, r = n -1;
            while (l < r) {
                int mid = (r + l + 1) >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}

浮点数二分¶

浮点数二分因为没有整除这个东西，所以直接就能做

当r - l < 1e-6的时候就可以r和l是一个数了

这个精度值至少要比结果的有效位数多2，比如保留5位小数，就需要r - l < 1e-7

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

求平方根：

#include <iostream>
using namespace std;

int main () {
    double x;
    cin >> x;
    double l = 0, r = x;
    while (r - l > 1e-8) { // 直接循环100次也是相同的效果
        double mid = (l + r) / 2;
        if (mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf\n", l);
    return 0;
}

790. 数的三次方根¶

#include <iostream>
using namespace std;

int main () {
    double n;
    cin >> n;
    double l = -10000, r = 10000;
    while (r - l >= 1e-7) {
        double mid = (l + r) / 2;
        if (mid * mid * mid > n) r = mid;
        else l = mid;
    }
    printf("%.6lf\n", l);
    return 0;
}

高精度¶

只有c++需要高精度，java和python用不到

java有大整数类，python是自带的

笔试偶尔出现的

高精度

高精度加法¶

存数字方法：第0位存个位

123456789 存成数组变成987654321，因为会有进位

高精度加法运算是个模拟人工加法的过程

一般习惯用vector来表示大整数，因为自带size这个函数表示数组的长度

不用原生数组的原因是有可能会有进位，进位之后的数组长度就不能确定了

加上引用是为了提高效率，如果不加引用的话，这个函数就会把整个数组拷贝一遍

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

vector<int> add(vector<int> &A, vector<int> &B) { //加上引用是为了提高效率，如果不加引用的话，这个函数就会把整个数组拷贝一遍
    vector<int> C;
    int carry = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++) {
        if (i < A.size()) carry += A[i];
        if (i < B.size()) carry += B[i];
        C.push_back(carry % 10);
        carry /= 10;
    }
    if (carry) C.push_back(1);
    return C;
}

int main () {
    string a, b; // ("123456")
    cin >> a >> b;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); // 这里是char类型的数字，-'0'让他变成真正的int
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0'); //从后向前，变成'123456'
    vector<int> C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    return 0;
}

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

int mian () {
    string a, b;
    cin >> a >> b;
    vector<int> 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 = add(A, B);
    for (int i = 0; i < C.size(); i++) printf("%d", C[i]);
    return 0;
}

高精度减法（有很多细节）¶

大整数的存储格式是一致的

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

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, carry = 0; i < a.size(); i++) {
        carry = a[i] - carry;
        // cout << carry << endl;
        if (i < b.size()) carry -= b[i];
        // cout << carry << endl;
        c.push_back((carry + 10) % 10);
        if (carry < 0) carry = 1;
        else carry = 0;
        // cout << carry << endl;
    }
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

int main () {
    string num1, num2; // 12, 123
    cin >> num1 >> num2;
    vector<int> a, b;
    for (int i = num1.size() - 1; i >= 0; i--) a.push_back(num1[i] - '0'); // 21
    for (int i = num2.size() - 1; i >= 0; i--) b.push_back(num2[i] - '0'); // 321

    if (cmp(a, b)) {
        vector<int> c = sub(a, b);
        for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    } else {
        vector<int> c = sub(b, a);
        printf("-");
        for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    }
    return 0;
}

高精度乘法¶

注意这道题里面A很大，B很小

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

vector<int> mul(vector<int> &a, int b) {
    vector<int> c;
    for (int i = 0, carry = 0; i < a.size() || carry; i++) {
        if (i < a.size()) carry = a[i] * b + carry;
        c.push_back(carry % 10);
        carry /= 10;
    }
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

int main () {
    string num1;
    int b;
    cin >> num1 >> b;
    vector<int> a;
    for (int i = num1.size() - 1; i >= 0; i--) a.push_back(num1[i] - '0');
    vector<int> c = mul(a, b);
    for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    return 0;
}

高精度除法¶

reverse函数需要#

余数是通过在定义function的时候传回去的

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

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

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');
    int r;
    auto C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
    cout << endl << r << endl;
    return 0;
}

A1 = 123 r = 4

1234 = a1 * 10 + r

自己的方法：

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

vector<int> div(vector<int> &a, int &b, int &r) {
    vector<int> c;
    r = 0;
    for (int i = 0; i < a.size(); i++) {
        r = r * 10 + a[i];
        // cout << r << endl;
        if (r >= b) c.push_back(r / b);
        else c.push_back(0);
        // cout << r << endl;
        r %= b;
    }
    while(c.size() > 1 && c.front() == 0) c.erase(c.begin());
    return c;
}

int main () {
    string a; // 123
    int b, r; // b = 11 
    cin >> a >> b;
    vector<int> A;
    for (int i = 0; i < a.size(); i++) A.push_back(a[i] - '0'); // 123
    vector<int> c = div(A, b, r);
    for (int i = 0; i < c.size(); i++) printf("%d", c[i]);
    cout << endl << r << endl;
    return 0;
}

前缀和与差分¶

前缀和就是数列的前n项之和

前缀和，有个长度为n的数组

前缀和数组si定义成原数组里的前i个数组而且数组是从1开始的

下标从1开始是为了能定义s0

[1, 10] s10 - s0

s0定义成0

整个时间复杂度是O1

如何求si

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

前缀和si的作用

能快速求出原数组中一段数的和

795. 前缀和¶

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n, m; // 可以将s0直接初始化为1
int a[N], s[N];


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++) s[i] = s[i - 1] + a[i];
    while (m -- ) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

二维前缀和¶

快速求某个子矩阵的和

sij 表示aij及其左上角所有元素的和

求和：(X1, y1) (x2, y2) sx2y2 - sx2y1-1 - Sx1-1y2 + sx1-1y1-1

x是行，y是列

AcWing 796. 子矩阵的和¶

for (int i : 1-n) 
  for(int j :1-n)
    sij = si-1j + sij-1 - si-1j-1+aij

#include <iostream>

using namespace std;

const int N= 1010;
int n, m, q;
int a[N][N], s[N][N];
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 ++) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
    while (q--) {
        int x1, x2, y1, 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;
}

差分¶

差分是前缀和的逆运算

构造b数组b1\b2，使得ai = b1 + ... bi，a是b的前缀和

方法：b1=a1

B2 = a2 - a1

b3 = a3 - a2

b是a的差分，a是b的前缀和

可以假定an全是0，然后进行插入

如果数组A是B的前缀和，则B是A的差分。我们构造一个数组的差分矩阵，是为了针对频繁的对数组中某个区间进行同一操作。例如将序列中[l, r]之间的每个数加上c这一操作，可能执行n次，每次的c不同，如果对原数组进行操作，每次操作都会花费O(n)的时间复杂度。如果使用该数组的差分数组进行操作，每次操作为O(1)。然后求差分数组的前缀和即为所求结果。

AcWing 797. 差分¶

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

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++) insert(i, i, a[i]);
    while (m--) {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    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;
}

二维差分¶

x是行，y是列

给定一个a数组，现在假想一个b数组是a数组的前缀和

给一个矩阵加c

Bx1y1 += c

bx2+1y1 -=c

bx1y2+1 -= c

bx2+1y2+1 += c

AcWing 798. 差分矩阵¶

对于差分是不需要考虑如何构造差分数组的

只要将每一个a[i]看成是对(i, i)位置的a[i]数值的插入即可

#include <iostream>
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[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]);

    while(q--) {
        int x1, y1, x2, y2, c;
        cin >> 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++) {
            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;
}

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

双指针算法¶

归并排序中合并序列用的就是双指针算法

第一类：两个指针指向两个序列

第二大类：两个指针指向一个序列，比如快排的过程

代码结构一般是:

for (int i = 0, j = 0; i < n; i++) {
  while(j < i && check(i,j)) j++;
}

最核心的性质是可以优化暴力做法（两个嵌套循环O(n ^ 2)）的复杂度

用两个指针扫描一个序列的复杂度是O(n)

KMP也是双指针算法

例题：输出字符串中每个用空格隔开的单词¶

#include <iostream>
#include <string.h>
using namespace std;
const int N = 10000;
int main () {
    char str[N];
    fgets(str, N, stdin);
//    printf("%s", str);
    int n = strlen(str);
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && str[j] != ' ') j++;
        for (int k = i; k < j; k++) printf("%c", str[k]);
        cout << endl;
        i = j; // 因为每个循环结束之后都有i++，所以只要i = j即可
    }
    return 0;
}

只要能将暴力算法时间复杂度为n^2的情况降到n，就可以被看成双指针算法

### 最长连续不重

双指针的算法可以从暴力的思路开始思考

j的含义：往左最远能到什么地方

双指针算法：O(n)

for (int i = 0, j = 0; i < n; i ++) {
  while (j <= i && check(i, j)) j++;
  res = max(res, i - j + 1);
}

这道题的check开个数组动态记录当前数组中每个数出现了多少次

#include <iostream>
using namespace std;
const int N = 100010;
int a[N], s[N];
int main () {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int res = 0;
    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;
    return 0;
}

另外开一个数组来记录一段数中重复的个数，非常精髓

双指针的思路都是先暴力做，然后再把时间复杂度降下来

800.数组元素的目标和¶

// 和纯暴力算法的区别在于，其中一个指针不会回退
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];

int main () {
    int n, m, x;
    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(a[i] + b[j] > x) j--;
        if (a[i] + b[j] == x) printf("%d %d\n", i, j);
    }
    return 0;
}

2816.判断子序列¶

我自己的做法：很复杂很繁杂

#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];

int main () {
    int n, m;
    cin >> n >> 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 && j < m; i++, j++) {
        // cout << "dd1" << endl;
        while(b[j] != a[i] && j < m - 1) {
            j ++;
            // cout << "oops";
            // cout << "dd2" << endl;
        }
        // cout << "dd3" << endl;
        if (i == n - 1) {
            if (a[i] == b[j]) {
                cout << "Yes";
                break;
            } else {
                cout <<  "No";
                break;
            }
        } 
        if (j == m - 1) {
            if (i == n - 1) {
                cout << "Yes";
                break;
            } else {
                cout << "No";
                break;
            }
        } 
        // cout << i << j << endl;
        // cout << a[i] << b[j]<< endl;
    }

    return 0;
}

简洁做法

#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
int main () {
    int n, m;
    cin >> n >>m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    int i = 0;
    for (int j = 0; j < m; j ++) {
        if (i < n && a[i] == b[j]) i++;
    }
    if (i == n) {
        puts("Yes");
    } else {
        puts("No");
    }
    return 0;
}

简介做法2

#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];

int main () {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> 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;
}

位运算¶

最常用的位运算的操作：

n的二进制表示中从右往左第k位（从0位开始算）是几 15 (1111)¶

先把第k位数字移到最后一位，使用位移运算，n >> k

看下个位是几，x & 1

和在一起，即n >> k & 1

例：将10的二进制数字输出出来（1010）使用位运算¶

#include <iostream>
using namespace std;

int main () {
    int x = 10;
    for (int k = 3; k >= 0; k--) cout << (x >> k & 1) << " ";
    return 0;
}

low bit操作¶

他是树状数组的基本操作

Lowbit(x)作用是返回x的最后一位1

x = 1010 lowbot(x) 返回10

x = 101000 返回1000

实现的方法是x & -x = x & (~x + 1)

一个整数的负数就是原数的补码，而补码是取反+1

负的x就是x取反+1

-x = ~x + 1

lowbit的作用是得到x的二进制中有多少个1

二进制中1的个数¶

#include <iostream>
using namespace std;
const int N = 100010;
int a[N];

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

int main () {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        int res = 0;
        cin >> x;
        while (x) x -= lowbit(x), res++; 
        cout << res << " ";
    }


    return 0;
}

原码、反码、补码¶

原码x = 1010

反码x = 0101

补码 0110补码等于反码+ 1

计算机底层实现中是没有减法的

int n = 10;
unsigned int x = -n;

离散化¶

特指整数的离散化

有序的、保序的离散化

a[]: 1, 3, 100, 2000, 5000000

可以将a[]映射到0, 1, 2, 3, 4

a[]中可能重复的元素，可以去重
如何算出x离散化后的值，二分

Unique() 作用是将不重复的数字放到前面，将重复的数字放在后面，然后返回第一个重复数字的位置

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素

int find(int x) { // 找到第一个大于等于x的位置
    int l = 0, r = alls.size() - 1;
    while(l < r) {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; //加不加1都行，+1的话就是映射到1， 2， 3
}

整个的值域跨度很大，但是值的存在很稀疏

相当于压缩稀疏矩阵

映射到从1开始的自然数

特指整数的离散化

值域的范围比较大，但是个数比较少

比如值域0-10^{9,但是个数只有10}5

离散化的过程：

a[]: 1, 3, 100, 1000, 50000000

i: 0 1 2 3 4

关键点：

a中可能有重复元素，需要去重
如何算出a中每一个值离散后的结果，a是有序的所以使用二分来找

unique将数组中所有的元素去重，然后返回重复第一位的下标

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1; // +1从1开始映射，也可以不加，就是从0开始映射
    }
    return r + 1; // 映射到1, 2, ...n

就是将所有的数映射成下标

802. 区间和¶

值域跨度很大，但是很稀疏

把用到过的下标拿过来进行排序

#include <iostream>
#include <vector> // C++中用vector来做离散化
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

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

vector<int> alls;
vector<PII> add, query;

int find (int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 因为要使用到前缀和所以需要从1开始
}

int main () {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    } 

    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);

    }
    // alls里面存了所有可能涉及到的下标，更改过的数字下标、以及区间的数字下标
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 处理插入
    for (auto item : add) {
        int x = find(item.first);
        a[x] += item.second;
    }

    // 预处理前缀和
    for (int i = 0; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

    // 处理询问
    for (auto item : query) {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

实现unique算法¶

他是第一个
a[i] != a[i - 1]

vector<int>::iterator unique(vector<int> &a) {
    int j = 0;
    for (int i = 0; i < a.size(); ++i) {
        if (!i || a[i] != a[i - 1])//如果是第一个元素或者该元素不等于前一个元素，即不重复元素，我们就把它存到数组前j个元素中
            a[j++] = a[i];//每存在一个不同元素，j++
    }
    return a.begin() + j;//返回的是前j个不重复元素的下标
}

区间合并¶

将所有存在交集的区间合并

python在很多情况下并不比C++慢，因为加了O2优化，运行时间在很多情况下和C++差不多的

给我们很多很多的区间，如果两个区间有交集的话，就把这两个区间合并

快速地将n个交集有区间的合并

规定：两个区间只有端点相交的话，也算有交集

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

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

803. 区间合并¶

这道题实际上是贪心算法

按所有区间的左端点进行排序
扫描整个区间，过程当中将所有可能有交集的区间合并

start st end ed

按照左端点从小到大的情况进行扫描，后一个区间的左端点一定在当前区间左端点的后面

在内部、有交集、没有交集

这是一道模拟+贪心

也比较像双指针算法

跟区间相关的题目很多，大部分都是贪心

pair排序在c++里面会优先以左端点进行排序

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

using namespace std;

typedef pair<int, int> PII;

vector<PII> segs;

int n;

void merge(vector<PII> &segs) {
    vector<PII> res;
    sort(segs.begin(), segs.end());
    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 () {
    cin >> n; 

    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}

第一讲 基础算法¶

排序¶