题目 2660:
蓝桥杯2022年第十三届省赛真题-积木画
时间限制: 1Sec 内存限制: 256MB 提交: 623 解决: 135
题目描述
小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2 个单位面积）和 L 型（大小为 3 个单位面积）：
同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？ 积木可以任意旋转，且画布的方向固定。
输入
输入一个整数 N，表示画布大小。
输出
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。
样例输入复制
3
样例输出复制
5
提示
五种情况如下图所示，颜色只是为了标识不同的积木：
对于所有测试用例，1 ≤ N ≤ 10000000.
解题思路:哎，但凡是比赛的时候再测一个数据也不会不过，太可惜了，但是写的时候思路是对的，可惜a2写错了。
如：
或者
不管这三块是怎么放的，都叫a3.如果在此基础上右边多一个小方格就叫a3，注意小方格可以在第四列上一行也可以在第四列下一行（不好找图就不给了，自行想象）
给出动态规划方程：
a[i][0]=(a[i-2][0]+a[i-2][1]+a[i-1][0])%mod;
a[i][1]=(a[i-1][0]*2+a[i-1][1])%mod;
画布大小为i的排法，既ai的值：
- 先考虑少一块I型积木的排法，既ai-1,这时加上一块I型积木就行了，
- 再考虑少一块L型积木的排法，既ai-2,这时加上一块L型积木就行了,
- 考虑少两块I型积木的排法，既ai-2，加上两块I型积木，注意，两块必需横着加进去，如果是竖着加，就相当于第一种类型排法了，重复了。
- 涉及缺更多积木时，会发现无论怎么排，排法都会和上述情况重复,也就是说，以上三种情况涵盖了ai的所有排法。
所以有：
a[i][0]=(a[i-2][0]+a[i-2][1]+a[i-1][0])%mod;
ai的排法，大家可以自行画图写出来。
写出初始状态：
a[1][0]=1,a[2][0]=2,a[1][1]=2,a[2][1]=4;
给出完整代码：
#include<stdio.h>
#define mod 1000000007
longinta[10000001][2];
intmain()
{
intn;
a[1][0]=1,a[2][0]=2,a[1][1]=2,a[2][1]=4;
scanf("%d",&n);
if(n==1)printf("1");
elseif(n==2)printf("2");
else {
for(inti=3;i<=n;i++){
a[i][0]=(a[i-2][0]+a[i-2][1]+a[i-1][0])%mod;
a[i][1]=(a[i-1][0]*2+a[i-1][1])%mod;
}
printf("%ld",a[n][0]%mod);
}
return0;
}
如果有哪里看不懂，可以评论区或者私信我，如果觉得对你有用，就给本蒟蒻一个好评吧。
