2024牛客暑期多校训练营5

难度梯度 EBLH JGK FCM DI A

B 珑

题意

有一个 \(n*m\) 的空白矩阵，有 \(1*2\) 和 \(2*1\) 的长方形。

每个位置只能被一个长方形覆盖，问在以下约束下，是否能覆盖完整个矩阵。

① 长方形的短边不能相邻，也就是说长度为 \(1\) 的边不能相邻。

② 长方形的长边不能相邻，也就是说长度为 \(2\) 的边不能相邻，并且共用一部分也不行。

解题思路

我们先钦定 \(n\le m\)，

如果总方格数量为奇数，那么我们可以知道一定不存在能覆盖完整个矩阵的方案。

然后我们只需要考虑总方案数量为偶数的方案了。

最开始，考虑 \(n=1,m=2\)，这样无论两个条件存在不存在都一定存在方案覆盖。

在特判完 \(n=1,m=2\) 的情况下，

然后考虑两个条件都存在，这样不可能使用两个及两个以上的长方形，所以一定没有方案能够覆盖。

然后再考虑两个条件都不存在，这样很容易发现，一定有方案能够覆盖。

接下来剩下，只有条件①或条件②的情况了。

只有条件①的情况下，我们容易构造出两种不同的 \(2*2\) 的方阵。

然后间隔搭配，这样一定能构造出 \(n\) 和 \(m\) 都为偶数的方案。

然后我们考虑一奇一偶，假设 \(n=3,5,7\)

我们发现可以构造出来。

但是我们会发现 \(n=1\) 是构造不出来的。

所以只有条件①时，只要 \(n\neq1\) 就一定能构造出来。

然后我们再来考虑条件②，我们会发现只要 \(n\ge2\)，一定会有长边相邻。

当 \(n=1\) 的时候，不可能有长边相邻。

所以只有条件②时，只有 \(n=1\) 才一定能构造出来。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    i64 n, m, a, b;
    cin >> n >> m >> a >> b;
    if (n > m) swap(n, m);
    if (n == 1 && m == 2) {
        cout << "Yes\n";
        return;
    }
    if (n * m % 2 == 1 || a + b == 0) {
        cout << "No\n";
        return;
    }
    if (a + b == 2) {
        cout << "Yes\n";
        return;
    }
    if (a == 0 && b == 1) {
        if (n != 1) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
        return;
    }
    if (a == 1 && b == 0) {
        if (n == 1) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
        return;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E 安

题意

May 和 Ray 两个人，分别都有 \(n\) 个骑士，对于第 \(i\) 个骑士，生命值分别为 \(a_i,b_i\)。

两人每回合可以选择一名己方的骑士，攻击对方对应位置的骑士(若对方骑士死亡，则无法进行操作)，被攻击的骑士血量将 \(-1\)。

当骑士血量为 \(0\) 时，该骑士死亡。当所有骑士都不能进行攻击时，游戏结束。

\(May\) 先手。问游戏结束后，\(May\) 可能剩余的骑士的数量的最大值。

解题思路

当 \(a_i>b_i\) 时，无论如何，\(May\) 都可以让这位骑士最终存活。

当 \(a_i<b_i\) 时，无论如何，\(Ray\) 都可以让这位骑士最终死亡。

当 \(a_i=b_i\) 时，可以发现，相当于把先手翻转，也就是说每两个这种情况，\(May\) 只能让其中一位骑士存活。

所以答案为 \(cnt_{a_i>b_i}+\dfrac{cnt_{a_i=b_i}+1}{2}\)

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long; 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0 ; i < n ; i++) cin >> a[i];
    for (int i = 0 ; i < n ; i++) cin >> b[i];
    int ans = 0, cnt = 0;
    for (int i = 0 ; i < n ; i++) {
        ans += (a[i] > b[i]);
    }
    for (int i = 0 ; i < n ; i++) {
        cnt += (a[i] == b[i]);
    }
    cout << ans + (cnt + 1) / 2 << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t ;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

H 入

题意

\(n\) 个点 \(m\) 条边的无向带权图。

每个回合，都移动到与当前点相邻的点的权值最小的那个点。

当无法移动，则游戏结束。

现在你可以随意安排起点和任意点的点权，点权必须两两不同。

问所有可能的情况中访问过的点的数量的最大值。

解题思路

通过移动的条件，我们可以知道，如果从 \(u\) 走到了 \(v\)，那么 \(u\) 相邻的所有点就不可能再被访问。这里我们直接枚举起点爆搜即可。

复杂度证明，设每个点度数为 \(x\)。

那么根据条件，一共会递归 \(\dfrac{n}{x}\) 层，每次遍历 \(x\) 条边,

总共遍历 \(n*x^{\dfrac{n}{x}}\)

当 \(x=3\) 的时候达到最大值

