【XJTU 2020暑期集训】Day12 - 2019 杭电多校训练第3场

A - Azshara's deep sea

B - Blow up the city

DAG上的支配树板题。建立超级点 S,将所有指挥城市向 S 连一条边,则原题转化成了:从 S 出发,有多少个点为到达 ab 的必经点(除 S 之外)。以 S 为根并根据反向图建立支配树,对于询问 a,b,答案即为 \mathrm{dep}[a]+\mathrm{dep}[b]-\mathrm{dep}[\mathrm{lca}(a,b)]。总复杂度 O(n\log n)

C - Yukikaze and Demons

D - Distribution of books

E - Easy Math Problem

F - Fansblog

签到题。首先由于素数密度为 \frac{1}{\log n},所以暴力找小于 p 的第一个素数 q,复杂度 O(\log n\cdot\sqrt{n})。然后由威尔逊定理(当且仅当 p 为素数时,有 (p-1)!\equiv -1\pmod{p}),可得答案为 (p-q-1)!^{-1},由于差值为 \log n 级别,暴力计算即可。

G - Find the answer

对于前 i 个元素,显然要选最大的若干个置0,所以离散化后建权值线段树,同时维护 \mathrm{sum}\mathrm{cnt},在线段树上二分即可。

H - Game

I - K Subsequence

J - Sindar's Art Exhibition

K - Squrirrel

Code

A - Azshara's deep sea


B - Blow up the city

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define MAX_N 100005
#define MAX_L 25

using namespace std;

int T, n, m, Q;
int deg[MAX_N];
int dep[MAX_N];
int par[MAX_N][MAX_L];
vector<int> e[MAX_N];
vector<int> re[MAX_N];

void ins(int x, int p) {
    par[x][0] = p, dep[x] = dep[p] + 1;
    for (int i = 1; i < MAX_L; i++) {
        par[x][i] = par[par[x][i - 1]][i - 1];
    }
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) {
        swap(a, b);
    }
    for (int d = dep[a] - dep[b], i = 0; d; d >>= 1, i++) {
        if (d & 1) {
            a = par[a][i];
        }
    }
    if (a == b) {
        return a;
    }
    for (int i = MAX_L - 1; i >= 0; i--) {
        if (par[a][i] != par[b][i]) {
            a = par[a][i];
            b = par[b][i];
        }
    }
    return par[a][0];
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i <= n + 1; i++) {
            deg[i] = dep[i] = 0;
            e[i].clear(), re[i].clear();
            for (int j = 0; j < MAX_L; j++) {
                par[i][j] = 0;
            }
        }
        int x, y;
        for (int i = 1; i <= m; i++) {
            scanf("%d%d", &x, &y);
            e[x].push_back(y);
            re[y].push_back(x);
            deg[x]++;
        }
        for (int i = 1; i <= n; i++) {
            if (!e[i].size()) {
                e[i].push_back(n + 1);
                re[n + 1].push_back(i);
                deg[i]++;
            }
        }
        queue<int> q;
        q.push(n + 1);
        while (!q.empty()) {
            x = q.front(), q.pop();
            if (e[x].size()) {
                int anc = e[x][0];
                for (int i = 1; i < e[x].size(); i++) {
                    anc = lca(anc, e[x][i]);
                }
                ins(x, anc);
            }
            for (int i = 0; i < re[x].size(); i++) {
                int t = re[x][i];
                deg[t]--;
                if (!deg[t]) {
                    q.push(t);
                }
            }
        }
        scanf("%d", &Q);
        int a, b;
        while (Q--) {
            scanf("%d%d", &a, &b);
            int t = lca(a, b);
            printf("%d\n", dep[a] + dep[b] - dep[t]);
        }
    }
}

C - Yukikaze and Demons


D - Distribution of books


E - Easy Math Problem


F - Fansblog

#include <iostream>
#include <stdio.h>
#include <string.h>
#define int __int128_t
#define LL long long

using namespace std;

int T, p;

bool check(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (!(x % i)) {
            return false;
        }
    }
    return true;
}

