K - 华丽收场

基本信息

题目出处	2023 ICPC 亚洲区域赛南京站
队伍通过率	9/342 (2.6%)

题解

以下用 \([1]\) 表示打出后可以抽一张牌的 \(Q\)，用 \([2]\) 表示打出后可以抽两张牌的 \(B\)。

首先可以观察到：

• 在满手牌之前，打出一张 \([1]\) 手牌数量不变，打出一张 \([2]\) 手牌数量加一。
• 一旦到达了满手牌状态，无论之后怎么打牌，都会保持满手牌。

从以上两点可以得出以下结论：

• 手牌数量随着游戏进行是单调不降的。
• 如果有最小可行的 \(k\)，那么决策的过程中一定会有一个时刻手牌数量到达了上限，否则 \(k\) 还可以更小。

也就是说，最优解一定会进入满手牌状态，且进入满手牌状态以后，所有的决策都不再受 \(k\) 的大小的影响。因此可以将本题分为两部分解答：手牌没满的情况，以及手牌满了之后的情况。

对于进入满手牌状态后的最优决策，我们可以利用动态规划求解。令 \(f(i, j)\) 表示当前手牌已满，手上有 \(j\) 张 \([2]\)，已经从牌堆抽了 \(i\) 张牌，最少需要此时手上还有多少张 \([1]\) 才能抽完。转移方程可以枚举下一张使用的牌是 \([1]\) 还是 \([2]\)。

在求出所有 \(f(i, j)\) 的基础上，我们枚举手牌上限 \(k\)，尝试判断它是否可行。我们可以枚举第一次进入满手牌状态时，牌堆里已经抽了 \(t\) 张牌，此时：

• 因为手牌未满时，打出一张 \([2]\) 手牌数量加一。进入满手牌状态时，手牌数增加了 \((k - n)\)，即我们一共打出了 \((k - n)\) 张 \([2]\)。
• 同样地，由于我们抽了 \(t\) 张牌，又已经知道打出了几张 \([2]\)，自然也能算出打出了 \(t - 2(k - n)\) 张 \([1]\)。

不妨预处理 \(s_1(i)\) 表示起始手牌加上牌堆的前 \(i\) 张牌中共有几张 \([1]\)，\(s_2(i)\) 表示起始手牌加上牌堆的前 \(i\) 张牌中共有几张 \([2]\)，则此时手牌中 \([1]\) 的数量 \(c_1\) 以及 \([2]\) 的数量 \(c_2\) 即可算出来：

\[ \begin{matrix} c_1 = s_1(t) - (t - 2(k - n)) \\ c_2 = s_2(t) - (k - n) \end{matrix} \]

判断 \(f(t, c_2) \le c_1\) 是否成立即可知道 \(k\) 是不是一个可行的手牌上限。但需要留意的是，即使在不触及手牌上限的情况，我们不一定能通过抽卡到达 \(f(t, c_2)\) 这一个状态，或者这个状态本身就不合法 (即 \(c_1 < 0\) 或者 \(c_2 < 0\))。因此我们需要一个额外的部分来判断能否在不触及手牌上限的情况下到达这个状态。

这里有多种解决方法，其中一种思路是再次采用动态规划，令 \(g(i, j) = 0 / 1\) 表示不考虑手牌上限的情况下，当前手上有 \(j\) 张 \([2]\)，从牌堆中抽了 \(i\) 张牌是否可行。由于不存在手牌上限，所以此时手上有多少张 \([1]\) 在 \(j\) 确定的情况下是可以计算得出的，所以这里同样可以通过枚举下一张使用的牌是 \([1]\) 还是 \([2]\) 进行转移。

那么我们就完善了判断一组 \((k, t)\) 是否合法的条件:

\[ (c_1 \geq 0) \land (c_2 \geq 0) \land (f(t, c_2) \le c_1) \land (g(t, c_2) = 1) \]

复杂度 \(\mathcal O(nm)\)。

参考代码

#include <bits/stdc++.h>
#define MAXN 2500
#define MAXM 2500
#define INF ((int) 1e9)
using namespace std;

