D. X-Sum - 题解

比赛与标签

比赛: Codeforces Round 790 (Div. 4) 标签: brute force, greedy, implementation 难度: *1000

喵喵的棋盘挑战！

主人你好呀~ 这道题是关于一个有趣的棋盘问题的说！(ฅ'ω'ฅ)

题目给了我们一个 n x m 大小的棋盘，每个格子里都有一个数字。我们的任务是在棋盘上放一个主教（Bishop），主教可以攻击它所在位置的两条完整对角线上的所有格子。我们的目标是，找到一个位置放置主教，使得它能攻击到的所有格子（包括它自己所在的格子）的数字总和最大。

简单来说，就是遍历棋盘上的每一个格子，假设把主教放在这个格子上，计算出两条对角线的数字和，然后找出所有可能位置中最大的那个和，呐~

聪明的猫娘妙计喵~

如果我们用最朴素的方法，对于棋盘上的每一个格子 (i, j)，都重新去遍历一遍它的主对角线和副对角线来求和，那可太慢啦！n 和 m 最大是200，n*m 个格子，每个格子再算一遍对角线，时间复杂度会爆炸的说！(>ω<)

所以，我们需要一个更聪明的办法，喵~ 这时候，猫娘的敏锐观察力就派上用场啦！

我们来观察一下对角线有什么特点：

主对角线 (从左上到右下): 在同一条主对角线上的所有格子 (r, c)，它们的行号 r 和列号 c 的差值 r - c 都是一个定值！
副对角线 (从右上到左下): 在同一条副对角线上的所有格子 (r, c)，它们的行号 r 和列号 c 的和 r + c 也是一个定值！

有了这个发现，事情就变得简单了！我们可以提前把所有主对角线和所有副对角线的元素和都计算出来，存到两个数组里。这个过程就叫做 预处理，喵~

具体的计划是这样的：

创建两个数组，一个叫 main_diag_sums 用来存所有主对角线的和，另一个叫 anti_diag_sums 用来存所有副对角线的和。
如何索引这两个数组呢？
- 对于副对角线，i + j 的值范围是从 0 + 0 = 0 到 (n-1) + (m-1) = n+m-2，正好可以直接用作数组下标。
- 对于主对角线，i - j 的值范围是从 0 - (m-1) = -(m-1) 到 (n-1) - 0 = n-1，出现了负数！数组下标可不能是负数呀。没关系，我们给它加上一个偏移量 m-1，这样 i - j + (m-1) 的范围就变成了 0 到 n+m-2，完美解决！
我们遍历一遍整个棋盘，对于每个格子 (i, j) 的值 a[i][j]，我们把它累加到对应的对角线和数组里：
- main_diag_sums[i - j + (m-1)] += a[i][j];
- anti_diag_sums[i + j] += a[i][j];
预处理完成！现在，我们再遍历一次棋盘，来计算每个格子作为主教位置时的总攻击力。
对于格子 (i, j)，它所在的主对角线和是 main_diag_sums[i - j + (m-1)]，副对角线和是 anti_diag_sums[i + j]。
注意一个关键点！ 格子 (i, j) 本身既属于主对角线，又属于副对角线。所以，如果我们直接把两个和加起来，a[i][j] 的值就被加了两次！题目要求每个格子只算一次，所以我们要减掉一次多余的 a[i][j]。
所以，在 (i, j) 位置的总和就是 main_diag_sums[i - j + (m-1)] + anti_diag_sums[i + j] - a[i][j]。
我们只需要在遍历的时候，不断更新找到的最大总和 max_sum 就好啦！

这样一来，我们只需要遍历两次棋盘，非常高效，一定能AC的！加油，喵~

代码魔法时间！

cpp

#include <iostream>
#include <vector>
#include <algorithm>

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> a(n, std::vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    }

    // 预处理所有对角线的和，喵~
    // 一共有 n + m - 1 条主对角线和 n + m - 1 条副对角线。
    std::vector<long long> main_diag_sums(n + m - 1, 0);
    std::vector<long long> anti_diag_sums(n + m - 1, 0);

    // 对于主对角线，所有格子 (i, j) 的 i - j 值相同。
    // i - j 的范围是 [-(m-1), n-1]。
    // 我们加上 (m-1) 的偏移量，让索引变成非负的 [0, n+m-2]。
    // 对于副对角线，所有格子 (i, j) 的 i + j 值相同。
    // i + j 的范围是 [0, n+m-2]，可以直接用作索引。
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            main_diag_sums[i - j + (m - 1)] += a[i][j];
            anti_diag_sums[i + j] += a[i][j];
        }
    }

    long long max_sum = 0;
    // 遍历所有可能的主教位置，寻找最大和。
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            // 对于 (i, j) 位置的主教，它的攻击总和 = 所在主对角线和 + 所在副对角线和。
            // 但是，格子 (i, j) 本身被计算了两次（一次在主对角线，一次在副对角线）。
            // 所以需要减去一次 a[i][j] 的值，才是正确答案哦！
            long long current_sum = main_diag_sums[i - j + (m - 1)] + anti_diag_sums[i + j] - a[i][j];
            max_sum = std::max(max_sum, current_sum);
        }
    }

    std::cout << max_sum << "\n";
}

int main() {
    // 加速输入输出，让程序跑得飞快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

效率分析喵~

时间复杂度: O(n * m) 的说。我们主要做了两件事：一次遍历棋盘来预处理对角线和（O(nm)），再一次遍历棋盘来计算每个位置的最大和（O(nm)）。总的来说就是 O(n*m)，对于这道题的数据范围来说绰绰有余啦！
空间复杂度: O(n * m) 的说。我们用了一个 n x m 的二维数组来存棋盘，然后用了两个大小为 n + m - 1 的一维数组来存对角线和。所以空间主要是由棋盘本身决定的。

猫娘的小课堂~

这道题是不是很有趣呀？它教会了我们一个重要的思想，喵~

核心思想: 预处理 (Precomputation)！当发现题目中有很多重复计算时，可以想办法把这些计算结果提前存起来。这是一种典型的 空间换时间 策略，在算法竞赛中非常常用哦！
对角线性质: 一定要记住这个小技巧呐！
- 主对角线 (左上->右下): i - j 是个常数。
- 副对角线 (右上->左下): i + j 是个常数。 这个性质在解决其他网格（Grid）问题时也可能派上大用场！
坐标映射: 当你想用一个计算结果（比如 i - j）作为数组下标，但它可能是负数时，一个简单的办法就是给它加上一个合适的偏移量，把它整体平移到非负数区间。
细节决定成败: 计算总和时，千万不要忘记中心点 a[i][j] 被两条对角线共享，所以会被计算两次。一定要记得减去一次，这可是拿到AC的关键一步呢！

希望这篇题解能帮到你，祝你刷题愉快，天天AC！喵~ (ฅ^•ﻌ•^ฅ)

D. X-Sum - 题解 ​

比赛与标签 ​

喵喵的棋盘挑战！ ​

聪明的猫娘妙计喵~ ​

代码魔法时间！ ​

效率分析喵~ ​

猫娘的小课堂~ ​