当前位置：首页 > article >正文

CCF-CSP第34次认证第二题——矩阵重塑（其二）【需反复思考学习！！！】

article 2025/2/13 19:57:23

第34次认证第二题——矩阵重塑（其二）

官网题目链接

时间限制： 1.0 秒

空间限制： 512 MiB

相关文件： 题目目录（样例文件）

题目背景

矩阵转置操作是将矩阵的行和列交换的过程。在转置过程中，原矩阵 𝐴A 的元素 𝑎𝑖𝑗aij 会移动到转置后的矩阵 𝐴𝑇AT 的 𝑎𝑗𝑖aji 的位置。这意味着 𝐴A 的第 𝑖i 行第 𝑗j 列的元素在 𝐴𝑇AT 中成为了第 𝑗j 行第 𝑖i 列的元素。

例如，有矩阵 𝐴A 如下：

𝐴=[𝑎𝑏𝑐𝑑𝑒𝑓]A=[adbecf]

它的转置矩阵 𝐴𝑇AT 会是：

𝐴𝑇=[𝑎𝑑𝑏𝑒𝑐𝑓]AT=abcdef

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

题目描述

给定 𝑛×𝑚n×m 的矩阵 𝑀M，试编写程序支持以下查询和操作：

重塑操作 𝑝p、𝑞q：将当前矩阵重塑为 𝑝×𝑞p×q 的形状（重塑的具体定义见上一题）；
转置操作：将当前矩阵转置；
元素查询 𝑖i、𝑗j：查询当前矩阵第 𝑖i 行 𝑗j 列的元素（0≤𝑖<𝑛0≤i<n 且 0≤𝑗<𝑚0≤j<m）。

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

输入格式

从标准输入读入数据。

输入共 𝑛+𝑡+1n+t+1 行。

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

接下来依次输入初始矩阵 𝑀M 的第 00 到第 𝑛−1n−1 行，每行包含 𝑚m 个整数，按列下标从 00 到 𝑚−1m−1 的顺序依次给出。

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

重塑操作：1 p q
转置操作：2 0 0
元素查询：3 i j

输出格式

输出到标准输出。

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

样例1输入

样例1输出

2
6

样例2输入

样例2输出

3
2
5

初始矩阵： [123456]135246， (1,0)(1,0) 位置元素为 33；

转置后： [135246][123456]， (1,0)(1,0) 位置元素为 22；

重塑后： [135246]154326， (1,0)(1,0) 位置元素为 55。

子任务

8080 的测试数据满足：

𝑡≤100t≤100；

全部的测试数据满足：

𝑡≤105t≤105 且其中转置操作的次数不超过 100100；
𝑛n、𝑚m 和所有重塑操作中的 𝑝p、𝑞q 均为正整数且 𝑛×𝑚=𝑝×𝑞≤104n×m=p×q≤104；
输入矩阵中每个元素的绝对值不超过 10001000。

提示

对于 𝑛×𝑚n×m 的矩阵，虽然转置和重塑操作都可以将矩阵形态变为 𝑚×𝑛m×n，但这两种操作通常会导致不同的结果。
评测环境仅提供各语言的标准库，特别地，不提供任何线性代数库（如 numpy、pytorch 等）。

语言和编译选项

#	名称	编译器	额外参数	代码长度限制
0	g++	`g++`	`-O2 -DONLINE_JUDGE`	65536 B
1	gcc	`gcc`	`-O2 -DONLINE_JUDGE`	65536 B
2	java	`javac`		65536 B
3	python3	`python3`		65536 B

参考题解

原始版本（可仅看优化版本）

#include<iostream>
#include<vector>
using namespace std;

 vector<vector<int> > reshape(const vector<vector<int> >& array, int newN, int newM) {
	int n = array.size();
	int m = array[0].size();
	vector<vector<int> > result(newN, vector<int>(newM));
	int index = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			result[index / newM][index % newM] = array[i][j]; //!!!!!!重点，学会这种方法，/列数为行标，%列数为列标！ 
			index++;
		}
	}
	return result; 
}

//转置 
vector<vector<int> > transpose(const vector<vector<int> >& array) {
	int n = array.size();
	int m = array[0].size();
	vector<vector<int> > result(m, vector<int>(n));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			result[j][i] = array[i][j];
		}
	}
	return result;
}

int main() {
	int n, m, t;
	cin >> n >> m >> t;
	vector<vector<int> > array(n, vector<int>(m));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> array[i][j];
		}
	}
	
	int op = 0;
	for(int i = 0; i < t; i++) {
		cin >> op;
		switch (op) {
			case 1: {
				int nn, mm;
				cin >> nn >> mm;
				array = reshape(array, nn, mm);
				break;
			}
			case 2: {
				int ignore;
				cin >> ignore >> ignore;
				array = transpose(array);
				break;
			}
			case 3: {
				int x, y;
				cin >> x >> y;
				cout << array[x][y] << endl;
				break;
			}
		}
	}
	return 0;
}

