AcWing基础算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int q[N];
int quick_select(int l, int r, int k) { // 在[l, r]查找第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_select(l, j, k);
    return quick_select(j + 1, r, k - sl);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int q[N], t[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]) t[k++] = q[i++];
        else t[k++] = q[j++];  // res += mid - i + 1; res为逆序对的数量
    }
    while (i <= mid) t[k++] = q[i++];
    while (j <= r) t[k++] = q[j++];
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = t[j];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

bool check(int x) {};

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

const double eps = 1e-6;

bool check(double x) {};

double bsearch_3(double l, double r) {
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

vint add(vint &a, vint &b) {
    vint c;
    for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.pb(t % 10);
        t /= 10;
    }
    return c;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

bool isgreater(vint &a, vint &b) {
    if (a.size() != b.size()) return a.size() > b.size();
    return vint(a.rbegin(), a.rend()) > vint(b.rbegin(), b.rend());
}
// 使用条件：a > b
vint sub(vint &a, vint &b)  {
    vint c;
    for (int i = 0, t = 0; i < a.size(); i++) {
        t = a[i] - t;
        if (i < b.size()) t -= b[i];
        c.pb((t + 10) % 10);
        if (t >= 0) t = 0;
        else t = 1;
    }
    while (c.back() == 0 && c.size() > 1) c.pop_back(); 
    return c;
}

1
2
3
4
5
6
7
8
9

vint mul(vint &a, int b) {
    vint c;
    for (int i = 0, t = 0; i < a.size() || t; i++) {
        if (i < a.size()) t += a[i] * b;
        c.pb(t % 10);
        t /= 10;
    }
    return c;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

vint div(vint a, int b, int &r) {
    vint c;
    r = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        r = r * 10 + a[i];
        c.pb(r / b);
        r %= b;
    }
    reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

vector<int> alls;
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

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 l + 1;   // 映射到1.2.3...
}