题解：CF2195H Codeforces Heuristic Contest 001

WaTleZero_pt · 2026-02-16 09:17:05 · 题解

这种题纯纯恶心人的吧？

首先容易发现我们可以用两个直角三角形填满 2 \times 3 的矩阵，因此 n 为偶数时一定能把每个格点都覆盖。

注意到样例只给了 n=1,2 的情况，因此我们有理由猜测只有 n=1 时不能把所有格点都覆盖，其余情况都可以。

因此，我们只需要构造出 n=3 的答案，那么一定可以通过在周围填充 2 \times 3 的矩阵构造出 n 为奇数时的答案。

你可能会觉得 n=3 难以构造，事实上我也这么觉得。我首先尝试构造 3 \times 9 的矩阵，但是失败了，如果有大神这么做出来了请教教我谢谢。既然 3 \times 9 无法构造，那如果我们在某一侧额外加 3 个可用点呢（如图 1）？尝试一下（中间使用特殊的斜三角填充，边缘特殊处理）发现是可以的（如图 2）。我们再尝试分别在两侧删掉 3 个点的情况（如图 3），再尝试一下（中间仍然使用 2 \times 3 矩形填充，边缘特殊处理）也是可以的（如图 4），把图 2 复制两份与图 4 拼接（需要旋转、翻转之类的操作）n=3 就解决了（如图 5），于是这题就做完了。