#2315. L 型覆盖
L 型覆盖
L 型覆盖
题目描述
CCF NOI 2024 四川省代表队评测活动 第二试 L 型覆盖(cover) L 型覆盖(cover) 【题目描述】 有一个 𝑛 列 𝑚 行的网格,左上角坐标为 (0, 0),右下角为 (𝑛, 𝑚)。现用两种 L 型去覆盖 所有边,要求每条边都被一个 L 型覆盖一次,且每条边只能被一个 L 型覆盖,并输出一种覆 盖方案。两种 L 型分别为两边长 1 + 1 的和两边长 1 + 2 的(详细形状见图 1)。此外,你需 要使用最少的数量的 L 型。 【输入格式】 从文件 cover.in 中读入数据。 输入的第一行包含一个整数 𝑇,表示数据组数。 接下来 𝑇 行,每行两个整数 𝑛, 𝑚,表示网格大小。 【输出格式】 输出到文件 cover.out 中。 对于每组数据,第一行输出使用的 L 型个数 𝑘。 接下来 𝑘 行,每行输出一个 L 型。一个 L 型用三个整数 𝑥, 𝑦, 𝑡 表示,𝑥, 𝑦 表示 L 型两条 边的交点,𝑡 表示 L 型的编号。具体如图 1 所示。其中蓝色数字表示数字上方 L 型的编号。 图 1: 每种 L 型与其编号 【样例输入】 第8 页 共11 页
CCF NOI 2024 四川省代表队评测活动 第二试 L 型覆盖(cover) 1 2 2 2 2 3 2 3 【样例输出】 1 4 2 2 2 8 3 1 2 8 4 0 1 1 5 0 0 1 6 6 7 1 3 6 8 0 2 1 9 2 3 8 10 2 1 7 11 1 0 2 12 0 0 2 【样例解释】 样例中第一组数据的覆盖方案如图 2。其中使用了 4 个 L 型。 图 2: 样例第一组数据的覆盖方案 样例中第二组数据的覆盖方案如图 3。其中使用了 6 个 L 型。 第9 页 共11 页
CCF NOI 2024 四川省代表队评测活动 第二试 L 型覆盖(cover) 图 3: 样例第二组数据的覆盖方案 【数据范围】 对于所有测试数据保证:1 ≤𝑛× 𝑚≤105,∑𝑛× 𝑚≤5 × 105。 测试点编号 min(𝑛, 𝑚) max(𝑛, 𝑚) 1 = 1 ≤500 2 ≤105 3 = 2 ≤500 4 ∼5 ≤105 6 = 3 ≤500 7 ∼8 ≤105 9 ∼10 ≤105 ≤9 11 ∼12 ≤16 13 ∼16 ≥4 ≤105 17 ∼20 ≤105 【部分分】 本题有部分分。对于一个测试点的所有数据,输出的方案均合法,且使用了最小数量的 L 型,即可获得该测试点 100% 的得分;如果输出的方案均合法,但存在某些数据未使用最小数 量的 L 型,可获得该测试点 20% 的得分;如果存在输出方案不合法,则此测试点不得分。 第10 页 共11 页
CCF NOI 2024 四川省代表队评测活动 第二试 L 型覆盖(cover) 【注意事项】 选手目录中 cover/check.cpp 可以检查你的输出是否正确,并同时输出使用了多少 L 型。你可以使用如下命令编译检查程序。 1 g++ ‐std=c++14 ‐O2 ‐o check check.cpp 并在 Linux 下使用如下命令检查你的输出。 1 ./check <input‐file> <output‐file> 或在 Windows 下使用如下命令检查你的输出。 1 check.exe <input‐file> <output‐file> 其中 <output‐file> 是你的输出,<input‐file> 是你的输出对应的输入。 程序会将检查日志输出到标准输出,对于输入的每组测试点输出一行日志。日志有如下三 个等级: • CRITICAL:表示检查程序遇到了无法恢复的错误,如运行参数错误,无法打开输入输 出文件等。输出这类日志后,检查程序将立刻停止运行。 • ERROR:表示输出的覆盖方案不合法,检查程序会同时输出错误原因,但这不会结束检 查程序。 • INFO:表示输出的覆盖方案合法,检查程序会同时输出使用的 L 型个数。 第11 页 共11 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2
2 2
2 3
4
2 2 8
1 2 8
0 1 1
0 0 1
6
1 3 6
0 2 1
2 3 8
2 1 7
1 0 2
0 0 2