NOIP 提高组初赛 · NOIP 2016 提高组初赛试题 第 21 题

一个 $1\times 8$ 的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_________种填涂方案。

这题本质是斐波那契数列的变种，拿到题先别去硬算，而是想：最左边那个格子填什么？由此拆成两种互斥情况，把大问题拆成两个小问题，递推关系就出来了。

学生最容易陷入‘分类讨论’的陷阱，比如按黑格总数分类，或者按黑格位置分类，这样组合爆炸，根本算不完。还有人会误以为只要不相邻就行，把‘黑格’当成‘空格’去算，导致序列错位。最典型的错误是算出 f(8)=89（把 f(1) 当成 1 而不是 2）或者 f(8)=34（漏掉了最左为黑的情况），这都是因为递推的初始条件没设对，或者拆分时漏了‘最左为黑则次左必白’这个关键约束。

考点概念：递推计数（不相邻问题）

这题考查的是典型的递推计数，核心思路是‘拆分’：把大问题拆成互斥的几种小情况，分别求解后相加。这里的关键约束是‘不允许两个黑格相邻’，这直接决定了递推的步长。

命题视角：为什么考这个？

命题人喜欢用这种‘看似简单实则暗藏递推’的题目来区分学生：只会暴力枚举的人会被 1×8 吓退，而能抽象出递推关系的人能轻松解决。这类题在初赛里常用来测试逻辑拆解能力，而不是单纯的计算能力。