Codeforces Round 978 (Div. 2) 题解 & 复盘

D. Attribute Checks

官方题解：

首先，让我们介绍一个缓慢但正确的解决方案。如果我们先处理了 $i$ 条记录，且当前智力水平为 $I$ ，那么 $d [i] [I]$ 就是任务答案。如果我们知道智力等级 $I$ ，那么我们也就知道了当前的力量等级 $S = P - I$ ，其中 $P$ 只是前 $i$ 条记录中的总点数。
既然我们想使用 dp，那我们就来讨论一下转换：
如果最新一条记录是 $r_{i} = 0$ ，那么它就是一个点，只有两个选项：
我们要么提升了智力，所以最后的状态是 $d [i - 1] [I - 1]$ ；
或者提升了力量，从状态 $d [i - 1] [I]$ 开始。
换句话说，我们可以计算出 $d [i] [I] = max (d [i - 1] [I - 1], d [i - 1] [I])$ 。
如果最新一条记录是 $r_{i} > 0$ ，那么这是一次智力检查，不会影响状态，只会影响答案。对于所有 $I \geq r_{i}$ ， $d [i] [I] = d [i - 1] [I] + 1$ ；否则，就是 $d [i] [I] = d [i - 1] [I]$ 。
如果是 $r_{i} < 0$ ，则是强度检查，并以类似的方式影响数值。对于所有 $I \leq P + r_{i}$ ， $d [i] [I] = d [i - 1] [I] + 1$ ；否则，也是 $d [i] [I] = d [i - 1] [I]$ 。
好了，我们有了一个需要花费 $O (n m)$ 时间和内存的解决方案，但我们可以加快速度。注意，第一种情况只出现了 $O (m)$ 次，而第二和第三种情况只是范围加法。因此，如果我们能在 $O (1)$ 内完成加法运算，那么用线性时间处理第一种情况就足以达到 $O (m^{2} + n)$ 的复杂度。
如何在 $O (1)$ 时间内处理范围加法？让我们使用差分数组 $a$ 来偷懒。我们不需要在 $[l, r]$ 中添加数值 $v$ ，而只需要在 $a [l]$ 中添加数值 $v$ ，在 $a [r + 1]$ 中添加数值 $- v$ 。当遇到 $r_{i} = 0$ 时，我们将一次性 "推入" 所有累积的操作。
你需要添加到某个位置 $i$ 的总值是 $\sum_{j = 0}^{i} a [i]$ 。因此，我们可以在 $O (m)$ 中从左往右计算所有运算，并保持前缀和。
最后一个问题是降低空间复杂度。通常，我们只能存储最后两层：当前层 $i$ 和上一层 $i - 1$ 。但实际上，可以只存储一层，并进行就地更新。
让我们只存储 dp 的最后一层 $d [I]$ 。属性检查完全不会改变数组 $d$ 。在 $r_{i} = 0$ 的情况下，首先需要将 $a$ 中的所有数据推送到 $d$ ，然后需要重新计算 $d$ 中的值。但由于公式为 $d [I] = max (d [I], d [I - 1])$ ，因此只需按降序遍历 $I$ 即可，一切正常！
总的来说，我们的解决方案的时间复杂度为 $O (m^{2} + n)$ ，空间复杂度为 $O (m)$ 。

复盘：

注意到 $m$ 异常地小，所以可以猜测是 $Θ (m^{2})$ 的做法，又很明显是动态规划的题目，就可以很快地想到解法。

代码：

cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int n, m;
int dp[5010][5010];
int d1[5010], d2[5010];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    vector<int> v(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> v[i];

    int cur = 0, lst = 1;
    for (int i = 1; i <= n; i++) {
        if (v[i] == 0) {
            if (cur == 0) {
                cur++;
                lst = i + 1;
                continue;
            }
            for (int j = 0; j <= 5000; j++)
                d1[j] = 0, d2[j] = 0;
            for (int j = lst; j < i; j++)
                if (v[j] > 0)
                    d1[v[j]]++;
                else
                    d2[-v[j]]++;
            for (int j = 1; j <= 5000; j++) {
                d1[j] += d1[j - 1];
                d2[j] += d2[j - 1];
            }
            dp[cur][0] = dp[cur - 1][0] + d1[0] + d2[cur];
            dp[cur][cur] = dp[cur - 1][cur - 1] + d1[cur] + d2[0];
            for (int j = 1; j < cur; j++)
                dp[cur][j] = max(dp[cur - 1][j - 1], dp[cur - 1][j]) +
                             d1[j] + d2[cur - j];
            lst = i + 1;
            cur++;
        }
    }
    for (int j = 0; j <= 5000; j++)
        d1[j] = 0, d2[j] = 0;
    for (int j = lst; j <= n; j++)
        if (v[j] > 0)
            d1[v[j]]++;
        else
            d2[-v[j]]++;
    for (int j = 1; j <= 5000; j++) {
        d1[j] += d1[j - 1];
        d2[j] += d2[j - 1];
    }
    dp[cur][0] = dp[cur - 1][0] + d1[0] + d2[cur];
    dp[cur][cur] = dp[cur - 1][cur - 1] + d1[cur] + d2[0];
    for (int j = 1; j < cur; j++)
        dp[cur][j] =
            max(dp[cur - 1][j - 1], dp[cur - 1][j]) + d1[j] + d2[cur - j];

    int ans = 0;
    for (int i = 0; i <= m; i++)
        ans = max(ans, dp[m][i]);

    cout << ans << endl;

    return 0;
}

