K. Torus Path - 题解
比赛与标签
比赛: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams) 标签: greedy, math 难度: *1500
主人，我们来分析一下任务喵~
nya~ 各位算法大师们好呀！今天我们来解决一个在环形棋盘上走路的有趣问题！(ฅ'ω'ฅ)
题目给了我们一个 n x n 的大棋盘，每个格子里都有一个非负整数。我们的小机器人一开始在左上角 (1,1)，目标是走到右下角 (n,n)。
走路的规则有点特别哦：
- 每次只能向右或者向下移动。
- 这个棋盘是个"环面"（Torus），意思是：
- 从最右边一列再向右走，会"传送"到同一行的最左边一列。
- 从最下面一行再向下走，会"传送"到同一列的最上面一行。
- 最重要的规则：同一个格子不能访问两次！起点从一开始就算访问过了，终点一旦到达就不能再离开。
我们的任务是，找到一条满足这些规则的路径，使得路径上所有格子的数字之和最大！这个最大和是多少呢？
解谜的关键，就在坐标之和里喵！
这个问题看起来好复杂呀，又是环面又是不能重复访问，直接去搜索所有路径肯定会超时的说。但是，不要怕！这种看似复杂的网格路径题，背后往往藏着美妙的数学性质，喵~
让我们把坐标变成从0开始的，也就是从 (0,0) 到 (n-1, n-1)，这样计算起来更方便呐。
步骤一：发现那个神奇的不变量！
我们来观察一下每次移动对坐标 (i, j) 会产生什么影响。特别注意 (i + j) mod n 这个值！
普通移动：
- 向下：
(i, j) -> (i+1, j)，i+j变成了i+1+j，增加了1。 - 向右：
(i, j) -> (i, j+1)，i+j变成了i+j+1，也增加了1。
- 向下：
环面传送：
- 从最右边传送：
(i, n-1) -> (i, 0)。i+j的值从i+n-1变成了i。我们来看看(i+j) mod n的变化：(i + (n-1) + 1) mod n = (i+n) mod n = i mod n。哇！(i+j) mod n的值也恰好增加了1！ - 从最下边传送：
(n-1, j) -> (0, j)。i+j的值从n-1+j变成了j。同样地，( (n-1)+j + 1) mod n = (n+j) mod n = j mod n。这个值也增加了1！
- 从最右边传送：
结论：无论怎么移动，每走一步，(i+j) mod n 的值都会严格递增1！这是解开谜题的黄金钥匙，喵！
步骤二：路径和不变量的关系
既然每走一步 (i+j) mod n 都会加1，那么：
- 我们从
(0,0)出发，它的(i+j) mod n是0。 - 走第一步到达的格子
c₁，它的(i+j) mod n必定是1。 - 走第
k-1步到达的第k个格子cₖ，它的(i+j) mod n必定是(k-1) mod n。
步骤三：我们到底要跳过哪个格子？
我们的路径必须在 (n-1, n-1) 结束。这个终点的 (i+j) mod n 是 ((n-1) + (n-1)) mod n = (2n-2) mod n = n-2。
假设我们的路径长度为 L（即访问了 L 个格子）。那么终点就是路径上的第 L 个格子。根据上面的规律，它的 (i+j) mod n 应该等于 (L-1) mod n。 所以我们得到一个等式： (L-1) mod n = n-2
我们想让得分尽可能高，也就是访问的格子尽可能多。最多能访问 n*n 个格子。
- 如果
L = n*n，那么(L-1) mod n = (n*n-1) mod n = n-1。这与n-2不相等！所以我们不可能访问所有格子。 - 那我们试试访问
n*n-1个格子，也就是只跳过1个格子。此时L = n*n-1，那么(L-1) mod n = (n*n-2) mod n = n-2。嘿！这和终点的要求完全吻合！
这说明，我们最理想的情况就是设计一条路径，访问棋盘上除了一个格子之外的所有格子。
步骤四：找出被跳过格子的位置！
我们已经知道，路径上第 k 个格子的 (i+j) mod n 是 (k-1) mod n。 如果路径长度是 n*n-1，那么路径上格子的 (i+j) mod n 序列会是 0, 1, ..., n-1 重复 n-1 次，再加上 0, 1, ..., n-2。 这意味着，对于 k = 0, 1, ..., n-2，所有满足 (i+j) mod n = k 的格子都被访问了。 而对于 k = n-1，我们只访问了 n-1 次，但棋盘上满足 (i+j) mod n = n-1 的格子有 n 个。
所以，那个被我们无情跳过的格子，一定满足 (i+j) mod n = n-1。 在 0 <= i, j <= n-1 的范围内，这等价于 i+j = n-1。 这正是从右上角 (0, n-1) 到左下角 (n-1, 0) 的反斜线（anti-diagonal）！
步骤五：最终的贪心策略！
既然我们必须在反斜线上的格子里选择一个跳过，为了让总分最大，我们当然应该选择跳过那个数值最小的格子啦！
所以最终的解法就是：
- 计算出棋盘上所有格子的总和
total。 - 找到反斜线上
(i+j = n-1)所有格子中的最小值min_val。 - 最终答案就是
total - min_val！是不是非常优雅呢，喵~
把思路变成代码喵！
#include <iostream>
#include <vector>
#include <climits> // 为了使用 LLONG_MAX
using namespace std;
int main() {
// 开启高速输入输出，让程序跑得更快喵~
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
// 使用 vector 来存储我们的 n x n 棋盘
vector<vector<long long>> grid(n, vector<long long>(n));
long long total = 0; // 用 long long 防止总和溢出，这是个好习惯哦
// 读入数据，并计算所有格子的总和
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> grid[i][j];
total += grid[i][j];
}
}
// 初始化反斜线上的最小值为一个非常大的数
long long min_anti = LLONG_MAX;
// 遍历反斜线上的所有格子
// 反斜线的特点是 i + j = n - 1 (对于0-indexed坐标)
// 所以 j = n - 1 - i
for (int i = 0; i < n; i++) {
int j = n - 1 - i;
// 找到反斜线上值最小的那个格子
if (grid[i][j] < min_anti) {
min_anti = grid[i][j];
}
}
// 最终答案就是总和减去这个必须跳过的、值最小的格子
cout << total - min_anti << endl;
return 0;
}效率分析时间到~
- 时间复杂度: O(n²) 的说。我们需要遍历整个
n x n的棋盘来读入数据和计算总和，这是主要的时间开销。之后遍历反斜线只需要 O(n) 的时间。所以总的来说是 O(n²) 呐。 - 空间复杂度: O(n²) 的说。我们需要一个
n x n的二维数组（或vector）来存储整个棋盘，所以空间开销是 O(n²)。
喵呜~ 这次学到了什么呢？
这道题真是太棒了，它教会了我们几件重要的事情：
- 寻找不变量：在处理网格和特定移动规则的问题时，尝试寻找一些在移动过程中保持不变或有规律变化的量（比如本题的
(i+j) mod n），这常常是解题的突破口！ - 从约束反推性质：我们没有去傻傻地构造路径，而是通过分析起点、终点和移动规则的约束，反向推导出了路径必须具备的性质（比如必须跳过一个格子，且这个格子在反斜线上）。这种思维方式非常强大！
- 贪心算法的证明: 当我们通过数学推导确定了选择范围后（必须从反斜线上选一个跳过），贪心（选择最小的跳过）就成了显而易见的最优策略。严谨的推导是贪心正确性的保证。
- 注意数据范围: 题目中的数值可能很大，
n也不小，所以格子的总和很容易超过int的范围。记得使用long long来避免溢出，这是一个竞赛中常见的细节喵~
希望这篇题解能帮助到你！继续加油，探索算法世界中更多的奥秘吧！(>^ω^<)