2月12日 模拟题 递推 题解
综上，我们得到递推方程f[i] = f[i -1] * 2 + 1
利用这个方程便可求出答案。
又我们把答案从 1 到 n 列出来，可以发现每一个答案都等于2的x(圆盘数）方 - 1，就可以很直接的写出以下代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
long long x = 1;
int main()
{
int n;
cin >> n;
for(int i = 1;i <= n;i++)
{
x *= 2;
}
cout << x - 1;
return 0;
}
就这道题用到了一个问题划分的思想（本蒟蒻的理解方式），研究第一个或第一和第二个骨牌覆盖后剩余的覆盖方案：
我们依然用f[i]来表示当行列数为i时，摆放的方式数。
当i = 1 的时候摆放方式只有一种 i = 0 时纯粹是我们的假象边界，赋值为1.
1、第一个骨牌竖着放：那么这种情况下剩下的格数就是2*（i-1）格，方式数就是f[i - 1]种。
2、第一第二个骨牌都横着放，把第一个4*4的空间给占了：那么现在剩下2*（i - 2）格的空间，方式数就是f[i - 2]种。
那么总问题就应该是f[i] = f[i - 1] + f[i - 2] 啦！
实际上就是斐波拉契数列
这样我们可以写出：
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
long long a[55];
int main()
{
int n;
cin >> n;
a[0] = a[1] = 1;
for(int i = 2;i <= n;i++)
{
a[i] = a[i-1]+a[i-2];
}
cout << a[n];
return 0;
}
代码十分简单，但是理解的话本蒟蒻还是觉得站在蒟蒻的角度是不太好理解的。
一道状态转移的题
总而言之意思就是每个人可以传给旁边的俩人，可以传的次数为m，人数为n，就相当于一个圈，向左或向右传。
那么我们可以定状态为：f[i][j] 意为经j次传递传到i编号处的人时的总方案数。
因为成圈型结构，我们肯定要求模，所以从0开始计数。
边界有两个：
f[0][0] 当传递次数为 0 时传到 0号（也就是小蛮时）方案数为1
f[i][0] (i != 0) //当传递不了而球又不在小蛮手上时，方案数为0.
某位置的方案数应该等于从左传到右加上从右传到左的方案总和，所以如下：
f[i][j] = f[(i - 1 + n) % n][j - 1] + f[(i + 1) % n][j - 1];
代码：
#include<bits/stdc++.h>
using namespace std;
long long f[35][35];
int main()
{
int n,m;
cin >> n >> m;
f[0][0] = 1;//边界，当传递次数为 0 时传到 0号（也就是小蛮时）方案数为1
for(int i = 1;i < n;i++)
{
f[i][0] = 0;//当传递不了而球又不在小蛮手上时，方案数为0.
}
for(int j = 1;j <= m;j++)
{
for(int i = 0;i < n;i++)
{
f[i][j] = f[(i - 1 + n) % n][j - 1] + f[(i + 1) % n][j - 1];
}//f[i][j]表示当传递次数为j时传到i号时的方案数。
}
cout << f[0][m];
return 0;
}
这道题首先我们看到给出n个球，r个盒子，并且每个盒子都得有东西。
那么要解决这道题我们可以定义状态：
f[i][j] 表示当放球编号（也就是数量啦这道题中的话）为i放入了j个盒子·时所有的方案数
这样边界便可直接得出：
1、当盒子只有一个时（j == 1），我们只有一种放的方式，就是全部放进去。当球数和盒子数一样时(i == j），由于不能空盒，则只能一个盒子放一个，所以方案数也为1。
2、当球数小于盒子数时（i < j），由于不能有空盒，所以这样的方案数为0。
状态转移则需对任一编号球放入某盒子做分析：
1、当第i个球独自占有第j个盒子时，其他球放的方案就为f[i - 1][j - 1]
2、当第i个球和其他某些球一起在某盒子里时，由于放入盒子是随机的，则就有j种可能，所以此时方案数为f[i - 1][j]*j。
所以说代码如下：
#include<bits/stdc++.h>
using namespace std;
long long f[25][25];
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(j == 1 || i == j)
{
f[i][j] = 1;
}
else{
if(i < j)
f[i][j] = 0;
else {
f[i][j] = f[i - 1][j - 1] + f[i - 1][j]*j;
}
}
}
}
cout << f[n][m];
return 0;
}
错排：
是一道简单的代码，坑爹的推导过程的一道题。
如果你够厉害的话，可以直接把规律方程写出来，那么你这道题就AC了。
0 1 2 9 44 。。。。。(加油)
但本蒟蒻是没有做到的，于是乎我们就开始分析吧。
定义状态为：f[i]当人数为i时的方案数。
这道题边界是：
1、一个人时，不能交换，方案数为0。
2、俩人时，只能互相交换，方案数为1.
对某个同学x给一号同学书分析：
1、他刚好给了1号同学，一号同学的书也可以说给了他（毕竟x是随机某一个，我们可以就定为1号同学给的那个嘛），那么此时剩下i-2个人要互相交换书，方案数为f[i - 2]。
2、他没能给到1号同学，但我们可以假设一号同学把书给了他，理由同上，那么此时还有i - 1个人要互相交换书，所以方案数为f[i - 1]。
但要知道我们的x同学是任一同学，那么x的可能就有（i - 1）种（因为给了一号同学书，一号不可能为x），所以总方案数要乘以一个（i - 1）。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long f[25];
int main()
{
int n;
cin >> n;
f[1] = 0;
f[2] = 1;
for(int i = 3;i <= n;i++)//状态是i本书时的排列方式总数，
//看的是一本书交换后的两种情况之和
{
f[i] = (i - 1)*(f[i - 1] + f[i - 2]);
}
cout << f[n];
return 0;
}
就特简单，就让人觉得推理过程可怕。
接下来转到卡特兰数环节！