矩阵重塑（其二）

GitHub跳转原题关系图 Canvas 关系图返回列表

用一维行优先序列保存矩阵，重塑只修改形状，转置时按下标映射重排，查询直接定位线性下标。

OJ: shumeng

题目 ID: CSP202406B

难度:普及-

标签:模拟矩阵下标映射

日期: 2026-07-31 16:21

形式化题目

给定一个初始 $n \times m$ 矩阵，支持三类操作：

重塑为 $x \times y$ ：按行优先顺序重排为新的行列形状；
转置：交换行和列；
查询 $(x, y)$ ：输出该位置的元素。

所有操作都保持元素总数不变，且操作保证合法。

思路

关键区分：重塑不改变行优先线性序列，只改形状；转置才真正改变行优先序列。

朴素做法：直接维护二维矩阵

先看直观实现，直接用二维数组保存矩阵，每次操作都显式地在二维下标间搬运元素。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，直接维护二维矩阵完成重塑、转置与查询。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int matrix[MAXN][MAXN]; // 直接保存二维矩阵
int n, m;

// 重塑为 x 行 y 列：先按行优先取出所有元素，再按新形状放回
void reshape(int x, int y) {
    int temp[MAXN];
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) temp[count++] = matrix[i][j];
    }
    count = 0;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) matrix[i][j] = temp[count++];
    }
    n = x;
    m = y;
}

// 转置：新矩阵的 (j,i) 位置放原矩阵的 (i,j)
void transpose() {
    int temp[MAXN]; // 平铺存放转置后的元素
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            temp[j * n + i] = matrix[i][j];
        }
    }
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) matrix[i][j] = temp[count++];
    }
    swap(n, m);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int operation_count;
    cin >> n >> m >> operation_count;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cin >> matrix[i][j];
    }

    while (operation_count--) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) {
            reshape(x, y);
        } else if (type == 2) {
            transpose();
        } else {
            cout << matrix[x][y] << '\n';
        }
    }

    return 0;
}

主解：一维序列 + 下标映射

用一维数组 value 按行优先顺序保存所有元素，同时维护当前行列数 $n, m$ 。

重塑：只修改 $n, m$ ，数组不动， $O(1)$ 。
查询：位置 $(x, y)$ 的线性下标是 $x \times m + y$ ，直接输出。
转置：原位置 $(i, j)$ 线性下标 $i \times m + j$ ，转置后变为 $(j, i)$ ，新线性下标 $j \times n + i$ 。扫描一遍数组按新下标重排，并交换 $n, m$ 。

由于元素总数不超过 $10^4$ 且转置次数不超过 $100$ ，每次转置线性扫描一次完全可行。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int value[MAXN]; // 行优先保存的矩阵元素
int n, m;        // 当前矩阵的行数与列数

// 矩阵转置：原位置 (i,j) 的线性下标 i*m+j，转置后位置 (j,i) 的线性下标 j*n+i
void transpose() {
    int temp[MAXN];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            temp[j * n + i] = value[i * m + j];
        }
    }
    for (int i = 0; i < n * m; i++) value[i] = temp[i];
    swap(n, m);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int operation_count;
    cin >> n >> m >> operation_count;
    for (int i = 0; i < n * m; i++) cin >> value[i];

    while (operation_count--) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) {
            n = x; // 重塑：只改形状，行优先序列不变
            m = y;
        } else if (type == 2) {
            transpose(); // 转置：需要重排元素并交换行列
        } else {
            cout << value[x * m + y] << '\n';
        }
    }

    return 0;
}

复杂度

设矩阵元素总数为 $N = nm$ 。

时间：初始读入 $O(N)$ ；转置 $O(N)$ ；重塑与查询 $O(1)$ 。转置最多 $100$ 次，总时间复杂度 $O(N + 100N + t)$ 。
空间：一维数组保存全部元素，空间复杂度 $O(N)$ 。

总结

把“形状变化”和“元素重排”分开处理就不会混淆：重塑只是换一种方式解释同一串数据，转置才需要真正的下标重排。用一维行优先序列配合 $i \times m + j$ 的线性下标公式，三类操作都能高效实现。

题目来自第 34 次 CSP 认证 T2，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

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

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

\mathbf{A} = \begin{bmatrix} a & b & c \\ d & e & f \end{bmatrix}

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

\mathbf{A}^T = \begin{bmatrix} a & d \\ b & e \\ c & f \end{bmatrix}

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

题目描述

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

重塑操作 $p,q$ ：将当前矩阵重塑为 $p \times q$ 的形状（重塑的具体定义见上一题）；
转置操作：将当前矩阵转置；
元素查询 $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$

输出格式

输出到标准输出。

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

input1

output1

1
22
6

input2

output2

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

转置后： $\begin{bmatrix} 1 & 3 & 5\\ 2 & 4 & 6 \end{bmatrix}$ ， $(1, 0)$ 位置元素为 $2$ ；

重塑后： $\begin{bmatrix} 1 & 3\\ 5 & 2\\ 4 & 6 \end{bmatrix}$ ， $(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 等）。