B3977 [语言月赛 202405] 更好的交换 题解

· · 题解

Source & Knowledge

2024 年 5 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定一个 n \times n 的方阵，每次操作交换某两行或某两列，求最终方阵。

题目分析

首先有一个非常显然的暴力，就是直接在每次操作时暴力修改，这样单次操作就是 O(n) 的，对于本题的全部数据来说无法通过，只能拿到 60 分：

for(int i = 1, op, x, y; i <= m; i++) {
    cin >> op >> x >> y;
    if(op == 1) for(int j = 1; j <= n; j++) swap(a[x][j], a[y][j]);
    else for(int j = 1; j <= n; j++) swap(a[j][x], a[j][y]);
}

考虑如何优化。不难发现，行和列之间的修改是无关的。我们可以将行和列的操作分开处理。

现在我们假设只有行操作，没有列操作该如何处理。

实际上，我们可以不用真的去交换每一行。考虑用一个数组 p_i 来表示当前第 i 行里所存储的是初始的哪一行。那么，对于一次交换 x 行和 y 行的操作，我们只需要交换 p_x 和 p_y 即可：

if(op == 1) swap(p[x], p[y]);

同理，如果只有列操作，没有行操作，该如何处理呢？可以开一个 q_i 数组，表示当前第 i 列里存储的是初始的哪一列，然后也只需要交换 q_x 和 q_y 即可。

if(op == 0) swap(q[x], q[y]);

由于行和列的操作互不相干，所以以上两个方法可以同时进行。也就是说，我们只要用数组 p 和 q 来代替每次的修改就可以了：

for(int i = 1, op, x, y; i <= m; i++) {
    cin >> op >> x >> y;
    if(op == 1) swap(p[x], p[y]);
    else swap(q[x], q[y]);
}

接下来考虑如何输出答案。在用二重循环枚举行和列时，直接输出 a[p_i][q_j] 即可：

for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++)
        cout << a[p[i]][q[j]] << ' ';
    cout << '\n';
}

视频讲解