今天的 XY 题居然是递推专题,五道题目全都是递推,30+个人 AK 了……
递推是按照一定的规律来计算序列中的每个项,通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复,该算法利用了计算机速度快和不知疲倦的机器特点。
"利用了计算机速度快和不知疲倦的机器特点" 😶
蛇皮目录
问题一
题目描述
在所有的 N 位数中,有多少个数中有偶数个数字 3?
Time Limit: 1000ms
Memory Limit: 65536Bit
输入输出格式
读入一个数 N。
输出答案。由于结果可能很大,你只需要输出这个答案 mod 12345 的值。
样例输入
2
样例输出
73
数据范围
1<=N<=1000
问题分析
很明显是递推(或者说 DP)。容易想到定义 $f(i)$ 表示在 $i$ 位数中有多少个数中有偶数个数字 3,但是这样如何进行状态转移呢?很明显,单纯这么定义无法直接状态转移。所以我们再定义 $g(i)$ 表示 $i$ 位数中有多少个数字中有奇数个数字 3。
考虑状态转移,对于 $f(i)$ 和 $g(i)$,肯定与 $i-1$ 位数字的情况有关。先考虑 $f(i)$:
- 如果第 $i$ 位数字(也就是相较于 $i-1$ 位,新增的一位数字)是 3,那么剩下的 $i-1$ 位就应该有奇数个 3,方案数是 $g(i-1)$;
- 如果第 $i$ 位数字不是 3,则可以是除了 3 以外的 9 个数字,剩下的 $i-1$ 位应当有偶数个 3,方案数:$f(i-1)\ast 9$
同理可以得出 $g(i)$ 的状态转移。转移方程:
f(i)=f(i-1)\ast 9+g(i-1) \\
g(i)=g(i-1)\ast 9+f(i-1)
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,tt=12345;
int n,f[maxn],g[maxn];
int main(){
scanf("%d",&n);
if (n==1) {printf("9\n");return 0;}
f[1]=8;g[1]=1;
for (int i=2;i<=n;i++){
f[i]=(f[i-1]*9%tt+g[i-1])%tt;
g[i]=(g[i-1]*9%tt+f[i-1])%tt;
}
printf("%d\n",f[n]);
return 0;
}
问题二
题目描述
用 1×1 和 2×2 的磁砖不重叠地铺满 N×3 的地板,共有多少种方案?
样例输入
2
样例输出
3
(数据范围、时空限制、输入输出格式同上)
问题分析
一看到这题可能会想到轮廓线 DP……其实根本没有这么复杂,注意到只有 1×1 和 2×2 两种地砖,那么对于每个 2×3 的矩形有两种情况:右边一块 2×2、左边两块 1×1 和 左边一块 2×2、右边两块 1×1。还有另一种情况就是每行三块 1×1。定义 $f(i)$ 表示铺 $i$ 行的方案数,那么递推式很容易得出:
f(i)=f(i-2)\ast 2+f(i-1)
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,tt=12345;
int n,f[maxn];
int main(){
scanf("%d",&n);
f[0]=1;
for (int i=1;i<=n;i++) f[i]=(f[i-2]*2%tt+f[i-1])%tt;
printf("%d\n",f[n]);
return 0;
}
问题三
题目描述
从原点出发,一步只能向右走、向上走或向左走。恰好走 N 步且不经过已走的点共有多少种走法?
样例输入
2
样例输出
7
(数据范围、时空限制、输入输出格式同上)
问题分析
一看这题,可能难点主要在“不经过已走的点”如何处理。如果我们定义 $f(i)$ 表示走了 i 步的方案数,那么“不经过已走的点”就没法处理了。
不妨定义 $f(i,0/1/2)$ 表示走了 i 步,最后一步向上/左/右走的方案数。那么上次是向右边走,这次就不能向左边走;上次向左,这次就不能向右。这样就可以直接进行状态转移了:
f(i,0)=f(i-1,0)+f(i-1,1)+f(i-1,2) \\
f(i,1)=f(i-1,0)+f(i-1,1) \\
f(i,2)=f(i-1,0)+f(i-1,2)
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,tt=12345;
int n,f[maxn][3];
int main(){
scanf("%d",&n);
f[1][0]=f[1][1]=f[1][2]=1;
for (int i=2;i<=n;i++){
f[i][0]=(f[i-1][0]+f[i-1][1]+f[i-1][2])%tt;
f[i][1]=(f[i-1][0]+f[i-1][1])%tt;
f[i][2]=(f[i-1][0]+f[i-1][2])%tt;
}
printf("%d\n",(f[n][0]+f[n][1]+f[n][2])%tt);
return 0;
}
问题四
题目描述
圆周上有 N 个点。连接任意多条(可能是 0 条)不相交的弦(共用端点也算相交)共有多少种方案?
样例输入
4
样例输出
9
(数据范围、时空限制、输入输出格式同上)
问题分析
也是很显然的递推题……一般这种题目我们可以“找规律”:
- 如果只有 0 个点,无法连接,只有一种方案,即全部不连。$f(0)=1$。
- 同理,如果只有一个点,$f(1)=1$。
- 如果有两个点,要么连接,要么不连,$f(2)=2$。
- (重头戏来了)如果有三个点,则新加入的点要么不与其他两个点连接(方案数:$f(2)$),要么随便选一个连接,“孤立”剩下的一个点,共 4 种方案。
(真正的重头戏)如果再加入一个点呢?
- 不与其他三个点连接,方案数 $f(3)$
- 与某个点连接,可以看成连成的这条边把点集分成了两部分,左右两部分剩下的点分别连边,方案数分别相乘。
在上述手算过程中我们发现了规律,总结出递推式就是:
f(i)=f(i-1)+ \sum_{j=0}^{i-2} f(j)\ast f(i-j-2)
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,tt=12345;
int n,f[maxn];
int main(){
scanf("%d",&n);
f[0]=f[1]=1;f[2]=2;
for (int i=3;i<=n;i++){
f[i]=f[i-1];
for (int j=0;j<=i-2;j++) f[i]=(f[i]+f[j]*f[i-j-2]%tt)%tt;
}
printf("%d\n",f[n]);
return 0;
}
问题五
题目描述
在网格中取一个 N×1 的矩形,并把它当作一个无向图。这个图有 2(N+1) 个顶点,有 3(N-1)+4 条边。这个图有多少个生成树?
样例输入
1
样例输出
4
(数据范围、时空限制、输入输出格式同上)
问题分析
(为了方便起见,在这里的分析中,我假设矩形从下到上安排)
首先我们可以定义 $f(i)$ 表示高度为 $i$ 的矩形形成生成树的个数。最开始我想到一个 naive 的想法:最底下的一个矩形有四种情况,上面每增加一个就有三种情况(如图),所以答案就是 $4\ast 3^{n-1}$ !
但是现实很残酷,很显然“梯子形”没有被我考虑到,即这样的情况:
所以我们不得不换一种定义:$f(i,0/1)$ 表示有 $i$ 个正方形,其中最上面一个正方形的最上面一条边取了/没取。因为接下来加入的正方形只和最上面一条边有关。考虑状态转移:
- 先考虑 $f(i,1)$ 如何转移:很简单,新加入的正方形上面一条边不取,只有一种情况,即“| |”。
接下来看看 $f(i,0)$ 怎么转移。
- 如果下面矩形最上面一条边没取,则有两种情况:左上、右上。
- 如果下面矩形最上面一条边取了,那么我们还要再考虑一种情况:可以把这条边拿来当做加入的正方形的最上面一条边(这个真的是想不到)。这样才保证了上面所述的“梯子形”可以考虑到。
转移方程:
f(i,0)=f(i-1,1)\ast 2+f(i-1,0)\ast 3 \\
f(i,1)=f(i-1,1)+f(i-1,0)
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1005,tt=12345;
int n,f[maxn][2];
int main(){
scanf("%d",&n);
f[1][0]=3;f[1][1]=1;
for (int i=2;i<=n;i++){
f[i][0]=(f[i-1][1]*2%tt+f[i-1][0]*3%tt)%tt;
f[i][1]=(f[i-1][0]+f[i-1][1])%tt;
}
printf("%d\n",(f[n][0]+f[n][1])%tt);
return 0;
}