「Summary」半期复习

我本来想躺平的

老老实实复习吧

平衡树

Fhq_Treap

#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;

int n, root, tot, tmp1, tmp2, tmp3;

struct Treap {
    int l, r, key, val, siz;
} s[MAXN];

int newnode(int val) {
    s[++tot].val = val, s[tot].key = rand(), s[tot].siz = 1;
    return tot;
}

void push_up(int p) {
    s[p].siz = s[s[p].l].siz + s[s[p].r].siz + 1;
}

void split(int p, int val, int& x, int& y) {
    if (p == 0) { x = y = 0; return; }
    if (s[p].val <= val) {
        x = p, split(s[p].r, val, s[p].r, y);
    } else {
        y = p, split(s[p].l, val, x, s[p].l);
    }
    push_up(p);
}

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (s[x].key > s[y].key) {
        s[x].r = merge(s[x].r, y);
        push_up(x);
        return x;
    } else {
        s[y].l = merge(x, s[y].l);
        push_up(y);
        return y;
    }
}

void insert(int val) {
    split(root, val, tmp1, tmp2);
    root = merge(merge(tmp1, newnode(val)), tmp2);
}

void remove(int val) {
    split(root, val, tmp1, tmp2);
    split(tmp1, val - 1, tmp1, tmp3);
    tmp3 = merge(s[tmp3].l, s[tmp3].r);
    root = merge(merge(tmp1, tmp3), tmp2);
}

int queryrnk(int val) {
    split(root, val - 1, tmp1, tmp2);
    int res = s[tmp1].siz + 1;
    root = merge(tmp1, tmp2);
    return res;
}

int querykth(int p, int k) {
    while (p) {
        if (s[s[p].l].siz + 1 == k) {
            return s[p].val;
        }
        if (s[s[p].l].siz >= k) {
            p = s[p].l; continue;
        }
        k -= s[s[p].l].siz + 1, p = s[p].r;
    }
}

int querypre(int val) {
    split(root, val - 1, tmp1, tmp2);
    int res = querykth(tmp1, s[tmp1].siz);
    root = merge(tmp1, tmp2);
    return res;
}

int querynxt(int val) {
    split(root, val, tmp1, tmp2);
    int res = querykth(tmp2, 1);
    root = merge(tmp1, tmp2);
    return res;
}

int main() {
    // freopen("D:\\Math\\tmp.in", "r", stdin);
    srand(time(0));
    scanf("%d", &n);
    while (n--) {
        int opt, val; scanf("%d %d", &opt, &val);
        if (opt == 1) {
            insert(val);
        } else if (opt == 2) {
            remove(val);
        } else if (opt == 3) {
            printf("%d\n", queryrnk(val));
        } else if (opt == 4) {
            printf("%d\n", querykth(root, val));
        } else if (opt == 5) {
            printf("%d\n", querypre(val));
        } else {
            printf("%d\n", querynxt(val));
        }
    }
    return 0;
}

高斯消元

核心思想

忘了

• step1
  依次扫描当前列的每一行，找到主元(当前列系数最大的)
• step2
  将找到的主元所在的行和当前行交换。
  开始消元，即，从后往前扫后面的每一行，用对应变元的系数去除主元，最后把主元的系数化为一，再去对后面的每一位依次做减法消元。

估计时没说清楚的，但是我自己懂了。。。

最后有个回带的过程，其实整体方法和手算没什么区别。

如果有多解，一定有某个元的系数是$0$.
在代码里体现就是消元的操作没有做够$n$次。

时间复杂度$n^3$.

运用范围

当遇到了概率期望题目的方程式会产生含有 当前$dp$值的转移方程时，形如
$\mathrm{dp_i} = a\times \mathrm{dp_i} + \dots$
并且每个状态前的系数可以确定
这时可以预处理出每个状态前的系数。
然后代入用高斯消元求解就行了。

Code

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e2 + 5;
const double EPS = 1e-18;

int n;
double a[MAXN][MAXN];

void Gauss() {
    int r, c;
    for (c = 1, r = 1; c <= n; c++) {
        int maxl = r;
        for (int i = r; i <= n; i++) if (fabs(a[i][c]) > fabs(a[maxl][c])) {
            maxl = i;
        }
        if (fabs(a[maxl][c]) < EPS) continue;
        for (int i = c; i <= n + 1; i++) swap(a[r][i], a[maxl][i]);
        for (int i = n + 1; i >= c; i--) a[r][i] /= a[r][c];
        for (int i = r; i <= n; i++) {
            for (int j = c; j <= n + 1; j++) {
                a[i][j] -= a[r][j] * a[i][c];
            }
        }
        r++;
    }
    if (r <= n) {
        // 因为 r 是从 1 开始，所以如果全部消完了， r 的终值应该是 n + 1
        printf("No Solution\n");
        exit(0);
    }
    for (int i = n; i >= 1; i--) {
        for (int j = i + 1; j <= n; j++) {
            a[i][n + 1] -= a[j][n + 1] * a[i][j];
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 1; j++) {
            scanf("%lf", &a[i][j]);
        }
    }
    Gauss();
    for (int i = 1; i <= n; i++) {
        printf("%.2lf\n", a[i][n + 1]);
    }
    return 0;
}