更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解
原题链接： 202406-2 矩阵重塑（其二）
时间限制： 1.0 秒
空间限制： 512 MiB
题目背景
矩阵转置操作是将矩阵的行和列交换的过程。在转置过程中，原矩阵 A \mathbf{A} A 的元素 a i j a_{ij} aij 会移动到转置后的矩阵 A T \mathbf{A}^T AT 的 a j i a_{ji} aji 的位置。这意味着 A \mathbf{A} A 的第 i i i 行第 j j j 列的元素在 A T \mathbf{A}^T AT 中成为了第 j j j 行第 i i i 列的元素。
例如，有矩阵 A \mathbf{A} A 如下：
A = [ a b c d e f ] \mathbf{A} = \begin{bmatrix} a & b & c \\ d & e & f \end{bmatrix} A=[adbecf]
它的转置矩阵 A T \mathbf{A}^T AT 会是：
A T = [ a d b e c f ] \mathbf{A}^T = \begin{bmatrix} a & d \\ b & e \\ c & f \end{bmatrix} AT= abcdef
矩阵转置在线性代数中是一个基本操作，广泛应用于各种数学和工程领域。
题目描述
给定 n × m n \times m n×m 的矩阵 M \mathbf{M} M，试编写程序支持以下查询和操作：
重塑操作 p p p、 q q q：将当前矩阵重塑为 p × q p \times q p×q 的形状（重塑的具体定义见上一题）；
转置操作：将当前矩阵转置；
元素查询 i i i、 j j j：查询当前矩阵第 i i i 行 j j j 列的元素（ 0 ≤ i < n 0 \le i < n 0≤i<n 且 0 ≤ j < m 0 \le j <m 0≤j<m）。
依次给出 t t t 个上述查询或操作，计算其中每个查询的结果。
输入格式
从标准输入读入数据。
输入共 n + t + 1 n + t + 1 n+t+1 行。
输入的第一行包含三个正整数 n n n、 m m m 和 t t t。
接下来依次输入初始矩阵 M \mathbf{M} M 的第 0 0 0 到第 n − 1 n - 1 n−1 行，每行包含 m m m 个整数，按列下标从 0 0 0 到 m − 1 m - 1 m−1 的顺序依次给出。
接下来输入 t t t 行，每行包含形如 op a b 的三个整数，依次给出每个查询或操作。具体输入格式如下：
重塑操作：1 p q
转置操作：2 0 0
元素查询：3 i j
输出格式
输出到标准输出。
每个查询操作输出一行，仅包含一个整数表示查询结果。
样例1输入
3 2 31 23 45 63 0 11 2 33 1 2样例1输出
26样例2输入
3 2 51 23 45 63 1 02 0 03 1 01 3 23 1 0样例2输出
325初始矩阵： [ 1 2 3 4 5 6 ] \begin{bmatrix} 1 & 2\\ 3 & 4\\ 5 & 6 \end{bmatrix} 135246 ， ( 1 , 0 ) (1, 0) (1,0) 位置元素为 3 3 3；
转置后： [ 1 3 5 2 4 6 ] \begin{bmatrix} 1 & 3 & 5\\ 2 & 4 & 6 \end{bmatrix} [123456]， ( 1 , 0 ) (1, 0) (1,0) 位置元素为 2 2 2；
重塑后： [ 1 3 5 2 4 6 ] \begin{bmatrix} 1 & 3\\ 5 & 2\\ 4 & 6 \end{bmatrix} 154326 ， ( 1 , 0 ) (1, 0) (1,0) 位置元素为 5 5 5。
子任务
80 80% 80 的测试数据满足：
t ≤ 100 t \le 100 t≤100；全部的测试数据满足：
t ≤ 1 0 5 t \le 10^{5} t≤105 且其中转置操作的次数不超过 100 100 100；
n n n、 m m m 和所有重塑操作中的 p p p、 q q q 均为正整数且 n × m = p × q ≤ 1 0 4 n \times m = p \times q \le 10^{4} n×m=p×q≤104；
输入矩阵中每个元素的绝对值不超过 1000 1000 1000。
提示
对于 n × m n \times m n×m 的矩阵，虽然转置和重塑操作都可以将矩阵形态变为 m × n m \times n m×n，但这两种操作通常会导致不同的结果。
评测环境仅提供各语言的标准库，特别地，不提供任何线性代数库（如 numpy、pytorch 等）。
题解
待补
时间复杂度： O ( t + 100 n m ) \mathcal{O}(t+100nm) O(t+100nm)。
参考代码（21ms，3912KB）
/* Created by Pujx on 2024/6/20.*/#pragma GCC optimize(2, 3, "Ofast", "inline")#include <bits/stdc++.h>using namespace std;#define endl '\n'//#define int long long//#define double long doubleusing i64 = long long;using ui64 = unsigned long long;//using i128 = __int128;#define inf (int)0x3f3f3f3f3f3f3f3f#define INF 0x3f3f3f3f3f3f3f3f#define yn(x) cout << (x ? "yes" : "no") << endl#define Yn(x) cout << (x ? "Yes" : "No") << endl#define YN(x) cout << (x ? "YES" : "NO") << endl#define mem(x, i) memset(x, i, sizeof(x))#define cinarr(a, n) for (int _ = 1; _ <= n; _++) cin >> a[_]#define cinstl(a) for (auto& _ : a) cin >> _#define coutarr(a, n) for (int _ = 1; _ <= n; _++) cout << a[_] << " \n"[_ == n]#define coutstl(a) for (const auto& _ : a) cout << _ << ' '; cout << endl#define all(x) (x).begin(), (x).end()#define md(x) (((x) % mod + mod) % mod)#define ls (s << 1)#define rs (s << 1 | 1)#define ft first#define se second#define pii pair<int, int>#ifdef DEBUG #include "debug.h"#else #define dbg(...) void(0)#endifconst int N = 2e5 + 5;//const int M = 1e5 + 5;const int mod = 998244353;//const int mod = 1e9 + 7;//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }int a[N];int n, m, t, k, q;void work() { cin >> n >> m >> t; for (int i = 0; i < n * m; i++) cin >> a[i]; while (t--) { int op, x, y; cin >> op >> x >> y; if (op == 1) n = x, m = y; else if (op == 2) { vector<int> b(a, a + n * m); swap(n, m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) a[i * m + j] = b[j * n + i]; } else cout << a[x * m + y] << endl; }}signed main() {#ifdef LOCAL freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin); freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);#endif ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int Case = 1; //cin >> Case; while (Case--) work(); return 0;}/* _____ _ _ _ __ __ | _ \ | | | | | | \ \ / / | |_| | | | | | | | \ \/ / | ___/ | | | | _ | | } { | | | |_| | | |_| | / /\ \ |_| \_____/ \_____/ /_/ \_\*/关于代码的亿点点说明：
代码的主体部分位于void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。#pragma ... 是用来开启 O2、O3 等优化加快代码速度。中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。"debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。