更多 CSP 認(rèn)證考試題目題解可以前往：CSP-CCF 認(rèn)證考試真題題解

---

原題鏈接： 202406-2 矩陣重塑（其二）

時(shí)間限制： 1.0 秒
空間限制： 512 MiB

題目背景

矩陣轉(zhuǎn)置操作是將矩陣的行和列交換的過(guò)程。在轉(zhuǎn)置過(guò)程中，原矩陣 $\mathbf{A}$ 的元素 $a_{ij}$? 會(huì)移動(dòng)到轉(zhuǎn)置后的矩陣 ${\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]$$

它的轉(zhuǎn)置矩陣 ${\mathbf{A}}^T$ 會(huì)是：

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

矩陣轉(zhuǎn)置在線性代數(shù)中是一個(gè)基本操作，廣泛應(yīng)用于各種數(shù)學(xué)和工程領(lǐng)域。

題目描述

給定 $n\times m$ 的矩陣 $\mathbf{M}$，試編寫程序支持以下查詢和操作：

1. 重塑操作 $p$、$q$：將當(dāng)前矩陣重塑為 $p\times q$ 的形狀（重塑的具體定義見(jiàn)上一題）；

2. 轉(zhuǎn)置操作：將當(dāng)前矩陣轉(zhuǎn)置；

3. 元素查詢 $i$、$j$：查詢當(dāng)前矩陣第 $i$ 行 $j$ 列的元素（$0\le i<n$ 且 $0\le j<m$）。

依次給出 $t$ 個(gè)上述查詢或操作，計(jì)算其中每個(gè)查詢的結(jié)果。

輸入格式

從標(biāo)準(zhǔn)輸入讀入數(shù)據(jù)。

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

輸入的第一行包含三個(gè)正整數(shù) $n$、$m$ 和 $t$。

接下來(lái)依次輸入初始矩陣 $\mathbf{M}$ 的第 $0$ 到第 $n?1$ 行，每行包含 $m$ 個(gè)整數(shù)，按列下標(biāo)從 $0$ 到 $m?1$ 的順序依次給出。

接下來(lái)輸入 $t$ 行，每行包含形如 op a b 的三個(gè)整數(shù)，依次給出每個(gè)查詢或操作。具體輸入格式如下：

• 重塑操作：1 p q

• 轉(zhuǎn)置操作：2 0 0

• 元素查詢：3 i j

輸出格式

輸出到標(biāo)準(zhǔn)輸出。

每個(gè)查詢操作輸出一行，僅包含一個(gè)整數(shù)表示查詢結(jié)果。

樣例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$；

轉(zhuǎn)置后： $\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$。

子任務(wù)

$80$ 的測(cè)試數(shù)據(jù)滿足：

• $t\le 100$；

全部的測(cè)試數(shù)據(jù)滿足：

• $t\le 10^5$ 且其中轉(zhuǎn)置操作的次數(shù)不超過(guò) $100$；

• $n$、$m$ 和所有重塑操作中的 $p$、$q$ 均為正整數(shù)且 $n\times m=p\times q\le 10^4$；

• 輸入矩陣中每個(gè)元素的絕對(duì)值不超過(guò) $1000$。

提示

• 對(duì)于 $n\times m$ 的矩陣，雖然轉(zhuǎn)置和重塑操作都可以將矩陣形態(tài)變?yōu)?$m\times n$，但這兩種操作通常會(huì)導(dǎo)致不同的結(jié)果。

• 評(píng)測(cè)環(huán)境僅提供各語(yǔ)言的標(biāo)準(zhǔn)庫(kù)，特別地，不提供任何線性代數(shù)庫(kù)（如 numpy、pytorch 等）。

---

題解

待補(bǔ)

時(shí)間復(fù)雜度：$\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;
}
/*_____   _   _       _  __    __|  _  \ | | | |     | | \ \  / /| |_| | | | | |     | |  \ \/ /|  ___/ | | | |  _  | |   }  {| |     | |_| | | |_| |  / /\ \|_|     \_____/ \_____/ /_/  \_\
*/

關(guān)于代碼的億點(diǎn)點(diǎn)說(shuō)明：

1. 代碼的主體部分位于 void work() 函數(shù)中，另外會(huì)有部分變量申明、結(jié)構(gòu)體定義、函數(shù)定義在上方。
2. #pragma ... 是用來(lái)開(kāi)啟 O2、O3 等優(yōu)化加快代碼速度。
3. 中間一大堆 #define ... 是我習(xí)慣上的一些宏定義，用來(lái)加快代碼編寫的速度。
4. "debug.h" 頭文件是我用于調(diào)試輸出的代碼，沒(méi)有這個(gè)頭文件也可以正常運(yùn)行（前提是沒(méi)定義 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途調(diào)試的輸出的語(yǔ)句，可能沒(méi)刪干凈，但是沒(méi)有提交上去沒(méi)有任何影響。
5. ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 這三句話是用于解除流同步，加快輸入 cin 輸出 cout 速度（這個(gè)輸入輸出流的速度很慢）。在小數(shù)據(jù)量無(wú)所謂，但是在比較大的讀入時(shí)建議加這句話，避免讀入輸出超時(shí)。如果記不下來(lái)可以換用 scanf 和 printf，但使用了這句話后，cin 和 scanf、cout 和 printf 不能混用。
6. 將 main 函數(shù)和 work 函數(shù)分開(kāi)寫純屬個(gè)人習(xí)慣，主要是為了多組數(shù)據(jù)。