「春季测试 2023」涂色游戏 题解

题目大意

有一个 $n \times m$ 的网格，初始全为白色（颜色0）。进行 $q$ 次操作，每次操作要么将一整行涂成某种颜色，要么将一整列涂成某种颜色。后续操作会覆盖之前操作的效果。求所有操作完成后网格中每个格子的颜色。

解题思路

核心算法：时间戳比较法

该解法使用时间戳来记录每个行和列的最后一次操作，通过比较时间戳来决定每个格子的最终颜色。

关键数据结构

int cl[N], il[N];  // cl[i]: 第i行的最终颜色, il[i]: 第i行的最后操作时间
int cr[N], ir[N];  // cr[j]: 第j列的最终颜色, ir[j]: 第j列的最后操作时间

算法流程

1. 初始化

memset(cl, 0, sizeof cl);
memset(il, 0, sizeof il);
memset(cr, 0, sizeof cr);
memset(ir, 0, sizeof ir);

• 初始化所有行和列的颜色为0（白色）
• 初始化所有行和列的操作时间为0（表示未被操作过）

2. 处理操作序列

for (int i = 1, opt, x, c; i <= q; ++i) {
    cin >> opt >> x >> c;
    if (!opt)
        cl[x] = c, il[x] = i;  // 行操作，记录颜色和时间
    else
        cr[x] = c, ir[x] = i;  // 列操作，记录颜色和时间
}

• 使用操作序号 i 作为时间戳
• 后续操作会覆盖之前操作的颜色和时间

3. 确定每个格子的颜色

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        cout << (il[i] < ir[j] ? cr[j] : cl[i]);
        // 如果行的操作时间 < 列的操作时间，使用列的颜色，否则使用行的颜色
    }
}

算法正确性证明

关键观察

对于格子 $(i, j)$：

• 如果最后一次影响它的是行操作，那么颜色为 cl[i]
• 如果最后一次影响它的是列操作，那么颜色为 cr[j]
• 通过比较操作时间 il[i] 和 ir[j] 可以确定哪个操作更晚

为什么这样比较？

• il[i] < ir[j] 表示列操作更晚，所以使用列颜色
• 否则表示行操作更晚或同时（实际上不会同时），使用行颜色

复杂度分析

• 时间复杂度：$O(n \times m + q)$
  • 处理操作：$O(q)$
  • 输出结果：$O(n \times m)$
• 空间复杂度：$O(n + m)$

样例验证

样例1第一组数据：

操作序列（时间戳从1开始）：
1: 列5涂1 → ir[5]=1, cr[5]=1
2: 行4涂0 → il[4]=2, cl[4]=0
3: 列4涂1 → ir[4]=3, cr[4]=1
4: 行3涂0 → il[3]=4, cl[3]=0
5: 列3涂1 → ir[3]=5, cr[3]=1
6: 行2涂0 → il[2]=6, cl[2]=0
7: 列2涂1 → ir[2]=7, cr[2]=1
8: 行1涂0 → il[1]=8, cl[1]=0
9: 列1涂1 → ir[1]=9, cr[1]=1

格子(1,1): il[1]=8 < ir[1]=9 → 使用cr[1]=1
格子(1,2): il[1]=8 > ir[2]=7 → 使用cl[1]=0
...

代码亮点

1. 简洁高效：算法思想简单，代码实现简洁
2. 时间戳技巧：利用操作序号自然作为时间戳
3. 空间优化：只存储行和列的信息，不存储整个网格
4. 覆盖处理：后续操作自动覆盖前面操作

注意事项

1. 多组数据清空：每组数据开始前需要清空数组
2. 输出格式：注意空格和换行符的位置
3. 边界情况：当行列都未被操作时，颜色为初始值0

总结

这个解法通过巧妙的时间戳比较，将复杂的覆盖关系转化为简单的时间比较问题。核心在于：

1. 问题转化：将网格涂色问题转化为时间比较问题
2. 状态记录：记录每个行和列的最后操作状态
3. 高效计算：通过 $O(1)$ 的时间比较确定每个格子的颜色

该算法能够高效处理 $n, m \leq 10^5$，$q \leq 10^5$ 的大规模数据，是一个优秀而实用的解决方案。