CCF-CSP认证考试 202406-2 矩阵重塑（其二） 100分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202406-2 矩阵重塑（其二）

时间限制： 1.0 秒
空间限制： 512 MiB

题目背景

矩阵转置操作是将矩阵的行和列交换的过程。在转置过程中，原矩阵 $\mathbf{A}$ 的元素 $a_{ij}$​ 会移动到转置后的矩阵 ${\mathbf{A}}^T$ 的 $a_{ji}$​ 的位置。这意味着 $\mathbf{A}$ 的第 $i$ 行第 $j$ 列的元素在 ${\mathbf{A}}^T$ 中成为了第 $j$ 行第 $i$ 列的元素。

例如，有矩阵 $\mathbf{A}$ 如下：

$$\mathbf{A}=\left[\begin{array}{ccc}a& b& c\\ d& e& f\end{array}\right]$$

它的转置矩阵 ${\mathbf{A}}^T$ 会是：

$${\mathbf{A}}^T=\left[\begin{array}{cc}a& d\\ b& e\\ c& f\end{array}\right]$$

矩阵转置在线性代数中是一个基本操作，广泛应用于各种数学和工程领域。

题目描述

给定 $n\times m$ 的矩阵 $\mathbf{M}$，试编写程序支持以下查询和操作：

1. 重塑操作 $p$、$q$：将当前矩阵重塑为 $p\times q$ 的形状（重塑的具体定义见上一题）；

2. 转置操作：将当前矩阵转置；

3. 元素查询 $i$、$j$：查询当前矩阵第 $i$ 行 $j$ 列的元素（$0\le i<n$ 且 $0\le j<m$）。

依次给出 $t$ 个上述查询或操作，计算其中每个查询的结果。

输入格式

从标准输入读入数据。

输入共 $n+t+1$ 行。

输入的第一行包含三个正整数 $n$、$m$ 和 $t$。

接下来依次输入初始矩阵 $\mathbf{M}$ 的第 $0$ 到第 $n-1$ 行，每行包含 $m$ 个整数，按列下标从 $0$ 到 $m-1$ 的顺序依次给出。

接下来输入 $t$ 行，每行包含形如 op a b 的三个整数，依次给出每个查询或操作。具体输入格式如下：

• 重塑操作：1 p q

• 转置操作：2 0 0

• 元素查询：3 i j

输出格式

输出到标准输出。

每个查询操作输出一行，仅包含一个整数表示查询结果。

样例1输入

3 2 3
1 2
3 4
5 6
3 0 1
1 2 3
3 1 2

样例1输出

2
6

样例2输入

3 2 5
1 2
3 4
5 6
3 1 0
2 0 0
3 1 0
1 3 2
3 1 0

样例2输出

3
2
5

初始矩阵： $\left[\begin{array}{cc}1& 2\\ 3& 4\\ 5& 6\end{array}\right]$， $(1,0)$ 位置元素为 $3$；

转置后： $\left[\begin{array}{ccc}1& 3& 5\\ 2& 4& 6\end{array}\right]$， $(1,0)$ 位置元素为 $2$；

重塑后： $\left[\begin{array}{cc}1& 3\\ 5& 2\\ 4& 6\end{array}\right]$​​， $(1,0)$ 位置元素为 $5$。

子任务

$80$ 的测试数据满足：

• $t\le 100$；

全部的测试数据满足：

• $t\le 10^5$ 且其中转置操作的次数不超过 $100$；

• $n$、$m$ 和所有重塑操作中的 $p$、$q$ 均为正整数且 $n\times m=p\times q\le 10^4$；

• 输入矩阵中每个元素的绝对值不超过 $1000$。

提示

• 对于 $n\times m$ 的矩阵，虽然转置和重塑操作都可以将矩阵形态变为 $m\times n$，但这两种操作通常会导致不同的结果。

• 评测环境仅提供各语言的标准库，特别地，不提供任何线性代数库（如 numpy、pytorch 等）。

题解

待补

时间复杂度：$\mathcal{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 double
using 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 LOCALfreopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int Case = 1;//cin >> Case;while (Case--) work();return 0;
}
/*_____   _   _       _  __    __|  _  \ | | | |     | | \ \  / /| |_| | | | | |     | |  \ \/ /|  ___/ | | | |  _  | |   }  {| |     | |_| | | |_| |  / /\ \|_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明：

1. 代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。
2. #pragma ... 是用来开启 O2、O3 等优化加快代码速度。
3. 中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。
4. "debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。
5. ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。
6. 将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。