算法竞赛中的小球放盒子问题
背景：写题的时候遇到过很多关于这类问题的变种题，所以打算总结一下
问题分类
根据球是否不同，盒子是否不同，盒子是否为空，一共可以分为 \(2^{3}\) 种情况讨论
Problem 1
题意
给定 N 个不同的球，放进 M 个不同的盒子，盒子允许为空，有多少种方案？
解析
从每个球的角度出发，每个球都有M种放法，所以就是 \(M^{N}\)
题目链接
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int qmi(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
while(cin >> n >> m)
cout << qmi(m,n) << endl;
return 0;
}
Problem 2
题意
给定 N 个相同的球，放进 M 个不同的盒子，盒子不允许为空，有多少种方案？
解析
这个就是经典的隔板法问题，相当于把N个球用隔板分成M个部分
N个球有N-1个空隙，在空隙中选择M-1个作为隔板将原来分成M个部分，所以答案是 \(C_{N-1}^{M-1}\)
题目链接
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int sp[20];
int qmi(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int C(int a,int b){
if(b > a) return 0;
int p = sp[a];
int q = sp[b];
int r = sp[a - b];
int res = p / q;
return res / r;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
sp[0] = 1;
for(int i = 1; i <= 15; i++) sp[i] = sp[i-1] * i;
while(cin >> n >> m){
cout << C(n-1,m-1) << endl;
}
return 0;
}
Problem 3
题意
给定 N 个相同的球，放进 M 个不同的盒子，盒子允许为空，有多少种方案？
解析
和问题2类似，只需要把隔板法变形一下。
我们可以假定每个隔板的右边自带了一个小球，那么这样总共就会有 N+M 个小球，选 M-1 个空隙，答案就是 \(C_{M+N-1}^{M-1}\)
每次插入板子后形成的组合，把右边的球去掉，可以发现就是我们所需要的答案
题目链接
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int sp[20];
int qmi(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int C(int a,int b){
if(b > a) return 0;
else return sp[a] / sp[b] / sp[a-b];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
sp[0] = 1;
for(int i = 1; i <= 20; i++) sp[i] = sp[i-1] * i;
while(cin >> n >> m){
cout << C(n+m-1,n) << endl;
}
return 0;
}
Problem 4
题意
给定 N 个相同的球，放进 M 个相同的盒子，盒子允许为空，有多少种方案？
解析
利用动态规划解决，设 \(dp[i][j]\) 表示将i个小球放到j个盒子里的方案数，那么初始化显然有 \(dp[0][0] = dp[0][1] = …… = dp[0][m] = 1\)
转移分两种情况考虑，第一种就是允许有盒子为空的情况 那么就是 \(dp[i][j-1]\)
第二种是不允许有空盒， 此时可以假定j个盒子里每个盒子已经有了一个球（或者可以理解为把每个盒子抽一个球之后再放回去）
这种方案数等价于 \(dp[i-j][j]\)
所以转移方程就是 \(dp[i][j] = dp[i][j-1] + dp[i-j][j]\)
题目链接
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int sp[20];
int dp[20][20];
int qmi(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int C(int a,int b){
if(b > a) return 0;
else return sp[a] / sp[b] / sp[a-b];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
sp[0] = 1;
for(int i = 1; i <= 20; i++) sp[i] = sp[i-1] * i;
for(int i = 1; i <= 15; i++) dp[0][i] = 1;
for(int i = 1; i <= 15; i++){
for(int j = 1; j <= 15; j++){
if(i >= j)
dp[i][j] = dp[i][j-1] + dp[i-j][j];
else dp[i][j] = dp[i][j-1];
}
}
while(cin >> n >> m){
cout << dp[n][m] << endl;
}
return 0;
}
Problem 5
题意
给定 N 个相同的球，放进 M 个相同的盒子，盒子不允许为空，有多少种方案？
解析
跟第4个问题几乎一样，转移方程也一样，只不过这次变成了盒子不能为空
那么最后的答案就是 \(dp[n-m][m]\) （即假定每个盒子已经有一个球了）
题目链接
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int sp[20];
int dp[20][20];
int qmi(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int C(int a,int b){
if(b > a) return 0;
else return sp[a] / sp[b] / sp[a-b];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
sp[0] = 1;
for(int i = 1; i <= 20; i++) sp[i] = sp[i-1] * i;
for(int i = 1; i <= 15; i++) dp[0][i] = 1;
for(int i = 1; i <= 15; i++){
for(int j = 1; j <= 15; j++){
if(i >= j)
dp[i][j] = dp[i][j-1] + dp[i-j][j];
else dp[i][j] = dp[i][j-1];
}
}
while(cin >> n >> m){
if(n >= m)
cout << dp[n-m][m] << endl;
else cout << 0 << endl;
}
return 0;
}
Problem 6
题意
给定 N 个不同的球，放进 M 个相同的盒子，盒子不允许为空，有多少种方案？
解析
依然采用动态规划解决，设 \(dp[i][j]\) 表示将i个小球放到j个盒子里的方案数
考虑两种情况，第一种情况，多了一个空盒子，多出来的球就放这个空盒子里，即 \(dp[i-1][j-1]\)
第二种情况，多出来的球放到之前的盒子里，由于有j个相同的盒子，即 \(dp[i-1][j] \times j\)
所以转移方程就是从 \(dp[i][j] = dp[i-1][j-1] + dp[i-1][j] \times j\)
其实这个是第二类斯特林数，存在通项公式可以优化时间复杂度，这里不再赘述，有兴趣的可以自己下来研究一下
题目链接
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int dp[20][20];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
dp[0][0] = 1;
for(int i = 1; i <= 15; i++){
for(int j = 1; j <= 15; j++){
dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j];
}
}
while(cin >> n >> m){
cout << dp[n][m] << endl;
}
return 0;
}
Problem 7
题意
给定 N 个不同的球，放进 M 个相同的盒子，盒子允许为空，有多少种方案？
解析
跟第6个问题一样，答案抽象出来其实是 \(\sum_{i=1}^ndp[n][i]\)
因为这里的区别就是有盒子可以为空，那么在第6个问题中 \(dp[n][j]\) 表示成把n个球放进j个盒子里的方案数，并且盒子不为空
其实在这个问题中就等价于有j个盒子不为空，而另外m-j个盒子为空的情况
题目链接
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int dp[20][20];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
dp[0][0] = 1;
for(int i = 1; i <= 15; i++){
for(int j = 1; j <= 15; j++){
dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j];
}
}
while(cin >> n >> m){
int res = 0;
for(int i = 1; i <= m; i++){
res += dp[n][i];
}
cout << res << endl;
}
return 0;
}
Problem 8
题意
给定 N 个不同的球，放进 M 个不同的盒子，盒子不允许为空，有多少种方案？
解析
可以先假定盒子都相同，问题转化为问题6
然后考虑不同盒子的排列即可
最后答案是 \(M! \times dp[n][m]\)
题目链接
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int dp[20][20];
int sp[20];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
sp[0] = 1;
for(int i = 1; i <= 15; i++) sp[i] = sp[i-1] * i;
dp[0][0] = 1;
for(int i = 1; i <= 15; i++){
for(int j = 1; j <= 15; j++){
dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j];
}
}
while(cin >> n >> m){
cout << sp[m] * dp[n][m] << endl;
}
return 0;
}
