[POI 2021/2022 R1] Domino 题解
Domino 题解P9416 题目导航
问题分析
(虽然但是题目说的已经很清楚了，但我还是想让大家听得跟明白一点，绝对不是在水字数显得我写的很多)
给定一个 \(2 \times n\) 的网格，我们需要用 \(1 \times 2\) 或 \(2 \times 1\) 的骨牌覆盖所有未被占用的格子。要求找到最小的 \(n\)，使得存在一种占用格子的设置方式，使得覆盖方案数恰好为 \(m\)。无解输出 NIE。
核心思路
1. 无占用格子的覆盖方案数
对于一个 \(2 \times n\) 的完整网格，覆盖方案数满足斐波那契关系：
[*]\(f(0) = 1\)（大概就是空棋盘嗯对）
[*]\(f(1) = 1\)（只能竖放一个 \(2 \times 1\) 的骨牌）
[*]\(f(n) = f(n-1) + f(n-2)\)（第一列竖放，或者前两列横放两个 \(1 \times 2\) 骨牌，就是递推公式）
2. 利用占用格子分割网格
我们可以用完全被占用的列将网格分割成多个独立段，每段内部没有占用格子：
[*]总方案数 \(m\) 等于各段方案数的乘积
[*]设第 \(i\) 段长度为 \(a_i\)（即 \(2 \times a_i\) 网格），则段方案数为 \(f(a_i)\)
[*]段间需要分隔列，总列数 \(n = \sum a_i + (k-1)\)，其中 \(k\) 为段数
3. 问题转化
我们需要将 \(m\) 分解为斐波那契数的乘积：\(m = \prod f(a_i)\)，并最小化 \(n = \sum a_i + (k-1)\)。
注意：
[*]\(f(1) = 1\) 不改变乘积但增加长度，因此不考虑 \(a_i = 1\) 的段
[*]当 \(m = 1\) 时，可直接用一列全部占用的格子实现，\(n = 1\)
4. 搜索算法
由于斐波那契数增长迅速，\(m \le 10^{18}\) 时涉及的项数不多。所以我们直接通过 DFS 搜索分解方案：
[*]预处理斐波那契数列
[*]从大到小枚举斐波那契数作为因子
[*]记录当前总长度，超过已知最优解时剪枝
[*]找到分解方案后计算 \(n = \text{总长度} - 1\)（减去最后一个分隔列）
完啦！！耶！！！
算法分析
时间复杂度
[*]斐波那契数列在 \(10^{18}\) 内约 90 项
[*]DFS 搜索的分支有限，剪枝有效
[*]实际运行效率很高
空间复杂度
[*]存储斐波那契数列：\(O(\log m)\)
[*]递归深度：\(O(\log m)\)
#include using namespace std;using ll = long long;const ll INF = 9e18;ll m, best = INF;vector fib;// 搜索将剩余值分解为斐波那契数乘积的最小长度void dfs(ll remain, ll total_len, int last_idx) { if (remain == 1) { // 成功分解 best = min(best, max(total_len - 1, 0LL)); return; } if (total_len >= best) return; // 剪枝：当前长度已不够优 // 从大到小枚举可能的斐波那契因子 for (int i = last_idx; i >= 2; i--) { if (fib > remain) continue; // 剪枝：因子太大 if (remain % fib == 0) { // 可整除，尝试使用该因子 dfs(remain / fib, total_len + i + 1, i); } }}int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> m; // 特判 m = 1 if (m == 1) { cout 感谢，下载保存了 感谢分享 这个好，看起来很实用 用心讨论，共获提升！ 很好很强大我过来先占个楼 待编辑 新版吗？好像是停更了吧。 这个有用。 这个好，看起来很实用 很好很强大我过来先占个楼 待编辑 谢谢分享，试用一下 热心回复！ yyds。多谢分享 感谢，下载保存了 热心回复！ 收藏一下 不知道什么时候能用到 不错，里面软件多更新就更好了 感谢发布原创作品，程序园因你更精彩 谢谢分享，试用一下 谢谢分享，试用一下
页:
[1]
2