CSP202406B - 矩阵重塑（其二）

2026/9/4· Soln

CSP认证模拟

题目描述

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

重塑操作 $p,q$ ：将当前矩阵重塑为 $p\times q$ 的形状；
转置操作：将当前矩阵转置；
元素查询 $i,j$ ：查询当前矩阵第 $i$ 行第 $j$ 列的元素，其中

$0\le i<n,\qquad 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

输入

输出

2
6

样例 2

输入

输出

3
2
5

样例解释

初始矩阵为：

$\left[\begin{array}{cc}1&2\cr3&4\cr5&6\end{array}\right]$

此时 $(1,0)$ 位置的元素为 $3$ 。

转置后矩阵为：

$\left[\begin{array}{ccc}1&3&5\cr2&4&6\end{array}\right]$

此时 $(1,0)$ 位置的元素为 $2$ 。

随后将矩阵重塑为 $3\times2$ ：

$\left[\begin{array}{cc}1&3\cr5&2\cr4&6\end{array}\right]$

此时 $(1,0)$ 位置的元素为 $5$ 。

子任务

$80%$ 的测试数据满足：

$t\le100$

全部测试数据满足：

$t\le10^5$ ；
其中转置操作的次数不超过 $100$ ；
$n,m$ 以及所有重塑操作中的 $p,q$ 均为正整数；
始终满足：

$n\times m=p\times q\le10^4$

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

提示

对于一个 $n\times m$ 的矩阵，虽然转置操作和重塑操作都可能将矩阵形态变成 $m\times n$ ，但两种操作得到的矩阵通常不同。

评测环境仅提供各语言标准库，不提供 numpy、pytorch 等线性代数库。

题解

模拟做法

我的做法是根据题意去做对应的模拟写法，过程直观简单：

读入输入的矩阵和各操作
写好各个操作的函数（依题意进行模拟）

需要注意转置和重塑操作的区别，不能简单地把转置操作认为是重塑操作的一种特殊情形。
代码如下：

#include <iostream>
#include <vector>

using namespace std;

int n, m, t;

// n * m = p * q
vector<vector<int>> reset(const vector<vector<int>>& m, const int& p, const int& q) {
    int idx = 0;
    vector<vector<int>> res(p, vector<int>(q));
    
    for(const vector<int>& r : m) {
        for(const int& e : r) {
            res[idx / q][idx % q] = e;
            idx ++;
        }
    }
    
    return res;
}

vector<vector<int>> transpose(const vector<vector<int>>& m) {
    vector<vector<int>> res(m[0].size(), vector<int>(m.size()));
    
    for (int i = 0; i < m.size(); i++) {
        for (int j = 0; j < m[0].size(); j++) {
            res[j][i] = m[i][j];
        }
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m >> t;
    
    vector<vector<int>> matrix(n, vector<int>(m));
    
    // read matrix
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < m; j ++) {
            cin >> matrix[i][j];
        } 
    }
    
    // operate
    for(int k = 0; k < t; k ++) {
        int op, p, q;
        cin >> op >> p >> q;
        
        if(op == 1) {
            matrix = reset(matrix, p, q);
            n = p;
            m = q;
        }
        
        else if(op == 2) {
            matrix = transpose(matrix);
            swap(n, m);
        }
        
        else if(op == 3) cout << matrix[p][q] << endl;
    }
    
    return 0;
}

这样做应该刚好 80 分，剩下的点会超时，也是刚好踩在命题人的设计点上了。

正解

需要注意题目条件中的范围和暗示：

$80\%$ 的测试数据满足：

$t\le100$

全部测试数据满足：

$t\le10^5$ ；

其中转置操作的次数不超过 $100$ ；

$n,m$ 以及所有重塑操作中的 $p,q$ 均为正整数；

始终满足：

$n\times m=p\times q\le10^4$

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

根据题目给出的数据范围，可知 $t \le 10^5$ ，矩阵元素数的数量级为 $10^4$ ，考虑最坏情况，每次操作都遍历所有的矩阵元素，那么总复杂度将会达到 $10^9$ 的数量级，这明显会超时。

再者，出题人特地提到转置操作的次数不超过 $100$ ，说明仅针对转置操作来说，对转置操作的要求是放宽了的。换句话说：

重塑与查询操作不能是 $O(n \times m)$ 的，而转置操作可以允许 $O(n \times m)$ 。

因此这里需要考虑对重塑操作进行优化。注意到重塑操作与转置操作的不同了吗，重塑操作实际上并没有改变矩阵元素的层次顺序，即若将矩阵元素排列为一维顺序，那么重塑前后对这些一维元素的顺序没有影响。

因此，使用数组来存储矩阵元素即可。给出代码如下：

#include <iostream>
#include <vector>

using namespace std;

int n, m, t;

vector<int> transpose(const vector<int>& mtx) {
    vector<int> res(n * m);
    
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < m; j ++) {
            // n * m \to m * n
            res[j * n + i] = mtx[i * m + j];
        }
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m >> t;
    
    vector<int> matrix(n * m);
    
    // read matrix
    for(int i = 0; i < n * m; i ++)
        cin >> matrix[i];
        
    // operate
    for(int k = 0; k < t; k ++) {
        int op, p, q;
        cin >> op >> p >> q;
        
        if(op == 1) {
            // reset
            n = p;
            m = q;
        }
        
        else if(op == 2) {
            matrix = transpose(matrix);
            swap(n, m);
        }
        
        else if(op == 3) cout << matrix[p * m + q] << endl;
    }
    
    return 0;
}

上述操作中，重塑和查询操作的复杂度均为 $O(1)$ ，转置操作的复杂度为 $O(n \times m)$ 。

cicada@blog:~

$ cat ../prev→CSP202403B - 相似度计算 $ cat ../next→CSP202409B - 字符串变换

本作品采用 CC BY-NC-SA 4.0 许可协议

转载或引用请注明出处