B3991 [语言月赛 202406] 数组交换 题解

· · 题解

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

视频讲解