改进思路

首先需要考虑时间问题，题目给出的时间限制是1秒，而t可以达到1e5次操作，这意味着如果每次操作都直接修改矩阵的话，时间复杂度可能会很高，尤其是转置操作，如果每次转置都实际交换元素的位置，那转置次数较多的话可能会超时。考虑用某种方式记录转置的状态，而不是每次实际转置。—— 问题的关键在于如何高效地维护矩阵的当前形态，而无需每次都物理上重塑或转置矩阵（不过子任务中提到 ”转置操作的次数不超过 100“ ，也许是已经考虑了这个问题？模拟系统没开咱也不知道这个代码能不能拿满分，这里只是探讨一下优化思路）
逆向思维：不主动改变矩阵形态——修改矩阵次数过多会提高时间复杂度（见3）；根据操作逆向求对应原始坐标的位置
赋值、算术运算（加减乘除）：O(1)；矩阵存储:使用std::vector<std::vector<int>>存储矩阵，初始化一个大小为n x m的矩阵耗时约为O(n*m)，因为每个元素都需要被初始化；矩阵转置:对于一个n x m的矩阵进行转置操作，通常需要遍历整个矩阵，因此时间复杂度为O(n*m)。
可能的思路是：维护一个一维数组data【矩阵的行优先存储方式】，存储所有元素，初始时按行优先顺序填充。然后，每次转置操作会切换一个转置标志，并交换当前的行列数。重塑操作则改变当前的行列数为p和q。当需要查询元素（i,j）时，根据当前是否转置，以及当前的行列数，计算出该元素在data数组中的位置。
但是，重塑操作后的数据是按行填充的，而转置会影响数据的排列顺序。因此，如果在转置后进行重塑，可能需要调整处理方式。这种情况下，仅仅使用一个标志位可能不够，因为重塑后的数据布局依赖于当前的实际存储顺序。例如，假设原矩阵是2x3，转置后变为3x2，数据存储顺序改变。此时如果重塑为6x1，转置后的重塑应该按照转置后的数据顺序来填充，而不是原顺序。因此，转置操作必须实际改变数据的存储方式，否则重塑后的数据顺序会错误。——简而言之，重塑操作只调整当前的行列数，不改变数据，因为数据是按行存储的。转置操作则重新生成数据数组，并交换行列数。查询操作根据当前的行列数计算索引。
具体来说：对于重塑操作，设置rows和cols为p和q；对于转置操作，生成新的data数组；新的data数组的大小是 rows*cols = cols*rows。
需要注意，输入可能较大，所以需要使用快速的输入方法。例如，可以用scanf代替cin，或者关闭同步。
在转置操作中，考虑使用vector的swap方法，这样可以避免不必要的拷贝，只需交换内部指针，效率更高。

优化后的代码

#include <cstdio>
#include <vector>

using namespace std;

int main () {
	int n, m, t;
	scanf("%d%d%d", &n, &m, &t);
	
	//按行优先存储矩阵元素
	vector<int> data(n * m); //预分配空间，避免 push_back 的潜在扩容开销
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &data[i * m + j]);//对于一维二维的转换i*m+j要熟悉 
		}
	} 
	
	int current_rows = n; //当前矩阵的行数
	int current_cols = m; //当前矩阵的列数
	
	while (t--) { //像这种到0结束的直接用while更简便，不要用for循环
		int op, a, b;
		scanf("%d%d%d", &op, &a, &b);
		
		if (op == 1) {
			//重塑仅改变形状，数据顺序不变
			current_rows = a;
			current_cols = b; 
		} else if (op == 2) {
			//转置
			vector<int> transposed_data;
			transposed_data.reserve(current_rows * current_cols); //预分配内存（reserve()）减少动态扩容开销
			//转置：按新行顺序遍历旧列（对转置的本质要熟悉）
			for (int col = 0; col < current_cols; col++) { //col为外层循环，即按列存数据，先存第一列，也就实现了转置 
				for (int row = 0; row < current_rows; row++) {
					transposed_data.push_back(data[row * current_cols + col]); 
				}
			} 
			
			//交换新旧数据（使用 vector::swap() 实现 O(1) 时间的数据交换）
			data.swap(transposed_data);
			//行列数交换(使用 swap() 函数代替临时变量交换行列数)
			swap(current_rows, current_cols); 
		} else if (op == 3) {
			//直接计算行优先索引
			printf("%d\n", data[a * current_cols + b]); 
		}
	} 
	return 0;
}