所以时间复杂度是 \(O(n*3^{\dfrac{n}{3}})\)

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
vector<int> adj[45];
int vis[45];
int ans, res = 1;
void dfs(int u, int p) {
    ans = max(ans, res);
    for (auto &to : adj[u]) {
        if (to == p) continue;
        if (vis[to]) continue;
        for (auto &x : adj[u]) {
            if (x == to) continue;
            vis[x]++;
        }
        res++;
        dfs(to, u);
        res--;
        for (auto &x : adj[u]) {
            if (x == to) continue;
            vis[x]--;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0 ; i < m ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1 ; i <= n ; i++) {
        dfs(i, 0);
    }
    cout << ans << "\n";
    return 0;
}

K 思

题意

Alice 和 Bob 在玩猜数游戏。

Alice 在心中想了一个整数 \(x\)，让 Bob 猜。

Bob 每次询问一个整数 \(y\)，Alice 会告诉 Bob 是否 \(x\ge y\)。

然后每次询问的代价为 \(|x-y|\)。

给出一个长度为 \(n\) 的数组 \(a\)。

已知 \(x\in a\)，问 \(x\) 所有可能中，询问最小代价之和的最大值。

解题思路

区间dp。

我们定义 \(dp_{L,R,C}\) 为答案在 \(a_L\) 到 \(a_R\) 之间，且 \(L\) 左侧查询次数减去 \(R\) 右侧查询次数为 \(c\) 的代价之和。

我们可以定义 \(dp_{i,i,c}=a_i*c\) 。可以知道查询次数不会多于 \(\log n\) 次，所以我们暂定 \(-40\le c\le40\)。

目前区间为 \([L,R]\)，我们可以从 \([L,k-1]\) 和 \([k,R]\) 合并过来。

假设左边区间的贡献为 \(lval\)，右边区间的贡献为 \(rval\)。

那么我们本次询问的值 \(val\in(a_{k-1},a_k]\)。

当我们询问值 \(val\)，合并后的代价为 \(\max(lval+val,rval-val)\)，

因为对于答案在左边的区间，我们选择了一个它右边的数，那么去掉绝对值后是加 \(val\)，

相反对于答案在右边的区间，我们选择了一个它左边的数，那么去掉绝对之后是减 \(val\)。

我们要让这个 \(\max\) 更小，也就是尽可能满足 \(lval+val=rval-val\)，即 \(val=\frac{rval-lval}{2}\)

如果这样计算出来的值不在 \((a_{k-1},a_k]\)，那么我们就把他移到端点。

然后我们会发现对于区间 \([L,R+1]\)，这样的 \(val\) 值，一定是 \(\ge\) 区间\([L,R]\) 的 \(val\) 值。

所以这里可以做一个双指针。

当我们枚举的左侧查询次数减去右侧查询次数为 \(c\) 时，

那么 \([L,k-1]\) 区间的次数之差应该为 \(c-1\)，因为此时我们询问的是 \(k-1\) 右侧的。

同理 \([k,R]\) 区间的次数之差应该为 \(c+1\)，因为我们询问的是 \(k\) 左侧的。

我们只有在询问次数之差的时候才恰好是最小代价之和。

所以答案为 \(dp_{1,n,0}\)。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int a[1005];
i64 dp[1005][1005][85];
const int M = 40;
const i64 inf = 1e18;
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for (int i = 1 ; i <= n ; i++) {
        for (int j = i ; j <= n ; j++) {
            for (int k = -40 ; k <= 40 ; k++) {
                dp[i][j][k + M] = i == j ? a[i] * k : inf;
            }
        }
    }
    for (int L = n ; L >= 1 ; L--) {
        for (int k = -40 + 1 ; k <= 40 - 1 ; k++) {
            int r = L + 1;
            for (int R = L + 1 ; R <= n ; R++) {
                while (r <= R) {
                    i64 left = dp[L][r - 1][k - 1 + M], right = dp[r][R][k + 1 + M];
                    if (left == inf || right == inf) break;
                    i64 val = (right - left + 1) / 2;
                    if (val > a[r]) val = a[r];
                    if (val < a[r - 1] + 1) val = a[r - 1] + 1;
                    i64 temp = max(left + val, right - val);
                    if (temp < dp[L][R][k + M]) {
                        dp[L][R][k + M] = temp;
                        r++;
                    } else {
                        break;
                    }
                }
                r--;
            }
        }
    }
    cout << dp[1][n][M] << "\n";
    return 0;
}

L 知

题意

\(n\) 个数 \(a_i(0\le a_i\le100)\)。

可以进行任意次操作。

每次操作选择一个下标 \(i\) 并且 \(a_i<100,a_{i+1}>0\)，使 \(a_i=a_i+1,a_{i+1}=a_{i+1}-1\)。

问数组的乘积之和的最大值可能是多少。答案对 \(998244353\) 取模。

解题思路

首先我们可以把操作转变为，对于第 \(i\) 个元素 \(a_i\)，\(a_i=a_i-1\) 且 \(j<i\) 的任意一个 \(a_j=a_j+1\)。

那么可以确定一个顺序，一定是从 \(i=1\) 枚举到 \(i=n\) 的，因为 \(i\) 不会对后面的元素造成影响。

那我们怎么确定一个关系，使得乘积之和最大？

当 \(a_i*a_j\le(a_i-1)*(a_j+1)\)，选择这个元素一定更优。

我们可以保证，被选择的 \(a_j\) 是当前 \(j<i\) 里面的最小的元素。

所以使用优先队列模拟即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int a[105];
const i64 P = 998244353;
void solve() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for (int _ = 0 ; _ < 300 ; _++) {
        for (int i = 2 ; i <= n ; i++) {
            while (a[i] > a[i - 1]) {
                a[i]--;
                a[i - 1]++;
            }
        }
    }
    i64 ans = 1;
    for (int i = 1 ; i <= n ; i++) {
        ans = ans * a[i] % P;
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}