int fpow(int x, int k, int p) {
    int ans = 1;
    while (k) {
        if (k & 1) {
            ans = ans * x % p;
        }
        x = x * x % p, k >>= 1;
    }
    return ans;
}

LL read() {
    LL x;
    scanf("%lld", &x);
    return x;
}

signed main() {
    T = read();
    while (T--) {
        p = read();
        int q = p - 2;
        while (!check(q)) {
            q -= 2;
        }
        int ans = 1;
        for (int i = 2; i <= p - q - 1; i++) {
            ans = ans * i % p;
        }
        printf("%lld\n", (long long)fpow(ans, p - 2, p));
    }
}

G - Find the answer

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#define MAX_N 200005
#define MAX_T 1600005
#define int long long

using namespace std;

int T, n, m, rt, tot;
int a[MAX_N];
int L[MAX_T];
int R[MAX_T];
int sum[MAX_T];
int cnt[MAX_T];
vector<int> v;

int getid(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

void pushup(int k) {
    sum[k] = sum[L[k]] + sum[R[k]];
    cnt[k] = cnt[L[k]] + cnt[R[k]];
}

void upd(int pos, int &k, int l, int r, int x) {
    if (!k) {
        k = ++tot;
    }
    if (l == r) {
        sum[k] += x, cnt[k]++;
        return;
    }
    int md = (l + r) >> 1;
    if (pos <= md) {
        upd(pos, L[k], l, md, x);
    } else {
        upd(pos, R[k], md + 1, r, x);
    }
    pushup(k);
}

int ask(int k, int l, int r, int s) {
    if (l == r) {
        return l;
    }
    int md = (l + r) >> 1;
    int ls = sum[L[k]];
    if (ls >= s) {
        return ask(L[k], l, md, s);
    } else {
        return ask(R[k], md + 1, r, s - ls);
    }
}

int getcnt(int a, int b, int k, int l, int r) {
    if (a <= l && r <= b) {
        return cnt[k];
    }
    int md = (l + r) >> 1, ans = 0;
    if (a <= md) {
        ans += getcnt(a, b, L[k], l, md);
    }
    if (b > md) {
        ans += getcnt(a, b, R[k], md + 1, r);
    }
    return ans;
}

int getsum(int a, int b, int k, int l, int r) {
    if (a <= l && r <= b) {
        return sum[k];
    }
    int md = (l + r) >> 1, ans = 0;
    if (a <= md) {
        ans += getsum(a, b, L[k], l, md);
    }
    if (b > md) {
        ans += getsum(a, b, R[k], md + 1, r);
    }
    return ans;
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld", &n, &m);
        v.clear();
        for (int i = 1; i <= n; i++) {
            scanf("%lld", a + i);
            v.push_back(a[i]);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        int N = v.size();
        for (int i = 0; i <= tot; i++) {
            L[i] = R[i] = sum[i] = cnt[i] = 0;
        }
        tot = rt = 0;
        map<int, int> mp;
        for (int i = 1; i <= n; i++) {
            int x = ask(rt, 1, N, m - a[i]);
            int s = getsum(1, x, rt, 1, N);
            int c = getcnt(1, x, rt, 1, N);
            int ts = getsum(x, x, rt, 1, N);
            int tc = getcnt(x, x, rt, 1, N);
            s -= ts, c -= tc;
            int dc, dt = m - a[i] - s;
            if (dt > 0) {
                dc = min(tc, dt / v[x - 1]);
                c += dc, s += dc * v[x - 1];
            }
            auto it = mp.upper_bound(v[x - 1]);
            if (it != mp.end()) {
                dt = m - a[i] - s;
                if (dt > 0) {
                    dc = min(it->second, dt / it->first);
                    c += dc;
                }
            }
            printf("%lld ", i - 1 - c);
            upd(getid(a[i]), rt, 1, N, a[i]);
        }
        printf("\n");
    }
}

H - Game


I - K Subsequence


J - Sindar's Art Exhibition


K - Squrirrel


点赞
  1. cc说道:
    Google Chrome Windows 10

    你好,请问一下你有2019-2020 XX Opencup GP of Tokyo 这个练习题的答案么?

发表评论

电子邮件地址不会被公开。必填项已用 * 标注