算法设计基础（七）

ST表就是基于倍增算法打表，在处理一些高级算法比如LCA是非常高效简洁的
BFPRT算法用于解决第 k 大数，当然第 k 大数之后还有比如主席树这样的算法

ST表

const int maxn = 1e5 + 10;
const int _maxn = 1e3;
int n, a[maxn], f[maxn][_maxn];

void ST_prework() {
    _rep(i, 1, n) f[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    _for(j, 1, t) {
        _rep(i, 1, n - (1<<j) + 1) f[i][j] = max(f[i][j-1], f[i + (1<<(j-1))][j-1]);
    }
}

int ST_query(int l, int r) {
    int k = log(r-l+1) / log(2);
    return max(f[l][k], f[r - (1<<k) + 1][k]);
}

BFPRT 算法

BFPRT 算法可以用于解决区间第 k 大数的问题

const int maxn = 1e5 + 10;
int a[maxn], n = 0, K;

inline bool invalid(int L, int R, int K) {
    return n == 0 || K > (R-L+1) || L > R;
}

int BFPRT(int L, int R, int K);
int getPivot(int L, int R) {
    if (R-L+1 <= 5) {
        sort(a+L, a+R+1);
        return (L+R)>>1;
    }

    int p = L-1;
    // move median to the leftmost
    for (int i = L; i + 4 <= R; i += 5) {
        sort(a+i, a+i+5);
        swap(a[++p], a[(i + i+4)>>1]);
    }

    return BFPRT(L, p, ((p-L+1)>>1) + 1);
}
int _part(int L, int R, int pivot) {
    // put a[pivot] -> a[R]
    swap(a[pivot], a[R]);

    int p = L;
    for (int i = L; i < R; i++) if (a[i] < a[R]) {
        swap(a[p++], a[i]);
    }

    swap(a[p], a[R]);
    return p;
}

int BFPRT(int L, int R, int K) {
    if (invalid(L, R, K)) return -1;
    if (L == R) return L;

    // get pivot
    int pivot = getPivot(L, R);
    int p = _part(L, R, pivot);
    int num = p-L+1;

    if (num == K) return p;
    else if (num > K) return BFPRT(L, p-1, K);
    else return BFPRT(p+1, R, K-num);
}

void init() {
    n = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    init();

    // get data
    scanf("%d", &n);
    _for(i, 0, n) scanf("%d", &a[i]);
    scanf("%d", &K);
    printf("Origin array:\n");
    _for(i, 0, n) printf("%d ", a[i]);

    // BFPRT
    int ans = BFPRT(0, n-1, K);
    printf("\n\n%dth number is %d\n", K, a[ans]);

    printf("\nFinal array:\n");
    _for(i, 0, n) printf("%d ", a[i]);
}

程序运行结果

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

8th number is 7

Final array:
4 0 1 3 2 5 6 7 8 9 10 12 13 14 17 15 16 11 18 19 
Process finished with exit code 0

贪心模型：活动选择问题

Acwing111

const int maxn = 50000 + 10;

class A {
public:
    int st, ed, id;
    bool operator< (const A &rhs) const {
        return ed > rhs.ed;
    }
} a[maxn];

inline bool cmp(const A &lhs, const A &rhs) {
    return lhs.st < rhs.st || (lhs.st == rhs.st && lhs.ed < rhs.ed);
}

int n, ans;
unordered_map<int, int> ID;

void init() {
    ID.clear();
    ans = 0;
}

void solve() {
    sort(a, a+n, cmp);
    priority_queue<A> pq;

    for (int i = 0; i < n; i++) {
        const A &x = a[i];

        if (!pq.empty() && x.st > pq.top().ed) {
            ID[x.id] = ID[pq.top().id];
            pq.pop(); pq.push(x);
        }
        else {
            ans++;
            ID[x.id] = ans;
            pq.push(x);
        }
    }

    printf("%d\n", ans);
    for (int i = 0; i < n; i++) printf("%d\n", ID[i]);
}

int main() {
    freopen("input.txt", "r", stdin);
    init();

    // get data
    scanf("%d", &n);
    _for(i, 0, n) {
        scanf("%d%d", &a[i].st, &a[i].ed);
        a[i].id = i;
    }

    solve();
}

高精度

高精度加法

const int BASE = 10;

vector<int> add(const vector<int>& A, const vector<int>& B) {
    if (A.size() < B.size()) return add(B, A);
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size(); i++) {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t%10), t /= 10;
    }
    if (t)  C.push_back(t);

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

高精度减法

vector<int> sub(const vector<int>& A, const 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;
}

高精度乘低精度

主循环用一个变量 $t$ 表示结果，注意以下情况

while(t) C.push_back(t%10), t /= 10;

vector<int> mul(const vector<int>& A, const 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;
    }
    return C;
}

高精度除以低精度

vector<int> div(const vector<int>& A, int b) {
    vector<int> C;
    int 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;
}

高精度乘高精度

vector<int> mul(const vector<int>& A, const vector<int>& B) {
    vector<int> C(A.size()+B.size()+10, 0);
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) C[i+j] += A[i] * B[j];
    }

    for (int i = 0; i < C.size(); i++) {
        if (C[i] >= 10) C[i+1] += C[i] / 10, C[i] %= 10;
    }

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

高精度和高精度的比较

check A < B, return true

bool cmp(const vector<int>& A, const vector<int>& B) {
    // check A <= B
    if (A.size() < B.size()) return true;
    if (A.size() > B.size()) return false;

    if (vector<int>(A.rbegin(), A.rend()) <= vector<int>(B.rbegin(), B.rend())) return true;
    return false;
}

高精度除以高精度

高精度除法重点理解

vector<int> div(vector<int> A, vector<int> B) {
    int dv = A.size() - B.size();
    vector<int> C(dv+1, 0);

    // append suffix zero
    reverse(B.begin(), B.end());
    for (int i = 0; i < dv; i++) B.push_back(0);
    reverse(B.begin(), B.end());

    for (int i = 0; i <= dv; i++) {
        while (!cmp(A, B)) {
            A = sub(A, B);
            C[dv-i]++;
        }
        B.erase(B.begin());
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

邻项交换与贪心选择

本文高精度算法的应用，以贪心算法中的
邻项交换来分析

Acwing114

const int maxn = 1000 + 10;
int n;
class P {
public:
    int M, b;
    P() = default;
    P(int M, int b) : M(M), b(b) {}

    bool operator< (const P &rhs) const {
        return M < rhs.M;
    }
} p[maxn];

void init() {
    //
}

vector<int> mul(const 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;
    }
    return C;
}

vector<int> div(const vector<int> &A, int b) {
    vector<int> C;
    int 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;
}

vector<int> vec_max(const vector<int> &A, const vector<int> &B) {
    if (A.size() > B.size()) return A;
    if (B.size() > A.size()) return B;

    if (vector<int>(A.rbegin(), A.rend()) > vector<int>(B.rbegin(), B.rend())) return A;
    return B;
}

void solve() {
    sort(p+1, p+1+n);

    vector<int> res(1, 1);
    vector<int> ans(1, 0);

    _rep(i, 0, n) {
        if (i) ans = vec_max(ans, div(res, p[i].b));
        res = mul(res, p[i].M / p[i].b);
    }
    reverse(ans.begin(), ans.end());
    for (auto x : ans) printf("%d", x);
    printf("\n");
}

int main() {
    freopen("input.txt", "r", stdin);
    init();

    // get data
    scanf("%d", &n);
    _rep(i, 0, n) {
        int a, b;
        scanf("%d%d", &a, &b);
        p[i] = P(a*b, b);
    }

    // then solve
    solve();
}