Codeforces Round 872 (Div. 2)【A - D2】

概率期望还是要多练习啊……

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

A. LuoTianyi and the Palindrome String

题解

数据范围较小，可以直接模拟。

事实上如果不全为一个字符的话，只需操作一次。

代码

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

void solve() {
    string s;
    cin >> s;

    while (not s.empty() and s == string(s.rbegin(), s.rend())) {
        s.pop_back();
    }

    cout << (s.empty() ? -1 : (int)s.size()) << "\n";
}

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

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

B. LuoTianyi and the Table

题解

主要关注左上角三个元素即可，有最大值、次大值、最小值和最小值、次小值、最大值两种情况。

代码

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

void solve() {
    int n, m;
    cin >> n >> m;

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

    if (n >= m) {
        swap(n, m);
    }

    auto cal = [&](int x, int y, int z) {
        return n * (m - 1) * abs(x - z) + (n - 1) * abs(y - z);
    };

    cout << max(cal(b[n * m - 1], b[n * m - 2], b[0]), cal(b[0], b[1], b[n * m - 1])) << "\n";
}

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

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

C. LuoTianyi and the Show

题解

第一步如果为 op 1 ，那么之后不会再有 op 2 ，此时答案为 op 1 的个数与已有值的个数之和；

第一步如果为 op 2 ，那么之后不会再有 op 1 ，此时答案为 op 2 的个数与已有值的个数之和；

第一步如果为 op 3 ，此时最优解是选取一个尽可能靠中间的数然后向两边扩展，枚举这个数即可。

代码

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

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> vis(m + 2, 1);
    vis[0] = vis[m + 1] = 0;
    set<int> st;
    int one = 0, two = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > 0) {
            vis[x] = 0;
            st.insert(x);
        } else {
            (x == -1 ? one : two) += 1;
        }
    }

    auto pre(vis), suf(vis);
    for (int i = 1; i <= m; i++) {
        pre[i] += pre[i - 1];
    }
    for (int i = m; i >= 0; i--) {
        suf[i] += suf[i + 1];
    }

    int ans = 0;
    for (int i = 1; i <= m; i++) {
        if (vis[i] == 1) {
            continue;
        }
        ans = max(ans, min(one, pre[i - 1]) + (i - 1 - pre[i - 1]) + 1 + (m - i - suf[i + 1]) + min(two, suf[i + 1]));
    }
    cout << min(m, max((int)st.size() + max(one, two), ans)) << "\n";
}

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

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

D2. LuoTianyi and the Floating Islands (Hard Version)

题解

如果 $k$ 为奇数，显然只有 $1$ 个结点是好结点。

证明：如果有两个结点是好结点，那么一定存在一个结点的一侧至少有 $\lceil \frac{k}{2} \rceil$ 个人，此时另一个结点向这一侧移动花费一定会减少，所以可以移动的这个结点不是好结点。

如果 $k$ 为偶数，那么好结点一定是一条链，这条链上的每个边左右各有 $\frac{k}{2}$ 个结点，这样移动时花费才不会改变，计算每条边在链中概率的期望，好结点个数的期望 = 边数的期望 + 1（点数 = 边数 + 1）。

代码

#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; }
};

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);

    int n, k;
    cin >> n >> k;

    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);
    }

    Combination C(2e5 + 10);

    if (k & 1) {
        cout << 1 << "\n";
        return 0;
    }

    Z ans = 1;
    vector<int> sz(n);
    function<void(int, int)> dfs = [&](int u, int p) {
        sz[u] = 1;
        for (auto v : G[u]) {
            if (v == p) {
                continue;
            }
            dfs(v, u);
            sz[u] += sz[v];
            ans += C.C(sz[v], k / 2) * C.C(n - sz[v], k / 2) / C.C(n, k);
        }
    };
    dfs(0, -1);
    cout << ans.val() << "\n";

    return 0;
}