自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

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

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

以下是正文

Source & Knowledge

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

题目大意

给定一个 $n$ 行 $m$ 列的数组 $a$。操作 $q$ 次，每次交换某两行或某两列，并随时会查询数组中某个位置的值。

题目分析

本题考察点有两个，第一个是如何仅读入一位整数，第二个是思维能力。

首先对于题目的输入，对于 $a$ 数组，如果按照下面的方式来编写：

int a[1005][1005];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        cin >> a[i][j];
    }
}

那么会导致答案错误。原因是，默认情况下，cin 会将一行不带空格的数按照一个整数来处理。

对于本题而言，一种处理方法是，使用一个 char 来代替读入 $a_{i, j}$，再做转换：

int n, m, q;
int a[1005][1005];
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        char c;
        cin >> c;
        a[i][j] = c - '0';
    }
}

其次，对于题目的任务。如果每一次交换操作都去交换两行、两列中的所有元素，那么会导致时间复杂度 $O(qN)$（$N = \max(n, m)$）。虽然不会超时，但又更好的办法。

考虑使用两个数组 $r, c$。其中 $r_i$ 代表当前第 $i$ 行存放的是原来第几行的数据，$c_i$ 代表当前第 $i$ 列存放的是原来第几列的数据。初始时 $r_i = c_i = i$。

这样，在每次交换时，不去交换 $a$ 数组，而仅仅是对 $r$ 或 $c$ 做交换，即可避免超时。在中途和最终输出时，输出 $a_{r_i, c_i}$ 即可。

for (int i = 0; i < q; i++) {
    int op, x, y;
    cin >> op >> x >> y;
    if (op == 1) {
        swap(r[x], r[y]);
    } else if (op == 2) {
        swap(c[x], c[y]);
    } else {
        cout << a[r[x]][c[y]] << endl;
    }
}
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        cout << a[r[i]][c[j]];
    }
    cout << endl;
}

视频讲解