Codeforces Round ＃809 (Div. 2)（6/6）（Kruskal重构树）

Problem - A - Codeforces

模拟

AC代码：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
char s[100];
void Solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= m; i++) {
        s[i] = 'B';
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > m + 1 - a[i]) {
            if (s[m + 1 - a[i]] != 'A') {
                s[m + 1 - a[i]] = 'A';
            }
            else {
                s[a[i]] = 'A';
            }
        }
        else {
            if (s[a[i]] != 'A') {
                s[a[i]] = 'A';
            }
            else {
                s[m + 1 - a[i]] = 'A';
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        cout << s[i];
    }
    cout << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        Solve();
    }

    return 0;
}

Problem - B - Codeforces

找规律，判奇偶

AC代码：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

void Solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);//ji
    vector<int> b(n + 1);//ou
    vector<int> c(n + 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (a[x] == 0 && b[x] == 0) {
            if (i & 1) {
                a[x]++;
            }
            else {
                b[x]++;
            }
        }
        else {
            if (i & 1 && !(a[x] & 1)) {
                a[x]++;
            }
            else if (!(i & 1) && a[x] & 1) {
                a[x]++;
            }
            if (i & 1 && b[x] & 1) {
                b[x]++;
            }
            else if (!(i & 1) && !(b[x] & 1)) {
                b[x]++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << max(a[i], b[i]) << " \n"[i == n];
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        Solve();
    }

    return 0;
}

Problem - C - Codeforces

模拟，分奇偶

AC代码：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

void Solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    LL sum = 0, ans = 0x3f3f3f3f;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n - 1; i += 2) {
        if (a[i - 1] >= a[i] || a[i + 1] >= a[i]) {
            sum += max({a[i - 1] + 1, a[i], a[i + 1] + 1}) - a[i];
        }
    }
    ans = sum;
    if (n % 2 == 0) {
        for (int i = n - 2; i > 0; i--) {
            if (i % 2 == 0) {
                sum += max({a[i - 1] + 1, a[i], a[i + 1] + 1}) - a[i];
            }
            else {
                sum -= max({a[i - 1] + 1, a[i], a[i + 1] + 1}) - a[i];
            }
            ans = min(ans, sum);
        }
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
         Solve();
    }

    return 0;
}

Problem - D1 - Codeforces

暴力，数学，模拟

AC代码：

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;

void Solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep (i, 0, n) {
        cin >> a[i];
    }
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= a[0]; i++) {
        int maxx = i;
        rep (j, 0, n) {
            int p;
            if (a[j] / i == 0) {
                p = k;
            }
            else {
                p = min({k, a[j] / i});
            }
            maxx = max({maxx, a[j] / p});
        }
        ans = min({ans, maxx - i});
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    rep (i, 0, T) {
        Solve();
    }

    return 0;
}

Problem - D2 - Codeforces

数学，贪心

值得细细思考

AC代码：

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;
int a[100010], b[100010];
void Solve() {
    int n, k;
    cin >> n >> k;
    rep (i, 0, n) {
        cin >> a[i];
    }
    memset(b, 0, sizeof(b));
    int val = 1e9 + 7;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= k && j <= a[i]; j = a[i] / (a[i] / j) + 1) {
            int val2 = a[i] / j;
            b[val2 + 1] = max(b[val2 + 1], val);
            val = val2;
        }
        b[0] = max(b[0], val);
    }
    int ans = 1e9 + 7, maxx = -1;
    for (int i = 0; i <= a[0]; i++) {
        maxx = max(maxx, b[i]);
        ans = min(ans, maxx - i);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    rep (i, 0, T) {
        Solve();
    }

    return 0;
}

Problem - E - Codeforces

Kruskal重构树+树剖+LCA+ST表

有时间学一下Kruskal重构树

AC代码：

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;
vector<int> G[400010];
int n, m, q, tot;
int f[400010], son[400010], dep[400010], siz[400010], top[400010], fa[400010], w[400010], st[400010][22], lg[400010];
void init1() {
    for (int i = 2; i <= 400005; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
}
void init2() {
    for (int i = 1; i <= tot; i++) {
        G[i].clear();
        fa[i] = w[i] = f[i] = son[i] = top[i] = siz[i] = 0;
    }
}
void dfs1(int u, int father) {
    f[u] = father;
    dep[u] = dep[father] + 1;
    siz[u] = 1;
    for (auto it : G[u]) {
        if (it == father) {
            continue;
        }
        dfs1(it, u);
        siz[u] += siz[it];
        if (siz[son[u]] < siz[it]) {
            son[u] = it;
        }
    }
}
void dfs2(int u, int t) {
    top[u] = t;
    if (!son[u]) {
        return;
    }
    dfs2(son[u], t);
    for (auto it : G[u]) {
        if (it == f[u] || it == son[u]) {
            continue;
        }
        dfs2(it, it);
    }
}
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) {
            swap(u, v);
        }
        u = f[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}
int getfa(int x) {
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
void build() {
    for (int i = 1; i <= tot; i++) {
        st[i][0] = i;
    }
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j + (1 << i) - 1 <= tot; j++) {
            st[j][i] = lca(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
        }
    }
}

int query(int l, int r) {
    int x = lg[r - l + 1];
    return w[lca(st[l][x], st[r - (1 << x) + 1][x])];
}
void Solve() {
    cin >> n >> m >> q;
    iota(fa, fa + 2 * n + 2, 0);
    tot = n;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        int uu = getfa(u), vv = getfa(v);
        if (uu == vv) {
            continue;
        }
        w[++tot] = i;
        G[tot].push_back(uu);
        G[uu].push_back(tot);
        G[vv].push_back(tot);
        G[tot].push_back(vv);
        fa[uu] = tot;
        fa[vv] = tot;
    }
    dfs1(tot, 0);
    dfs2(tot, tot);
    build();
    rep (i, 0, q) {
        int l, r;
        cin >> l >> r;
        cout << query(l, r) << ' ';
    }
    cout << '\n';
    init2();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    init1();
    cin >> T;
    rep (i, 0, T) {
        Solve();
    }
    
    return 0;
}