CCF认证202406-02 | 矩阵重塑（其二）
题目背景
矩阵转置操作是将矩阵的行和列交换的过程。在转置过程中，原矩阵 A 的元素 aij 会移动到转置后的矩阵 AT 的 aji 的位置。这意味着 A 的第 i 行第 j 列的元素在 AT 中成为了第 j 行第 i 列的元素。
例如，有矩阵 A 如下：
A=[abcdef]
它的转置矩阵 AT 会是：
AT=[adbecf]
矩阵转置在线性代数中是一个基本操作，广泛应用于各种数学和工程领域。
题目描述
给定 n×m 的矩阵 M，试编写程序支持以下查询和操作：
-
重塑操作 p、q：将当前矩阵重塑为p×q 的形状（重塑的具体定义见上一题）；
-
转置操作：将当前矩阵转置；
-
元素查询 i、j：查询当前矩阵第 i 行 j 列的元素（0≤i<n 且 0≤j<m）。
依次给出 t 个上述查询或操作，计算其中每个查询的结果。
输入格式
从标准输入读入数据。
输入共 n+t+1 行。
输入的第一行包含三个正整数 n、m 和 t。
接下来依次输入初始矩阵 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
初始矩阵： [123456]， (1,0) 位置元素为 3；
转置后： [135246]， (1,0) 位置元素为 2；
重塑后： [135246]， (1,0) 位置元素为 5。
子任务
80 的测试数据满足：
- t≤100；
全部的测试数据满足：
-
t≤105 且其中转置操作的次数不超过 100；
-
n、m 和所有重塑操作中的 p、q 均为正整数且 n×m=p×q≤104；
-
输入矩阵中每个元素的绝对值不超过 1000。
提示
-
对于 n×m 的矩阵，虽然转置和重塑操作都可以将矩阵形态变为 m×n，但这两种操作通常会导致不同的结果。
-
评测环境仅提供各语言的标准库，特别地，不提供任何线性代数库（如
numpy、pytorch等）。
题解：
观察题目，比第一题多出了一个转置的操作，和一个查询的操作就没了。
分析题目，第一题的重塑矩阵并不会改变原矩阵的数字的顺序，及将原矩阵转化成一维后，重塑的矩阵和原矩阵的一维数组相同。
而转置矩阵会改变原数组的数字的顺序，所以要处理操作。
再解决查询问题，直接从一维数组中提取第i*y+j个数字及为答案，没有时间问题。
所以这题除去输入输出，最大的时间损耗就在转置上。
对于转置问题，观察转置的特性，比如一个4*3的矩阵转置
就是在原一维数组上隔m个数取一个放入新数组，重复m次。这就解决了转置的问题。时间复杂度O（n）。
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;
int n=0,m=0,t=0,i,j,op=0,nx=0,ny=0,sum=0;
int num[10001]={0};
int newnum[10001]={0};
main()
{
cin >> n >> m >> t;
nx=n;ny=m;sum=n*m;
for(i=0;i<sum;i++){
cin >> num[i];
}
while(t>0){
cin >> op;
if(op==1){
cin >> nx >> ny;
}
else if(op==2){
cin >> n >> n;
//
n=0;
for(i=0;i<ny;i++){
for(j=i;j<sum;j+=ny){
newnum[n]=num[j];
n++;
}
}
for(i=0;i<sum;i++){
num[i]=newnum[i];
//cout << newnum[i] << " ";
}
//cout << "\n";
n=nx;nx=ny;ny=n;
//
}
else if(op==3){
cin >> n >> m;
cout << num[n*ny+m] << "\n";
}
t--;
}
}