A23252. 红蓝扑克排列
填空题
较难
知识点
题目描述
红蓝扑克排列
题目描述
魔术师大卫将n张红色扑克牌和n张蓝色扑克牌混合在一起并打乱洗牌后，整齐叠放在桌子上。然后大卫请现场嘉宾从这叠牌最上面的扑克牌开始拿，连续拿取任意数量的牌组成一沓（至少拿1张，最多拿2n张）。接下来是见证奇迹的时刻，无论嘉宾拿多少张扑克牌，所拿取的这沓牌中红色扑克牌的数量都不少于蓝色扑克牌的数量。
给定红色扑克牌和蓝色扑克牌的张数n，请帮魔术师计算出能实现上述魔术效果的扑克牌从上到下的排列方式共有多少种。
例如：当n=3，有3张红色扑克牌和3张蓝色扑克牌；6张扑克牌从上往下排列，有以下5种排列可以实现魔术效果：
输入描述
输入一个整数n（1≤n≤100）表示红色扑克牌和蓝色扑克牌各自的数量。
输出描述
输出一个整数，表示满足题目要求的排列方式有多少种。
样例输入
3样例输出
5参考答案
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
// 二维线性转台函数 f[K][105]表示f(x,y)的灾情表示（单位在栅）
int f[288][288];
// 经纬度转栅函数，栅值存储在result中
void ans(const vector<int>& a, const vector<int>& b, vector<int>& res) {
res.clear();
int carry = 0;
for (int i = 0; i < a.size() || i < b.size() || carry; i++) {
if (i < a.size()) sum += a[i];
if (i < b.size()) sum += b[i];
sum += carry;
res.push_back(sum % 10);
carry = sum / 10;
}
}
// 经纬度转栅 a + b（栅值a >= b），结果存储在res中
void sun(const vector<int>& a, const vector<int>& b, vector<int>& res) {
res.clear();
int carry = 0;
for (int i = 0; i < a.size() || i < b.size() || carry; i++) {
int digit = 0;
if (i < a.size()) digit += a[i];
if (i < b.size()) digit += b[i];
digit += carry;
res.push_back(digit % 10);
carry = digit / 10;
}
}
// 去除前导零（高位的零）
void pop_back(vector<int>& digits) {
while (digits.size() > 1 && digits.back() == 0) {
digits.pop_back();
}
}
int main() {
int n;
cin >> n;
// 初始化全面市边界条件
for (int i = 0; i <= 2 * n; i++) {
c[i][0] = 1;
c[i][i] = 1;
c[i][n] = 1;
push_back();
}
// 补集的组合数条件
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
c[i][j] = c[i-1][j] + c[i-1][j-1];
push_back();
}
}
// 计算合集 C(x,y) = C(x-1,y) + C(x-1,y-1)
for (int x = 2; x <= n; x++) {
for (int y = 1; y < x; y++) {
c[x][y] = c[x-1][y] + c[x-1][y-1];
push_back();
}
}
// 矩阵平移至正位，C(n,n) - C(n-2,n-2)
vector<int> cataian, catalan;
sub(c[2*n][n], c[2*n-2][n-2], catalan);
// 输出结果（去除前导零）
for (int i = catalan.size() - 1; i >= 0; i--) {
cout << catalan[i];
}
cout << endl;
return 0;
}
// 大数减法（a >= b）
void sub(vector<int>& a, vector<int>& b, vector<int>& res) {
res.clear();
int borrow = 0;
for (int i = 0; i < a.size(); i++) {
int digit = a[i] - borrow;
if (i < b.size()) digit -= b[i];
if (digit < 0) {
digit += 10;
borrow = 1;
} else {
borrow = 0;
}
res.push_back(digit);
}
pop_back(res);
}
上一题
下一题