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

· · 题解

Source & Knowledge

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

题目大意

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

题目分析

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

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

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

// 遍历卷积结果的行
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 类型来存储卷积结果。