北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 18 题

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

别被‘图论’的标签带偏了，这题本质是递推计数。先想：第 i 格填黑时，第 i-1 格必须白；填白时，第 i-1 格可黑可白。把‘以白结尾的方案数’和‘以黑结尾的方案数’分开记，就能一步步推。

最容易掉进的坑是：看到‘方格染色’就下意识用排列组合，或者把‘不相邻’理解成‘间隔至少一个白’，导致多算或少算；还有人会把黑格数当成变量去分类讨论，反而把简单的递推搞复杂了。

这道题考查的是递推计数（动态规划）的基础思想。题目要求在一个 1×8 的方格中填黑、白两色，且任意两个黑格不能相邻。虽然题干没明说，但这类‘不相邻’的染色问题，核心就是把状态拆清楚：每一格填完后，下一格的选择只取决于上一格的颜色。因此，我们定义两个量：f[i] 表示前 i 格填完且第 i 格是白色的方案数，g[i] 表示前 i 格填完且第 i 格是黑色的方案数。这样拆分后，转移关系就一目了然了：如果第 i 格是白色，第 i-1 格无论是黑是白都可以，所以 f[i] = f[i-1] + g[i-1]；如果第 i 格是黑色，第 i-1 格必须是白色，所以 g[i] = f[i-1]。初始条件很简单：第一格填白有 1 种，填黑也有 1 种，即 f[1]=1, g[1]=1。然后从 i=2 到 8 依次递推，最后答案就是 f[8] + g[8]。

按这个思路手算一遍：f[1]=1, g[1]=1；f[2]=2, g[2]=1；f[3]=3, g[3]=2；f[4]=5, g[4]=3；f[5]=8, g[5]=5；f[6]=13, g[6]=8；f[7]=21, g[7]=13；f[8]=34, g[8]=21。加起来 34+21=55，正好对应选项 A。

命题人爱在这里挖坑：一是用‘图论’‘最短路径’等术语把学生引向错误的思路，其实本题与图无关，纯粹是线性递推；二是让学生误以为黑格数量会影响结果，实际上只要保证不相邻，黑格数自然由递推决定，不需要额外分类。避坑的关键就是抓住‘状态拆分’这个核心：把‘以白结尾’和‘以黑结尾’分开记，转移就自然出来了。

从考频趋势看，递推计数在近年 CSP-J/S 和 GESP 中属于高频考点，尤其喜欢结合‘不相邻’‘不连续’等限制条件出现，比如 2022 年某省赛就有类似 1×n 方格填色题，2023 年这道题就是典型延续。这类题往往不需要复杂算法，重在建模和递推关系的正确拆分。

未来预测方面，基于现有数据，递推计数仍将是必考方向，命题人可能会在 1×n 基础上增加‘至少 k 个黑格’或‘黑格不能相邻且不能隔 1 个白’等更复杂的约束，但核心依然是状态拆分与递推。暂无足够依据预测具体变体形式，但复习时应重点掌握‘不相邻’‘不连续’等限制下的递推建模方法。