[语言月赛 202401] 图像变换的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求把一张 $n$ ~n~ 行 $m$ ~m~ 列的字符画放大 $k$ ~k~ 倍：原图中的每个字符在横向与纵向上各重复 $k$ ~k~ 次，最终输出 $nk$ ~nk~ 行、每行 $mk$ ~mk~ 个字符的字符画。核心解法是按行放大——把原图一行的每个字符横向重复 $k$ ~k~ 次得到放大行，再把这一行整体纵向复制 $k$ ~k~ 次。

分析

核心观察

放大后位于第 $r$ ~r~ 行第 $c$ ~c~ 列的字符，就是原图第 $\lceil r/k \rceil$ ~\lceil r/k \rceil~ 行第 $\lceil c/k \rceil$ ~\lceil c/k \rceil~ 列的字符：原图的一个字符在新图中占据一块 $k \times k$ ~k \times k~ 的同字符方块，各字符之间的相对位置保持不变。

思路

设原图第 $i$ ~i~ 行第 $j$ ~j~ 列的字符为 $s_{i,j}$ ~s_{i,j}~，其中 $1 \le i \le n$ ~1 \le i \le n~、 $1 \le j \le m$ ~1 \le j \le m~。放大后它落在新图第 $i$ ~i~ 块、第 $j$ ~j~ 块方格内，占据的行区间与列区间分别是

$\displaystyle r \in [\,(i-1)k+1,\; ik\,], \qquad c \in [\,(j-1)k+1,\; jk\,]$

反过来，新图第 $r$ ~r~ 行第 $c$ ~c~ 列应填的字符即

$\displaystyle s_{\lceil r/k \rceil,\ \lceil c/k \rceil}$

按这个映射四重循环逐格填写是直接的朴素做法，时间与空间都是 $O(nmk^2)$ ~O(nmk^2)~，与输出规模同阶。

注意到同一行的 $k$ ~k~ 个副本完全相同，可以改成按行构造：取出原图的一行，把其中每个字符横向重复 $k$ ~k~ 次，得到长度为 $mk$ ~mk~ 的放大行，再把这一行连同换行符纵向拼接 $k$ ~k~ 次。这样只需要两层循环，代码更短，也不必显式开一个二维数组；复杂度仍为 $O(nmk^2)$ ~O(nmk^2)~，因为它已经等于输出本身的规模，无法再降低。

具体示例

以样例 $n = 4$ ~n = 4~、 $m = 3$ ~m = 3~、 $k = 2$ ~k = 2~ 为例，输出共 $nk = 8$ ~nk = 8~ 行、每行 $mk = 6$ ~mk = 6~ 个字符，总计 $48$ ~48~ 个字符。原图第 $3$ ~3~ 行是 @w@：@ 横向重复 $2$ ~2~ 次、w 也横向重复 $2$ ~2~ 次，得到放大行 @@ww@@；这一行再纵向复制 $2$ ~2~ 次，占据输出的第 $5$ ~5~ 行与第 $6$ ~6~ 行。原图第 $4$ ~4~ 行是 !!!，同理放大为 !!!!!!，占据第 $7$ ~7~ 行与第 $8$ ~8~ 行。原图第 $1$ ~1~ 行的 $3$ ~3~ 个字符彼此相同，放大后该字符在每行连续出现 $6$ ~6~ 次，并占据第 $1$ ~1~、 $2$ ~2~ 两行。

算法步骤

读入 n、m、k，再逐行读入原图的 $n$ ~n~ 行字符。
对原图的每一行，把其中第 $j$ ~j~ 个字符重复 $k$ ~k~ 次追加到放大行 row，最后在 row 末尾补一个换行符。
把 row 连续追加 $k$ ~k~ 次到输出串 out，完成这一行的纵向放大。
一次性输出 out。

复杂度分析

时间： $O(nmk^2)$ ~O(nmk^2)~，即输出字符总数 $nk \times mk$ ~nk \times mk~；读入原图的 $O(nm)$ ~O(nm)~ 被其覆盖。
空间： $O(nmk^2)$ ~O(nmk^2)~，代码把整份输出攒在一个字符串中；若改为逐行写出，空间可降到 $O(mk)$ ~O(mk)~。

实现注意事项

字符画由码值在 $33 \sim 126$ ~33 \sim 126~ 之间的可见字符组成，行内不含空格，因此按空白切分的字符串读入即可：scanf 的字符串格式、cin 读 string、Python 的 split() 都能把每一行正确读成一个字符串。
C++ 若用定长字符数组接收，数组容量至少要开到 $m + 1$ ~m + 1~，并给读入格式加上宽度限制，避免越界写。
输出的每一行末尾只有一个换行符。字符画本身不含空格，逐字符输出时天然不会产生行尾空格，不要为了对齐而补足行宽。
$k = 1$ ~k = 1~ 时输出与原图完全一致； $n = m = 1$ ~n = m = 1~ 时输出 $k$ ~k~ 行、每行 $k$ ~k~ 个相同的字符。
行数与列数都要按放大后的 $nk$ ~nk~ 与 $mk$ ~mk~ 计算，纵向重复的次数是 $k$ ~k~ 而不是 $n$ ~n~。
最大输出规模为 $nk \times mk = 1000 \times 1000 = 10^6$ 个字符，加上 $1000$ ~1000~ 个换行约 $1$ ~1~ MB，远小于内存限制；但仍应把整份结果拼好后一次性写出，避免频繁刷新缓冲区带来的开销。
纵向复制的是已经横向放大过的整行，所以输出中连续 $k$ ~k~ 行完全相同，相邻的每 $k$ ~k~ 列也完全相同。两种放大次序的结果一致，按行构造的写法不必区分先后。

源代码

#include <cstdio>
#include <string>

int main() {
    int n = 0, m = 0, k = 0;
    if (std::scanf("%d%d%d", &n, &m, &k) != 3) return 0;

    std::string out;
    out.reserve((size_t)n * k * ((size_t)m * k + 1));

    for (int i = 0; i < n; ++i) {
        char buf[128];
        if (std::scanf("%127s", buf) != 1) return 0;

        std::string row;  // 横向放大后的一整行，末尾已带换行符
        row.reserve((size_t)m * k + 1);
        for (int j = 0; j < m; ++j) row.append((size_t)k, buf[j]);
        row.push_back('\n');

        for (int t = 0; t < k; ++t) out += row;  // 纵向放大
    }

    std::fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n, m, k = int(data[0]), int(data[1]), int(data[2])

    out = []
    for i in range(n):
        s = data[3 + i].decode()
        row = "".join(ch * k for ch in s) + "\n"  # 横向放大后的一整行
        out.append(row * k)                       # 纵向放大

    sys.stdout.write("".join(out))


main()

目前没有评论。