题解 | #牛客周赛 Round 136 #

A

$O(1)$ 。

#include "bits/stdc++.h"
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b, c;
    cin >> a >> b >> c;
    cout << c << ' ' << a << ' ' << b << '\n';
    return 0;
}

B

$O(t)$ 。

#include "bits/stdc++.h"
using namespace std;
void solve() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << "a\n";
    } else {
        cout << "No\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

使用组合数。

$O(|s|)$ 。

#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
constexpr int P = 998244353;
i64 *fac, *ifac;
i64 power(i64 a, i64 b, int p = P) {
    i64 res = 1;
    for (; b > 0; b >>= 1, a = a * a % p) {
        if (b & 1) {
            res = res * a % p;
        }
    }
    return res;
}
i64 inv(i64 x) { 
    return power(x, P - 2, P); 
}
void init(int N) {
    fac = new i64[N + 1];
    ifac = new i64[N + 1];
    fac[0] = 1;
    for (int i = 1; i <= N; i++) {
        fac[i] = fac[i - 1] * i % P;
    }
    ifac[N] = inv(fac[N]);
    for (int i = N - 1; i >= 0; i--) {
        ifac[i] = ifac[i + 1] * (i + 1) % P;
    }
}
i64 C(int n, int m) {
    if (m < 0 || m > n || n < 0) {
        return 0;
    }
    return fac[n] * ifac[m] % P * ifac[n - m] % P;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init(2E5);
    int n;
    string s;
    cin >> n >> s;
    int cntj = count(s.begin(), s.end(), 'j'), cnto = count(s.begin(), s.end(), 'o'), cnt = n - cntj - cnto;
    cout << C((n + 1) / 2, cntj) * fac[cntj] % P * C(n / 2, cnto) % P * fac[cnto] % P * fac[cnt] % P << '\n';
    return 0;
}

D

排序后从大到小删或者从小到大删。

$O(n)$ 。

#include "bits/stdc++.h"
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int l = 0, r = 0;
    for (auto x : a) {
        if (x < a[(n - 1) / 2]) l++;
        else if (x > a[(n - 1) / 2]) r++;
    }
    int ans = min(n - 2 * r + 1, n - 2 * l);
    if (ans < n) {
        cout << ans << '\n';
    } else {
        cout << "-1\n";
    }
    return 0;
}

E

$dp_u = 1$ ，表示红方站在 $u$ 时，红方必胜。 $u$ 是叶子时， $dp_u = 1$ ； $u$ 不是根时，若它的儿子中有至少 $2$ 个必胜点，则 $dp_u = 1$ ； $u$ 是根时，若它的儿子中有至少 $1$ 个必胜点，则 $dp_u = 1$ 。

$O(\sum n)$ 。

#include "bits/stdc++.h"
using namespace std;
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> dp(n);
    auto dfs = [&](auto &&self, int x, int p) -> void {
        int ok = 1, cnt = 0;
        for (auto y : adj[x]) {
            if (y != p) {
                ok = 0
                self(self, y, x);
                cnt += dp[y];
            }       
        }
        if (ok) {
            dp[x] = 1;
        } else if (x == 0) {
            dp[x] = (cnt > 0);
        } else {
            dp[x] = (cnt > 1);
        }
    };
    dfs(dfs, 0, -1);
    cout << (dp[0] ? "red" : "purple") << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

$k < n-1$ ：直接构造一条长度为 $k$ 的链，再把剩下的点放远处当孤立点。

$k \ge n-1$ ：设有 $h$ 行，第 $i$ 行长度为 $len_i$ ，并且 $len_0 \ge len_1 \ge ...$ ，所有行左对齐。每行内部边数是 $len_i-1$ ，第 $i$ 行和第 $i+1$ 行之间的竖边数是 $len_{i+1}$ 。总边数为： $\sum (len_i-1) + \sum len_{i+1} = 2n - len_0 - h$ ，只要让 $len_0 + h = 2n-k$ ，就能得到恰好 $k$ 条边。令 $s = 2n-k$ ，取 $h = \frac{s}{2}$ ， $len_0 = s-h$ 。如果 $k$ 超过 $\max = 2n - \min\limits_{h=1}^{n}\left(h+\left\lceil \frac{n}{h}\right\rceil\right)$ ，直接输出 No。

#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    int msum = INT_MAX;
    for (int h = 1; h <= n; h++) {
        int a = (n + h - 1) / h;
        msum = min(msum, a + h);
    }
    int mxeges = 2 * n - msum;
    if (k > mxeges) {
        cout << "No\n";
        return 0;
    }
    vector<pair<int, int>> pts;
    if (k < n - 1) {
        for (int i = 0; i <= k; i++) {
            pts.push_back({0, i});
        }
        for (int i = 0; (int)pts.size() < n; i++) {
            pts.push_back({100000000 + 2 * i, 100000000});
        }
    } else {
        int s = 2 * n - k;
        int h = s / 2;
        int a = s - h;
        vector<int> len(h, 1);
        i64 rem = n - h;
        for (int i = 0; i < h; i++) {
            int add = min<i64>(rem, a - 1);
            len[i] += add;
            rem -= add;
        }
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < len[y]; x++) {
                pts.push_back({x, y});
            }
        }
    }
    cout << "Yes\n";
    for (auto p : pts) {
        cout << p.first << ' ' << p.second << '\n';
    }
    return 0;
}