P9117 [春季测试 2023] 涂色游戏 题解

andyli · 2023-03-09 17:49:12 · 题解

对于每行和每列，分别记录这一整行/列上一次被修改为的值以及修改的时间。最终对于每个数，它对应行和对应列中修改时间靠后的那一行/列的值便是他的值。

int main() {
    multipleTests([&]() {
        dR(int, n, m, q);
        std::vector<int> a(n), b(m), t0(n), t1(m);
        for (int i = 1; i <= q; i++) {
            dR(int, op, x, c), x--;
            if (op == 0)
                a[x] = c, t0[x] = i; // 修改这行的值及时间戳
            else
                b[x] = c, t1[x] = i; // 修改这列的值及时间戳
        }
        for (int i = 0; i < n; i++, writeln())
            for (int j = 0; j < m; j++)
                if (t0[i] > t1[j]) // 比较修改时间
                    io.write(a[i], ' ');
                else
                    io.write(b[j], ' ');
    });
    return 0;
}

你也可以只用两个 unsigned long long 数组，前半部分存时间，后半部分存值，输出时强制转换成 unsigned 可以取值，比较大小可以直接比较。

加上一些快读和快写优化跑到了最优解（官方数据 207ms）。

int main() {
    dR(unsigned, t);
    while (t--) {
        dR(unsigned, n, m, q);
        std::vector<u64> a(n), b(m);
        for (unsigned i = 1; i <= q; i++) {
            dR(unsigned, op, x, c), x--;
            if (op == 0)
                a[x] = (u64(i) << 32) + c;
            else
                b[x] = (u64(i) << 32) + c;
        }
        for (unsigned i = 0; i < n; i++, writeln())
            for (unsigned j = 0; j < m; j++)
                if (a[i] > b[j])
                    io.write(unsigned(a[i]), ' ');
                else
                    io.write(unsigned(b[j]), ' ');
    }
    return 0;
}