昨天 22:21 已编辑衡阳师范学院 C++ 发布于上海

关注

牛客小白月赛 130 出题人题解

由于E数据水了点，导致个别选手的错解E代码交F卡住了，在这里说声抱歉，赛后将加强E的数据。

A

将 $80\%$ 看成 $\frac{4}{5}$ ，那么答案就是 $\frac{m\times 4+(5-1)}{5}\times n=\frac{(m+1)\times 4\times n}{5}$ ，表示向上取整的一个写法。

代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 998244353;
void solve() {
    i64 n, m; cin >> n >> m;
    i64 ans = (m + 1) * 4 / 5 * n;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
//     std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

B

注意到每次只能对相邻的两个数组中的元素进行操作，我们可以依次按照从左往右的顺序将数组中的每个元素通过操作转为目标元素，如果最后一个元素可以和目标元素匹配上，则答案为 YES，否则为 NO。时间复杂度： $O(n)$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 998244353;
void solve() {
	int n; cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i < n; i++) a[i + 1] += b[i] - a[i];
    if (a[n] == b[n]) cout << "Yes\n";
    else cout << "No\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

C

令 $k_x$ 表示大猴子 $x$ 被小猴子喜欢的次数、 $co(x, y)$ 表示同时喜欢 $x$ 和 $y$ 的小猴子数量，即 $(a_i,b_i)=(x,y)$ 或 $(b_i,a_i)=(x,y)$ 的对数，若最终选的大猴子为 $(x, y)$ ，则满意的小猴子数为：

k_x + k_y - co(x, y)

若喜欢次数最高的大猴子集合 $S$ 的大小 $len(S)\geqq 2$ ：则两只大王都必须从 $S$ 里选，上述式子，则变为：
$2\times \max\{k_1,k_2,\dots k_m\} - co(x,y),\left (x\in S,y\in S\right )$
现在只需最小化 $co(x,y)$ 的值，即可求出最多能满意的小猴子数量。
若集合 $S$ 的大小 $len(S)=1$ ：则第一只大王必须选择集合 $S$ ，另外一只大王只需选择喜欢度次大的大猴子即可，和上述式子一样，只需最小化 $co(x,y)$ 的值，即可求出最多能满意的小猴子数量。

以上两种情况，均可通过 $map$ 容器进行模拟，时间复杂度为： $O(n\log n)$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    int n, m; cin >> n >> m;
    vector<int> k(m + 1);
    map<pair<int, int>, int> mp;
    for (int i = 1, a, b; i <= n; i++) {
        cin >> a >> b;
        if (a > b) swap(a, b);
        k[a]++; k[b]++; mp[{a, b}]++;
    }

    int mx = 0, cmx = -1;
    for (int i = 1; i <= m; i++) mx = max(mx, k[i]);
    for (int i = 1; i <= m; i++) cmx = max(cmx, (k[i] != mx ? k[i] : 0));

    int cnt = 0, ccnt = 0;
    for (int i = 1; i <= m; i++) cnt += (k[i] == mx);
    for (int i = 1; i <= m; i++) ccnt += (k[i] == cmx);

    vector<int> vis(m + 1), cvis(m + 1);
    for (int i = 1; i <= m; i++) vis[i] = (k[i] == mx);
    for (int i = 1; i <= m; i++) cvis[i] = (k[i] == cmx);
    
    int ans = 0;
    if (cnt >= 2) {
        int sum = min(1000000LL, 1LL * (cnt - 1) * cnt / 2), mn = 1e9;
        for (auto &[u, v] : mp) {
            auto &[a, b] = u;
            if (vis[a] && vis[b]) mn = min(mn, v);
            sum -= (vis[a] && vis[b]);
        }
        ans = mx * 2 - (sum == 0 ? mn : 0);
    } else {
        int sum = ccnt, mn = 1e9;
        for (auto &[u, v] : mp) {
            auto &[a, b] = u;
            if ((vis[a] && cvis[b]) || (vis[b] && cvis[a])) mn = min(mn, v);
            sum -= ((vis[a] && cvis[b]) || (vis[b] && cvis[a]));
        }
        ans = mx + cmx - (sum == 0 ? mn : 0);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

D

根据题意可知，无论我们每次怎么操作， $\text{mex}(a_1,a_2,\dots,a_{n})$ 都是随着操作次数的增加而单调不减的。

假设当前 $\text{mex}(a_1,a_2,\dots,a_{n})=x$ ，如果我们选择了比 $x$ 小的数 $y$ 进行删除，那么剩余 $n-1$ 个数的 $\text{mex}$ 一定等于 $y$ ，故最终 $\text{mex}$ 保持不变，即 $\text{mex}(a_1,a_2,\dots,a_{n})=x$ ；那如果选择比 $x$ 大的数 $y$ 进行删除，那么剩余 $n-1$ 个数的 $\text{mex}$ 一定等于 $x$ ，故最终 $\text{mex}$ 变为 $y$ ，即 $\text{mex}(a_1,a_2,\dots,a_{n})=y$ ，故是随着操作次数的增加而单调不减的。

现在我们定义 $dp_{t,x}$ 表示执行恰好 $t$ 次操作，最终 $\text{mex}(a_1,a_2,\dots,a_{n})=x$ 的不同方案数，那么根据前面的推导现在我们知道，这种状态只能由上一次操作后 $\text{mex}(a_1,a_2,\dots,a_{n})\leqq x$ 的状态得到：

当上一次操作 $\text{mex}(a_1,a_2,\dots,a_{n})< x$ 时，我们必须选择数 $x$ 将其删除（很明显数 $x$ 一定在当前序列中出现），这样状态才能变成 $\text{mex}(a_1,a_2,\dots,a_{n})= x$ 的状态，一共有 $1$ 种选取方式；
当上一次操作 $\text{mex}(a_1,a_2,\dots,a_{n})= x$ 时，我们可以选择 $\{0,1,\dots,x-1\}$ 中的任意一个数将其删除（数 $\{0,1,\dots,x-1\}$ 一定都在当前序列中出现），这样状态才能保持 $\text{mex}(a_1,a_2,\dots,a_{n})= x$ 的状态，一共有 $x$ 种选取方式；

所以现在我们可以推出动态规划方程为：

dp_{t,x}=dp_{t-1,x}\cdot x+\sum_{y=0}^{x-1}dp_{t-1,y}

可以发现 $\sum_{i=0}^{x-1}dp_{t-1,i}$ 这部分可以直接前缀和进行优化，即令 $pre_{t,x}=\sum_{i=0}^{x}dp_{t,i}$ ，这样式子转化为：

dp_{t,x}=dp_{t-1,x}\cdot x+pre_{t-1,x-1}

总时间复杂度为 $O(n\cdot k)$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 998244353;
i64 add(i64 x, i64 y) {
    return (x + y) % mod;
}
void solve() {
    int n, k, s = 0; cin >> n >> k;
    vector<int> vis(n + 1);
    for (int i = 1, x; i <= n; i++) {
        cin >> x; vis[x] = 1;
    }
    for (int i = 0; i <= n; i++) s = (vis[i] ? s : i);
    vector<vector<i64>> dp(k + 1, vector<i64>(n + 1)), pre(k + 1, vector<i64>(n + 1));
    dp[0][s] = 1;
    for (int x = 0; x <= n; x++) pre[0][x] = (x >= s);
    for (int x = 1; x <= n; x++) {
        for (int t = 1; t <= k; t++) {
            dp[t][x] = add(dp[t - 1][x] * x % mod, pre[t - 1][x - 1]);
            pre[t][x] = add(pre[t][x - 1], dp[t][x]);
        }
    }
    for (int x = 0; x <= n; x++) {
        i64 sum = 0;
        for (int t = 0; t <= k; t++) sum = add(sum, dp[t][x]);
        cout << sum << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

E

题目意思就是值为 $1$ 的位置可以向上或向左移动，然后求最少需要多少次移动，才能将原矩阵移动为满足有序序列 $A$ 的新矩阵。首先如果能满足要求，那么移动次数就一定是初始矩阵横纵坐标之和减去最终矩阵横纵坐标之和，然后验证是否满足移动要求，就需要贪心思想，因为是往上移动的，所以从最后一行开始贪心，由于我们是要满足有序序列 $\text{A}$ 对应的那几列都为 $1$ ，故对于当前这一行我们从左往右贪心，对于序列 $\text{A}$ 第一个 $1$ 的位置肯定是贪心它右边（包含这个位置）最靠近这个位置的 $1$ 移动到当前位置，以此类推，之后几个 $1$ 一样是这样贪心，如果找不到，就说明不满足，输出 $-1$ 即可，最后这一行剩余没被贪心的 $1$ 就需要将其移动到上一行，用于上一行贪心，以此类推，和之前一样的操作。

时间复杂度为： $O(n\cdot m)$ 。当然也可以通过 $set$ 的方式存储当前剩余的位置编号，然后进行贪心，时间复杂度： $O(n\cdot m\cdot\log m)$ 。

赛时有些选手用前缀和的写法过了 E题，但是对于二维数组进行前缀和其实是不对的，比如这组数据：

代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 998244353;
int a[505][505], b[505][505];
int lie[505];
bool check(int n, int m, int k) {
    memcpy(b, a, sizeof a);
    for (int i = n; i >= 1; i--) {
        int l = 0;
        for (int j = 1; j <= m; j++) {
            while (b[i][j] && l < k && lie[l] <= j) {
                l++;
                b[i][j]--;
            }
            b[i - 1][j] += b[i][j];
        }
        if (l < k) return false;
    }
    return true;
}

void solve() {
    int n, m, k; cin >> n >> m >> k;
    i64 ans = 0, sum = k * n;
    vector<int> S(k);
    for (int i = 0; i < k; i++) {
        cin >> S[i]; ans -= S[i] * n;
    }
    ans -= (1 + n) * n / 2 * k;
    for (int i = 0; i < k; i++) lie[i] = S[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            sum -= a[i][j];
            if (a[i][j]) ans += i + j;
        }
    }
    if (!sum && check(n, m, k)) {
        cout << ans << '\n';
    } else {
        cout << "-1\n";
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

F

困难版本是不给定序列 $\text{A}$ ，然后需要寻找一个字典序最大的序列 $\text{A}$ 使之满足要求，考虑字典序最小的情况，那肯定便是 $\text{A}=\{1,2,\dots,k\}$ ，如果它满足，我们就让 $\text{A}=\{2,3,\dots,k+1\}$ ，直到 $\text{A}=\{i,i+1,\dots,i+k-1\}$ 不满足为止，故当前序列 $\text{A}=\{i-1,i,\dots,i+k-2\}$ 则为我们目前字典序最大的一个序列，这里我们只是先贪心了第一位字典序最大化后对应的序列 $\text{A}$ ，可以直接固定第一位的位置不去管它，然后来看第二位，和上面的操作一样，我一样是选一段连续的区间贪心，之后的都是以此类推，最后即可得到我们字典序最大化的序列 $\text{A}$ ，然后根据移动次数一定是初始矩阵横纵坐标之和减去最终矩阵横纵坐标之和即可得到答案，如果中途没有一个满足的，则输出 -1。

然后check当前序列 $\text{A}$ 和前面简单版本E的写法一样，最终时间复杂度为： $O(n\cdot m^2)$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 998244353;
int a[125][505], b[125][505];
int lie[505];
bool check(int n, int m, int k) {
    memcpy(b, a, sizeof a);
    for (int i = n; i >= 1; i--) {
        int l = 0;
        for (int j = 1; j <= m; j++) {
            while (b[i][j] && l < k && lie[l] <= j) {
                l++;
                b[i][j]--;
            }
            b[i - 1][j] += b[i][j];
        }
        if (l < k) return false;
    }
    return true;
}

void solve() {
    int n, m, k; cin >> n >> m;
    int ans = 0, sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j]; sum += a[i][j];
            if (a[i][j]) ans += i + j;
        }
    }
    if (sum == 0) {
        cout << "0\n";
        return;
    }
    if (sum % n != 0) {
        cout << "-1\n";
        return;
    }
    k = sum / n;
    for (int i = 0; i < k; i++) lie[i] = i + 1;
    int p = 0;
    while (p < k) {
        bool vis = true;
        while (lie[k - 1] <= m && check(n, m, k)) {
            vis = false;
            for (int i = p; i < k; i++) lie[i]++;
        }
        if (vis) break;
        for (int i = p; i < k; i++) lie[i]--;
        p++;
    }
    for (int i = 0; i < k; i++) ans -= lie[i] * n;
    ans -= (n + 1) * n / 2 * k;
    if (check(n, m, k)) cout << ans << '\n';
    else cout << "-1\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}