洛谷 AT_past202005_i 行列操作 の 题解

这道题最难的点在于用什么方法存储矩阵 $a$ 和一个特殊的操作方式。

要存矩阵 $a$，最先想到的是二维数组，但是二维数组开不到 $1 \le n \le 10^5$，所以可以用一个长度为 $2 \cdot n$ 的一维数组 $m$ 来存。当 $i \le n$ 时，让一维数组 $m_{i}$ 负责存第 $i$ 行的内容；而当 $n + 1 \le i \le 2 \cdot n$ 时，$m_{i}$ 负责存第 $i$ 列的内容。

由题目给出的内容公式和我们用的方法可知最终该怎么对 $m_{i}$ 赋初始值。

• $i \le n$ 时，$m_{i} = n \cdot (i - 1)$

• $n + 1 \le i \le 2 \cdot n$ 时， $m_{i} = i - 1 - n$

于是有了以下代码。

for(long long i = 1; i <= n; i++) m[i] = n * (i - 1);
for(long long i = n + 1; i <= 2 * n; i++) m[i] = i - 1 - n;

之后我们可以想一下大概思路。首先定义两个变量 $a$ 和 $b$，$a$ 初始值设定为 $0$，负责行，$b$ 初始值设定为 $n$，负责列，他们俩要担负表示行列和交换行列的重任，大概意思是第 $i$ 行被表示为 m[a + x]，第 $i$ 列则被表示为 m[b + y]，要交换的时候只要交换 $a$ 和 $b$ 即可。

大概思路已经说完了，我就直接在下面放代码了。

#include <iostream>
using namespace std;
long long n, q, m[1000001], a, b;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    cin >> n >> q;
    for(long long i = 1; i <= n; i++) m[i] = n * (i - 1);
    for(long long i = n + 1; i <= 2 * n; i++) m[i] = i - 1 - n;
    a = 0, b = n;
    for(long long i = 1; i <= q; i++){
        long long option;
        cin >> option;
        if(option == 1){
            long long x, y;
            cin >> x >> y;
            swap(m[a + x], m[a + y]);
        }
        else if(option == 2){
            long long x, y;
            cin >> x >> y;
            swap(m[b + x], m[b + y]);
        }
        else if(option == 3) swap(a, b);
        else{
            long long x, y;
            cin >> x >> y;
            long long ans = m[a + x] + m[b + y];
            cout << ans << endl;
        }
    }
    return 0;
}

记录