算法竞赛中的小球放盒子问题

背景：写题的时候遇到过很多关于这类问题的变种题，所以打算总结一下

问题分类

根据球是否不同，盒子是否不同，盒子是否为空，一共可以分为 23 种情况讨论

Problem 1

题意

给定 N 个不同的球，放进 M 个不同的盒子，盒子允许为空，有多少种方案？

解析

从每个球的角度出发，每个球都有M种放法，所以就是 MN

题目链接

Problem 1

代码

#include
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个部分，所以答案是 CM−1N−1

题目链接

Problem 2

代码

#include
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 个空隙，答案就是 CM−1M+N−1
每次插入板子后形成的组合，把右边的球去掉，可以发现就是我们所需要的答案

题目链接

Problem 3

代码

#include
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]

题目链接

Problem 4

代码

#include
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] （即假定每个盒子已经有一个球了）

题目链接

Problem 5

代码

#include
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]×j
所以转移方程就是从 dp[i][j]=dp[i−1][j−1]+dp[i−1][j]×j
其实这个是第二类斯特林数，存在通项公式可以优化时间复杂度，这里不再赘述，有兴趣的可以自己下来研究一下

题目链接

Problem 6

代码

#include
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个问题一样，答案抽象出来其实是 ∑ni=1dp[n][i]
因为这里的区别就是有盒子可以为空，那么在第6个问题中 dp[n][j] 表示成把n个球放进j个盒子里的方案数，并且盒子不为空
其实在这个问题中就等价于有j个盒子不为空，而另外m-j个盒子为空的情况

题目链接

Problem 7

代码

#include
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!×dp[n][m]

题目链接

Problem 8

#include
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;
}