B4345 [语言月赛 202506] 卷积画图题解

Source & Knowledge

2025 年 6 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定一个

n \times m

的二维数组（画布）和一个

k \times k

的二维数组（模板）。我们需要对画布执行“卷积”操作：将模板放置在画布的左上角，然后逐步向右、向下移动。在每个位置，将模板与画布上对应区域的元素相乘并求和，得到新的值，从而形成一个大小为

(n - k + 1) \times (m - k + 1)

的新画布。请输出这个卷积后的新画布。

题目分析

卷积操作涉及到三个嵌套的循环：两个外层循环控制模板在画布上的移动位置，两个内层循环计算当前位置的卷积结果。

根据题目描述，卷积操作的定义是：将模板的每个元素与画布上对应位置的元素相乘，然后将所有乘积相加。这个操作会针对画布上所有能够完整覆盖模板的区域进行。我们可以设计四层嵌套循环来完成计算：

外层两层循环：用于遍历卷积结果矩阵 $C$ 的每个位置 $(i', j')$ 。
- for i' from 1 to n - k + 1: 遍历结果的行。
- for j' from 1 to m - k + 1: 遍历结果的列。
内层两层循环：用于计算当前结果位置 $C_{i', j'}$ 的值。
- for x from 1 to k: 遍历模板的行。
- for y from 1 to k: 遍历模板的列。

在最内层，我们将 a[i' + x - 1][j' + y - 1] （画布中对应位置的元素）与 b[x][y] （模板中的元素）相乘，并累加到当前位置的卷积结果中。

CPP

// 遍历卷积结果的行
for (int ii = 1; ii <= n - k + 1; ++ii) {
    // 遍历卷积结果的列
    for (int jj = 1; jj <= m - k + 1; ++jj) {
        long long sum = 0; // 初始化当前位置的卷积和
        
        // 遍历模板的每个元素
        for (int x = 1; x <= k; ++x) {
            for (int y = 1; y <= k; ++y) {
                // 将画布上对应区域的元素与模板元素相乘并累加
                sum += huabu[ii + x - 1][jj + y - 1] * muban[x][y];
            }
        }
        cout << sum << " "; // 输出当前卷积结果
    }
    cout << endl; // 每行结束后换行
}

特别的，题目中指出，所有输入数据中的整数都在

1

到

10^7

之间。

k

最大为

100

。一个卷积结果的最大值可能为

k \times k \times 10^7 \times 10^7 = 100 \times 100 \times 10^7 \times 10^7 = 10^4 \times 10^{14} = 10^{18}

。这个值会超过 int 的最大范围，因此需要使用 long long 类型来存储卷积结果。

B4345 [语言月赛 202506] 卷积画图题解

文章操作

Source & Knowledge

题目大意

题目分析

相关推荐

评论

B4345 [语言月赛 202506] 卷积画图题解