自动搬运

查看原文

来自洛谷，原作者为

	ShiRoZeTsu AFOed

搬运于2025-08-24 21:16:19，当前版本为作者最后更新于2024-05-20 17:58:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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';
}

视频讲解