题解：B4380 [蓝桥杯青少年组省赛 2025] 魔术扑克牌排列

· · 题解

解题思路

题目要求方案数，考虑动态规划。

考虑动态转移： - 如果第 $i$ 张牌是红牌，那么前 $i - 1$ 张牌需要有 $j - 1$ 张红牌，即 $f_{i, j} = f_{i - 1, j - 1}$。 - 如果第 $i$ 张牌是蓝牌，那么前 $i - 1$ 张牌需要有 $j$ 张红牌，即 $f_{i, j} = f_{i - 1, j}

所以 f_{i, j} = f_{i - 1, j - 1} + f_{i - 1, j}。

由于答案可能很大，需要用高精度进行计算。

AC_Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 3e2 + 10;

int n, m;
vector<int> f[N][N];

vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size() || i < B.size() || t; ++ i )
    {
        if (i < A.size())
            t += A[i];
        if (i < B.size())
            t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    return C;
}

int main()
{
    cin >> n;
    m = n * 2;

    f[1][1] = vector<int>(1, 1);
    for (int i = 2; i <= m; ++ i )
        for (int j = (i + 1) / 2; j <= n; ++ j )
            f[i][j] = add(f[i - 1][j - 1], f[i - 1][j]);

    vector<int> res(1, 0);
    for (int i = n; i >= n - i; -- i )
        res = add(res, f[m][i]);

    for (int i = res.size() - 1; i >= 0; -- i )
        cout << res[i];

    return 0;
}