2022蓝桥杯B组—积木画——递推算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了2022蓝桥杯B组—积木画——递推算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

积木画

题目描述

小明最近迷上了积木画，有这么两种类型的积木，分别为 $I$ 型（大小为 $2$ 个单位面积）和 $L$ 型（大小为 $3$ 个单位面积）：

2022蓝桥杯B组—积木画——递推算法

同时，小明有一块面积大小为 $2 \times N$ 的画布，画布由 $2 \times N$ 个 $1 \times 1$ 区域构成。

小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？

积木可以任意旋转，且画布的方向固定。

输入格式

输入一个整数 $N(1\le N \le 10^7)$ ，表示画布大小。

输出格式

输出一个整数表示答案。

由于答案可能很大，所以输出其对 $1000000007$ 取模后的值。

算法：递推 $O (n)$

思路

假设没有 $L$ 型积木，给你 $2\times N$ 的一个画布和 $I$ 型积木，那么这道题就是简单的递推题。
- 假设 $r e s [i]$ 表示在 $2\times i$ 的一个画布放 $I$ 型积木，恰好填充完整的方案数。
  1. 当 $i = 0$ 时，只有一种方案：不放 $\rightarrow res[0]=1$
  2. 当 $i\ge0$ 时
    - 因为我们要保证填放的积木时合法的（也就是最后能把画布刚好填充完）
    - $\rightarrow$ 这就意味着，我们放 $I$ 型积木有两种放法： $2 * 1 、 2 * 2$
    - 于是，对于 $2\times 3$ 的画布，我们相当于：
      1. 在 $2\times2$ 的画布基础上放置一个 $2\times 1$ 的积木
      2. 在 $2\times 1$ 的画布基础上放置一个 $2\times 2$ 的积木
    - 图例：
    - $\longrightarrow$ 于是我们得到了递推公式： $r e s [i] = r e s [i - 1] + r e s [i - 2]$
那么回到题目，在加入 $L$ 型积木后，我们怎么找到递推公式呢？
- 这里的关键点就在于题目给定的画布为 $2\times N$ ，并且我们的方案必定是恰好放完画布。
- 这就意味着， $L$ 型积木一定是成对出现的，不然一定无法恰好放完。
- 图例：
- 于是我们进一步分析， $L$ 型积木一定是成对出现的，意味着我们放 $L$ 型积木的时候相当于放一个 $2\times 3$ 的积木
- 图例：
- 同时，翻转一下这个 $\times3$ 的积木，也是一种方法
- 图例：
但是这就结束了吗？
- 仔细观测，我们会发现，虽然 $L$ 型积木是成对出现的，但是我们可以在里面穿插 $I$ 型积木
- 例如：
- 随着穿插的 $I$ 型积木数量增多，就相当于 $2\times 3、2\times 4、2\times 5\cdots$ 的积木
于是，这道题的题意就变成了：
- 给定一个 $2\times N$ 的画布，以及 $2\times 1、2\times 2、2\times 3\cdots$ 的积木，其中长度大于 $3$ 的积木，都有两种，求恰好把画布放完的方案数。
- 那么假设 $r e s [i]$ 表示在 $2\times i$ 的画布上放置积木，恰好填充完整个方案的方案数。
  1. $i = 0$ 时，只有一种方案：不放 $\rightarrow$ $r e s [0] = 1$
  2. $i\ge 1$ 时
    - 如果我们最后一步填充的是 $2\times 1、2\times 2$ 的积木，那就相当于 $r e s [i - 1] 、 r e s [i - 2]$
    - 如果我们最后一步填充的是 $2\times 3、2\times 4\cdots$ 的积木，那就相当于 $2\times res[i-3]、2\times res[i-4]$
    - 于是我们就得到了递推公式：
      - $\longrightarrow res[i]=res[i-1]+res[i-2]+2\times (res[i-3]+res[i-4]+\cdots+res[0])$

代码

如果直接实现递推公式，核心代码相当于两层循环 $O(n^2)$
```
res[0] = 1;	// 初始化
for(int i = 1 ; i <= n ; ++i){	// 枚举画布大小
    res[i] = res[i-1];
    if(i >= 2)	res[i] += res[i-2];
    for(int j = i-3 ; j >= 0 ; --j)	res[i] += 2*res[j]; // 枚举长度大于 3 的积木
}
```
- 但是由于本题的数据范围为 $10^7$ ， $O(n^2)$ 的算法会导致 $T L E$
- 于是，我们需要优化代码，我们仔细观察第二层循环，会发现其实这些状态我们在前面已经计算过了，相当于一个前缀和，于是我们能把第二层循环优化掉。
真正的核心代码 $O(n^2)$
```
res[0]=1;	// 初始化
sum=0;		// 存储 0 ~ (i-3) 的前缀和
for(int i = 1, j = -2; i <= n ; ++i, ++j){
 	res[i] = res[i-1];
    if(i >= 2)	res[i] += res[i-2];
    if(j >= 0)	sum += res[j];
    res[i] += sum << 1;
}
```

本题完整代码文章来源地址https://www.toymoban.com/news/detail-422938.html

#include <iostream>
using namespace std;
const int N = 1e7+10, mod = 1e9+7;
typedef long long ll;

ll res[N];

int main()
{
    int n;
    cin >> n;
    
    res[0] = 1;
    ll sum = 0;
    for(int i = 1, j = -2 ; i <= n ; ++i, ++j){
        res[i] = res[i-1];
        if(i >= 2) res[i] += res[i-2], res[i] %= mod;
        if(j >= 0) sum += res[j], sum %= mod;
        res[i] += sum << 1, res[i] %= mod;
    }
    cout << res[n] << endl;
    return 0;
}