int n, m;
char H[MAXN + 10], P[MAXM + 10];

int num[MAXM + 10][3], f[MAXM + 10][MAXM / 2 + 10];
bool g[MAXM + 10][MAXN + MAXM + 10];

int idx(char c) {
    if (c == 'Q') return 1;
    else if (c == 'B') return 2;
    else return 0;
}

// 当前手牌已满，手上有 j 张 [2]，已经从牌堆抽了 i 张牌，最少需要此时手上还有多少张 [1] 才能抽完
// 单独提一个函数是为了优化 j * 2 >= m - i 的情况，此时只要把 [2] 都打出去就能抽完牌，不需要 [1]
int query(int i, int j) {
    if (j * 2 >= m - i) return 0;
    return f[i][j];
}

void solve() {
    scanf("%d%d%s%s", &n, &m, H + 1, P + 1);

    // 预处理初始手牌以及前 i 张手牌里共有几张 [1] 和 [2]
    for (int i = 0; i < 3; i++) num[0][i] = 0;
    for (int i = 1; i <= n; i++) num[0][idx(H[i])]++;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < 3; j++) num[i][j] = num[i - 1][j];
        num[i][idx(P[i])]++;
    }

    // 计算 f[i][j] 表示
    // 当前手牌已满，手上有 j 张 [2]，已经从牌堆抽了 i 张牌，最少需要此时手上还有多少张 [1] 才能抽完
    for (int i = m - 1; i >= 0; i--) for (int j = 0; j * 2 < m - i; j++) {
        f[i][j] = INF;

        // 下一张打 [1]
        // 注意这里的 max(..., 1)，因为我们要打一张 [1] 再摸一张 [1]，所以至少需要 1 张 [1]
        if (P[i + 1] == 'Q') f[i][j] = min(f[i][j], max(query(i + 1, j), 1));
        else if (P[i + 1] == 'B') f[i][j] = min(f[i][j], query(i + 1, j + 1) + 1);
        else f[i][j] = min(f[i][j], query(i + 1, j) + 1);

        // 下一张打 [2]，至少需要一张 [2]
        if (j == 0) continue;
        if (P[i + 1] == 'Q') f[i][j] = min(f[i][j], max(query(i + 2, j - 1) - 1, 0));
        else if (P[i + 1] == 'B') f[i][j] = min(f[i][j], query(i + 2, j));
        else f[i][j] = min(f[i][j], query(i + 2, j - 1));
    }

    for (int i = 0; i <= m; i++) for (int j = 0; j <= num[m][2]; j++) g[i][j] = false;
    // 不考虑手牌上限的情况下，当前手上有 j 张 [2]，从牌堆中抽了 i 张牌是否可行
    g[0][num[0][2]] = true;
    for (int i = 0; i < m; i++) for (int j = 0; j <= num[i][2]; j++) if (g[i][j]) {
        // 计算当前手上有几张 [1]
        int one = num[i][1] - (i - 2 * (num[i][2] - j));
        if (one < 0) continue;

        // 下一张打 [1]
        if (one > 0) {
            if (P[i + 1] == 'B') g[i + 1][j + 1] = true;
            else g[i + 1][j] = true;
        }

        // 下一张打 [2]
        if (j > 0 && i + 2 <= m) {
            int tmp = (P[i + 1] == 'B' ? 1 : 0) + (P[i + 2] == 'B' ? 1 : 0);
            g[i + 2][j - 1 + tmp] = true;
        }
    }

    // 枚举手牌上限 k，以及第一次达到手牌上限时，从牌堆摸了 t 张牌
    for (int k = n; k <= n + m; k++) for (int t = 0; t <= m; t++) {
        int cnt1 = num[t][1] - (t - 2 * (k - n));
        int cnt2 = num[t][2] - (k - n);
        if (cnt1 >= 0 && cnt2 >= 0 && query(t, cnt2) <= cnt1 && g[t][cnt2]) {
            printf("%d\n", k);
            return;
        }
    }
    printf("IMPOSSIBLE\n");
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}