E. Card Game

官方题解：

假设我们要解决一种花色的问题。考虑两个玩家之间的纸牌分配；如何检查第一个玩家的纸牌和第二个玩家的纸牌之间是否至少存在一种匹配？
让我们把牌从最高级到最低级排序，并按此顺序进行检查。如果我们得到了第一位玩家的牌，我们就可以把它添加到待匹配牌的 "牌池" 中；如果我们得到了第二位玩家的牌，我们就把它与 "牌池" 中的一张牌进行匹配（如果没有，则不存在有效匹配）。因此，如果存在这种顺序的前缀，其中第二个玩家的牌的数量超过了属于第一个玩家的牌的数量，那么它就不是一个有效的分配。听起来耳熟吗？
假设属于第一位玩家的牌用开头的括号表示，属于第二位玩家的牌用结尾的括号表示。那么，如果我们只需要解决一种花色的问题，那么分布必须是一个规则的括号序列。因此，在这种情况下，我们只需计算常规括号序列的数量即可。
然而，如果至少有 $2$ 种花色，那么可能会有属于第一位玩家的 $1$ 种花色的 "额外" 牌，我们可以将其与属于第二位玩家的其他花色的 "额外" 牌进行匹配。为了解决这个问题，我们可以使用下面的动态编程：设 $d p_{i, j}$ 是分配前 $i$ 种花色的牌的方法数，这样就有 $j$ 张额外的属于 $1$ 个玩家的 $1$ 种花色的牌。
为了计算 $d p_{1, j}$ ，我们必须计算括号序列的数量，使得每个前缀的余额至少是 $0$ ，而整个序列的余额正好是 $j$ 。在我看来，最简单的方法是运行另一个动态编程（类似于 " $w_{x, y}$ 是具有 $x$ 个元素和平衡 $y$ 的序列数 "）；不过，你也可以尝试用类似于计算加泰罗尼亚数的组合方法来解决这个问题。
那么从 $d p_{i, j}$ 到 $d p_{i + 1, j^{'}}$ 的过渡呢？让我们迭代 $k$ -- 我们将使用 "额外" 牌的数量来匹配属于第二位玩家的 $(i + 1)$ （th-th）花色的牌，因此我们从 $d p_{i, j}$ 过渡到 $d p_{i + 1, j - k}$ 。
现在我们需要计算如何分配 $m$ 张相同花色的牌，使得第二位玩家得到的牌比第一位玩家多 $k$ 张，而第一位玩家的所有牌都可以配对。假设我们把牌从最低等级排到最高等级。那么，在每个前缀上，属于第一位玩家的牌的数量不应该超过属于第二位玩家的牌的数量（否则我们将无法匹配属于第一位玩家的所有牌），总的来说，属于第二位玩家的牌的数量应该大于 $k$ 。因此，这正是每个前缀的余额为 $\geq 0$ ，而总余额等于 $k$ 的括号序列的数量（我们已经计算过了）！
因此，解决方案包括两个步骤。首先，对于每一个 $k \in [0, m]$ ，我们计算每个前缀上余额为非负，且总余额等于 $k$ 的括号序列的数量；然后，我们运行动态编程，其形式为 " $d p_{i, j}$ 是分配前 $i$ 种花色的牌的方法的数量，以便有 $j$ 额外的 $1$ 种花色的牌属于 $1$ （st）玩家 "。解法中最耗时的部分就是这个动态编程，它在 $O (n m^{2})$ 中起作用，因此整个解法在 $O (n m^{2})$ 中起作用。

复盘：

这也是一道动态规划，巧妙之处在于将匹配问题转化为了合法括号序列数问题，以及在预处理 $w_{x, y}$ 的时候使用了倒序 dp，避免了平衡系数为负数的讨论

代码：

cpp

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int n, m;
const long long M = 998244353;

long long w[510][510];
long long dp[510][510];

long long mad(long long x, long long y) { return (x + y) % M; }

long long mml(long long x, long long y) { return (x * y) % M; }

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    // 预处理:一种花色的牌中用了 j 张 1 的策略数
    w[0][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= i; j++)
            if (j)
                w[i][j] = mad(w[i - 1][j - 1], w[i - 1][j + 1]);
            else
                w[i][j] = w[i - 1][j + 1];

    // 动态规划 : 前 i 种花色 剩下 j 张 1 可用的策略数
    for (int i = 0; i <= m; i++)
        dp[1][i] = w[m][i];
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = j; k <= m; k++)
                dp[i][j] = mad(dp[i][j], mml(dp[i - 1][k], w[m][k - j]));

    for (int j = 0; j <= n; j++, cout << endl)
        for (int i = 0; i <= m; i++)
            cout << w[j][i] << ' ';
    cout << dp[n][0] << endl;

    return 0;
}

Codeforces Round 978 (Div. 2) 题解 & 复盘 ​

D. Attribute Checks ​

官方题解： ​

复盘： ​

代码： ​

E. Card Game ​

官方题解： ​

复盘： ​

代码： ​

Codeforces Round 978 (Div. 2) 题解 & 复盘

D. Attribute Checks

官方题解：

复盘：

代码：

E. Card Game

官方题解：

复盘：

代码：