2024牛客暑期多校训练营5 题解

B - 珑

Question

你需要用若干个 1×2 或 2×1 的多米诺骨牌覆盖一个 $n \times m$ 的矩形。每个位置必须恰好被覆盖一次，且多米诺骨牌不得超出矩形范围。

此外，可能存在两种类型的约束：

多米诺骨牌的短边不能相邻，即没有两个多米诺骨牌可以共享长度为 1 的边。
多米诺骨牌的长边不能相邻，即没有两个多米诺骨牌可以共享长度为 2 的边（即使它们只共享一条边）。

有 $T$ 个查询，每个查询给出 $n, m, a, b$ ，分别代表矩形的大小以及两种约束是否存在。当 $a$ 为 0 时，第一种约束存在；当 $a$ 为 1 时，第一种约束不存在。当 $b$ 为 0 时，第二种约束存在；当 $b$ 为 1 时，第二种约束不存在。对于每个查询，你需要判断是否有方法可以覆盖整个矩形。

Solution

可以手玩一下，一共是四种情况

显然， $n \times m$ 为奇数的时候，肯定无解

$a = b = 1$

用 $1 \times 2$ 的随便放就好了

$a = 1, b = 0$

也就是长边不能相邻

只有这种情况能实现

$a = 0, b = 1$

也就是断边不能相邻，我们可以组成一个基本单元

于是，我们就组成了一个 $2 \times 3$ 的基本单元，所以偶数边就满足了，奇数边可能模 $3$ 为 $1$ ，或为 $2$ ，我们已经有 $1 \times 2$ 和 $2 \times 2$ 的方法，所以 $a = 0, b = 1$ 的都能放

$a = b = 0$

只有 $1 \times 2$ 能满足

Code

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

void solve() {
    int n, m, a, b; cin >> n >> m >> a >> b; a ^= 1, b ^= 1;
    if ((n == 1 && m == 2) || (n == 2 && m == 1)) {
        cout << "Yes" << '\n';
        return;
    }
    if ((a == 0 && b == 0) || (a == 1 && b == 0)) {
        if ((a == 1 && b == 0) && (n == 1 || m == 1)) {
            cout << "No" << '\n';
            return;
        }
        if (n % 2 == 0 && m % 2 == 0) cout << "Yes" << '\n';
        else if (n % 2 == 1 && m % 2 == 1) cout << "No" << '\n';
        else cout << "Yes" << '\n';
    }
    else if ((a == 1 && b == 1)) {
        if ((n == 1 && m == 2) || (n == 2 && m == 1)) cout << "Yes" << '\n';
        else cout << "No" << '\n';
    }
    else if (a == 0 && b == 1) {
        if ((n == 1 && m % 2 == 0) || (m == 1 && n % 2 == 0)) cout << "Yes" << '\n';
        else cout << "No" << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

H - 入

Question

有一个无向图，其中每个顶点都有唯一的权重 $a_{i}$ 。

最初，一颗棋子被放在一个顶点上。每走一步，棋子都会移动到权重最小的相邻顶点。如果所有相邻顶点的权重都大于当前顶点，则立即停止移动。

您可以为顶点自由分配权重 $a_{i}$ （确保它们都是唯一的），并选择棋子的初始位置。您的目标是使棋子访问的顶点数最大化。

$n \leq 40$

Solution

由于 $n$ 非常小，所以我们考虑暴力 DFS

每次 DFS 到一个点，我们就把这个点从图中删掉（具体做法是用 vis 数组标记），然后继续 DFS，在回溯时，把 vis 标记去掉

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 45;

vector<int> g[MAXN];
int vis[MAXN];

int dfs(int u) {
    vector<int> p;
    for (auto v : g[u]) {
        if (vis[v]) continue;
        vis[v] = u;
        p.push_back(v);
    }
    int res = 1;
    for (auto v : p)
        res = max(res, dfs(v) + 1);
    for (auto v : p)
        if (vis[v] == u) vis[v] = 0;
    return res;
}


int main() {
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        vis[i] = i;
        res = max(res, dfs(i));
        vis[i] = 0;
    }
    cout << res << '\n';
    return 0;
}

L - 知

Question

游戏由 $n$ 个关卡组成，你事先知道通过每个关卡的概率，即 $\frac{a_{1}}{100}, \frac{a_{2}}{100}, \dots, \frac{a_{n}}{100}$ ，其中 $a_{i}$ 是非负整数。

您可以执行任意数量的操作。每个操作都允许您选择一个索引 $i (1 \leq i < n, a_{i + 1} > 0, a_{i} < 100)$ ，并将 $a_{i + 1}$ 递减一个，同时将 $a_{i}$ 递增一个。

执行操作后，开始游戏，目标是最大限度地提高通过所有关卡的概率。

输出最大概率乘以 $100^{n}$ ，模数为 $998244353$ 。

$1 \leq T, n, a_{i} \leq 100$ .

Solution

我们的想法，肯定是让 $p_{i}$ 尽量均匀

但是由于我们只能让后面一个变小，然后前面一个变大

所以暴力的把，如果 $a_{i + 1} > a_{i}$ 那么，让 c $a_{i + 1} - 1, a_{i} + 1$

暴力跑可能超时，所以，我们开一个 set<int> 记录下后面所有数，如果当前的 $a_{i}$ 小于 set 中最小的数，那么把 set 中最大的数 $- 1$ ，把 $a_{i} + 1$

Code

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

typedef long long ll;
const ll TT = 998244353;

void solve() {
    int n; cin >> n;
    ll sum = 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    multiset<int> s;
    for (int i = n; i >= 1; i--) {
        while (true) {
            if ((!s.empty()) && a[i] < *s.rbegin()) {
                auto it = s.end(); --it;
                int x = *it;
                s.erase(it); x -= 1; a[i] += 1;
                s.insert(x);
            }
            else {
                s.insert(a[i]);
                break;
            }
        }
    }
    ll res = 1;
    for (auto x : s) res = res * x % TT;
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}