Codeforces Round #845 (Div. 2) and ByteRace 2023【A - E】

C 题想用区间最值结果没有板子，其实在加减时直接判断就可以。

比赛链接：https://codeforces.com/contest/1777

A. Everybody Likes Good Arrays!

题解

每个连续奇偶性相同的段都只留下一个数。

代码

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

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

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        int ans = 0;
        for (int i = 0; i < n; ) {
            int j = i + 1;
            while (j < n and a[j] % 2 == a[i] % 2) {
                j++;
            }
            ans += j - i - 1;
            i = j;
        }
        cout << ans << "\n";
    }

    return 0;
}

B. Emordnilap

题解

对于某一数对 $(i, j)$ ，设 $i < j$ ，相对排列有两种方式：

• $i$ 在前，相对位置为： $i, j, j, i$ ，有 $2$ 个逆序对
• $j$ 在前，相对位置为： $j, i, i, j$ ，有 $2$ 个逆序对

所以共有 $n! \cdot C_n^2 \cdot 2$ 个逆序对。

代码

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

constexpr int MOD = 1e9 + 7;
constexpr int N = 1e5 + 10;

int norm(int x) { if (x < 0) { x += MOD; } if (x >= MOD) { x -= MOD; } return x; }
template<class T> T binpow(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }

struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const { return x; }
    Z operator-() const { return Z(norm(MOD - x)); }
    Z inv() const { assert(x != 0); return binpow(*this, MOD - 2); }
    Z &operator*=(const Z &rhs) { x = 1LL * x * rhs.x % MOD; return *this; }
    Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; }
    Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
    friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; }
    friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; }
    friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; }
    friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; }
};

struct Combination {
    vector<Z> fac, inv;

    Combination(int n) : fac(n), inv(n) {
        fac[0] = 1;
        for (int i = 1; i < n; i++) fac[i] = fac[i - 1] * i;
        inv[n - 1] = fac[n - 1].inv();
        for (int i = n - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1);
    }

    Z C(int n, int m){
        if(m < 0 or m > n) return 0;
        return fac[n] * inv[m] * inv[n - m];
    }

    Z A(int n, int m){
        if(m < 0 or m > n) return 0;
        return fac[n] * inv[n - m];
    }
};

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

    Combination C(N);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        cout << (C.fac[n] * C.C(n, 2) * 2).val() << "\n";
    }

    return 0;
}

C. Quiz Master

题解

答案只与最值差有关，排序后双指针模拟。

代码

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

constexpr int N = 1e5 + 10;

vector d(N, vector<int>());

void Init() {
    for (int i = 1; i < N; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                d[i].push_back(j);
                if (j != i / j) {
                    d[i].push_back(i / j);
                }
            }
        }
    }
}

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

    Init();

    int t;
    cin >> t;

    while (t--) {
        int n, m;
        cin >> n >> m;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());

        vector<int> cnt(m + 1);
        int vis = 0;
        
        auto op = [&](int x, bool add) {
            for (auto i : d[x]) {
                if (i > m) {
                    continue;
                }
                if (cnt[i] == 0) {
                    vis++;
                }
                cnt[i] += (add ? 1 : -1);
                if (cnt[i] == 0) {
                    vis--;
                }
            }
        };

        int ans = INT_MAX;
        for (int l = 0, r = 0; l < n; l++) {
            while (r < n and vis != m) {
                op(a[r], true);
                r++;
            }
            if (vis == m) {
                ans = min(ans, a[r - 1] - a[l]);
            }
            op(a[l], false);
        }
        cout << (ans == INT_MAX ? -1 : ans) << "\n";
    }

    return 0;
}

D. Score of a Tree

题解

对于某一结点 $u$ ：

• $u$ 在第 $i$ 秒的值是以 $u$ 为根节点的子树内与 $u$ 距离为 $i$ 的所有结点初始值的异或
• 设子树内最大深度为 $d_{max}$ ，则在 $d_{max} + 1$ 秒后结点 $u$ 的值为 $0$
• 在 $0 \sim d_{max}$ 秒，结点 $u$ 值的期望都为 $\frac{1}{2}$ （ $k$ 个布尔值选奇数项赋 $1$ ，有一半情况）

共有 $2^n$ 种情况，每个结点值的期望为 $\frac{(d_{max} + 1)}{2}$ ，答案为 $2^{n - 1} \cdot \sum \limits _{i = 1} ^{n} (d_{max} + 1)$ ，其中 $d_{max}$ 可以在 DFS 中线性计算。

代码

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

constexpr int MOD = 1e9 + 7;

int norm(int x) { if (x < 0) { x += MOD; } if (x >= MOD) { x -= MOD; } return x; }
template<class T> T binpow(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }

struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const { return x; }
    Z operator-() const { return Z(norm(MOD - x)); }
    Z inv() const { assert(x != 0); return binpow(*this, MOD - 2); }
    Z &operator*=(const Z &rhs) { x = 1LL * x * rhs.x % MOD; return *this; }
    Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; }
    Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
    friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; }
    friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; }
    friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; }
    friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; }
};

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

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<vector<int>> G(n);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            G[u].push_back(v);
            G[v].push_back(u);
        }

        vector<int> dp(n);
        function<void(int, int)> dfs = [&](int u, int p) {
            dp[u] = 1;
            for (auto v : G[u]) {
                if (v != p) {
                    dfs(v, u);
                    dp[u] = max(dp[u], dp[v] + 1);
                }
            }
        };
        dfs(0, -1);

        cout << (binpow(Z(2), n - 1) * accumulate(dp.begin(), dp.end(), Z(0))).val() << "\n";
    }

    return 0;
}

E. Edge Reverse

题解

二分边权，小于等于 $mid$ 的边建双向边，然后用强连通分量中的 Tarjan 或 Kosaraju 算法找出发点。

代码

Kosaraju 版：

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

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

    int t;
    cin >> t;

    while (t--) {
        int n, m;
        cin >> n >> m;

        vector<int> u(m), v(m), w(m);
        for (int i = 0; i < m; i++) {
            cin >> u[i] >> v[i] >> w[i];
            --u[i], --v[i];
        }

        vector<int> p(m);
        iota(p.begin(), p.end(), 0);
        sort(p.begin(), p.end(), [&](int x, int y) {
            return w[x] < w[y];
        });

        int l = 0, r = 1e9 + 10;
        auto ok = [&](int mid) {
            vector<vector<int>> G(n);
            for (auto i : p) {
                G[u[i]].push_back(v[i]);
                if (w[i] <= mid) {
                    G[v[i]].push_back(u[i]);
                }
            }
            vector<bool> vis(n);
            int root = -1;
            function<void(int)> dfs = [&](int u) { // Kosaraju
                vis[u] = true;
                for (auto v : G[u]) {
                    if (not vis[v]) {
                        dfs(v);
                    }
                }
                root = u;
            };
            for (int i = 0; i < n; i++) {
                if (not vis[i]) {
                    dfs(i);
                }
            }
            vis.assign(n, false);
            dfs(root);
            return all_of(vis.begin(), vis.end(), [](bool x) { return x == true; });
        };
        while (l < r) {
            int mid = (l + r) / 2;
            if (ok(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        cout << (l == 1e9 + 10 ? -1 : l) << "\n";
    }

    return 0;
}

Tarjan 版：

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

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

    int t;
    cin >> t;

    while (t--) {
        int n, m;
        cin >> n >> m;

        vector<int> u(m), v(m), w(m);
        for (int i = 0; i < m; i++) {
            cin >> u[i] >> v[i] >> w[i];
            --u[i], --v[i];
        }

        vector<int> p(m);
        iota(p.begin(), p.end(), 0);
        sort(p.begin(), p.end(), [&](int x, int y) {
            return w[x] < w[y];
        });

        int l = 0, r = 1e9 + 10;
        auto ok = [&](int mid) {
            vector<vector<int>> G(n);
            for (auto i : p) {
                G[u[i]].push_back(v[i]);
                if (w[i] <= mid) {
                    G[v[i]].push_back(u[i]);
                }
            }
            vector<int> low(n), dfn(n), sccno(n);
            int ck = 0, scc_cnt = 0;
            stack<int> stk;
            function<void(int)> tarjan = [&](int u) {
                low[u] = dfn[u] = ++ck;
                stk.push(u);
                for (auto v : G[u]) {
                    if (dfn[v] == 0) {
                        tarjan(v);
                        low[u] = min(low[u], low[v]);
                    } else if (sccno[v] == 0) {
                        low[u] = min(low[u], dfn[v]);
                    }
                }
                if (low[u] == dfn[u]) {
                    scc_cnt++;
                    while (1) {
                        int x = stk.top();
                        stk.pop();
                        sccno[x] = scc_cnt;
                        if (x == u) {
                            break;
                        }
                    }
                }
            };
            for (int i = 0; i < n; i++) {
                if (dfn[i] == 0) {
                    tarjan(i);
                }
            }
            vector<bool> vis(n);
            function<void(int)> dfs = [&](int u) {
                vis[u] = true;
                for (auto v : G[u]) {
                    if (not vis[v]) {
                        dfs(v);
                    }
                }
            };
            for (int i = 0; i < n; i++) {
                if (sccno[i] == scc_cnt) {
                    dfs(i);
                    break;
                }
            }
            return all_of(vis.begin(), vis.end(), [](bool x) { return x == true; });
        };
        while (l < r) {
            int mid = (l + r) / 2;
            if (ok(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        cout << (l == 1e9 + 10 ? -1 : l) << "\n";
    }

    return 0;
}