CCF-CSP认证考试 202406-1 矩阵重塑（其一） 100分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

---

原题链接： 202406-1 矩阵重塑（其一）

时间限制： 1.0 秒
空间限制： 512 MiB

题目背景

矩阵（二维）的重塑（reshape）操作是指改变矩阵的行数和列数，同时保持矩阵中元素的总数不变。

题目描述

矩阵的重塑操作可以具体定义为以下步骤：

设原矩阵为 $\mathbf{M}$，其维度为 $n\times m$，即有 $n$ 行和 $m$ 列。新矩阵为 ${\mathbf{M}}^{\prime }$，其维度为 $p\times q$。重塑操作要满足 $n\times m=p\times q$，这保证了元素的总数不变。

1. 线性化原矩阵：按照行优先的顺序，将原矩阵 $\mathbf{M}$ 的元素转换成一个长度为 $n\times m$ 的一维数组 $\mathbf{A}$。这意味着你先读取 $\mathbf{M}$ 的第 $0$ 行元素，然后是第 $1$ 行，依此类推，直到最后一行。

2. 填充新矩阵：使用一维数组 $\mathbf{A}$ 中的元素按照行优先的顺序填充新矩阵 ${\mathbf{M}}^{\prime }$。首先填充 ${\mathbf{M}}^{\prime }$ 的第 $0$ 行，直到该行有 $q$ 个元素，然后继续填充第 $1$ 行，直到所有 $p$ 行都被填满。

给定原矩阵中的一个元素的位置 $(i,j)$（$0\le i<n$ 且 $0\le j<m$），我们可以找到这个元素在被线性化后的一维数组 $\mathbf{A}$ 中的位置 $k$（$0\le k<n\times m$），然后确定它在新矩阵 ${\mathbf{M}}^{\prime }$ 中的位置 $(i^{\prime },j^{\prime })$（$0\le i^{\prime }<p$ 且 $0\le j<q$）。它们之间满足如下数学关系： $$i\times m+j=k=i^{\prime }\times q+j^{\prime }$$

给定 $n\times m$ 的矩阵 $\mathbf{M}$ 和目标形状 $p$、$q$，试将 $\mathbf{M}$ 重塑为 $p\times q$ 的矩阵 ${\mathbf{M}}^{\prime }$。

输入格式

从标准输入读入数据。

输入共 $n+1$ 行。

输入的第一行包含四个正整数 $n$、$m$ 和 $p$、$q$。

接下来依次输入原矩阵 $\mathbf{M}$ 的第 $0$ 到第 $n-1$ 行，每行包含 $m$ 个整数，按列下标从 $0$ 到 $m-1$ 的顺序依次给出。

输出格式

输出到标准输出。

输出共 $p$ 行，每行 $q$ 个整数，表示重塑后的矩阵 ${\mathbf{M}}^{\prime }$。输出格式与输入相同，即依次输出 ${\mathbf{M}}^{\prime }$ 的第 $0$ 行到第 $p-1$ 行；行内按列下标从 $0$ 到 $q-1$ 的顺序输出，且两个整数间仅用一个空格分隔。

样例1输入

2 3 3 2
1 2 3
4 5 6

样例1输出

1 2
3 4
5 6

样例2输入

2 2 1 4
6 6
6 6

样例2输出

6 6 6 6

子任务

全部的测试数据满足：

• $n$、$m$ 和 $p$、$q$ 均为正整数且 $n\times m=p\times q\le 10^4$；

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

提示

评测环境仅提供各语言的标准库，特别地，不提供任何线性代数库（如 numpy、pytorch 等）。

---

题解

待补

时间复杂度：$\mathcal{O}(nm)$。

参考代码（3ms，3944KB）

/*
    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 ""
#else
    #define dbg(...) void(0)
#endif

const 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, p, q;

void work() {
    cin >> n >> m >> p >> q;
    for (int i = 0; i < n * m; i++) cin >> a[i];
    for (int i = 0; i < p * q; i++) cout << a[i] << " \n"[i % q == q - 1];
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明：

1. 代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。
2. #pragma ... 是用来开启 O2、O3 等优化加快代码速度。
3. 中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。
4. "" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。
5. ios::sync_with_stdio(false); (0); (0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。
6. 将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。