A. Maximum Neighborhood

时间限制：每测试点2秒
内存限制：每测试点512MB

问题描述

考虑用数字填充的 $n \times n$ 网格，填充规则如下：
- 第一行从左到右包含从 $1$ 到 $n$ 的整数；
- 第二行从左到右包含从 $(n+1)$ 到 $2n$ 的整数；
- 依此类推，直到第 $n$ 行，包含从 $(n^2-n+1)$ 到 $n^2$ 的整数。

定义单元格的成本为其数值加上所有相邻单元格数值之和。如果两个单元格共享一条边，则视为相邻。

你的任务是计算网格中所有单元格的最大成本。
![[Pasted image 20251201120745.png]]

输入格式

第一行包含单个整数 $t$ ($1 \leq t \leq 100$) —— 测试用例数量。
每个测试用例仅包含一行，为一个整数 $n$ ($1 \leq n \leq 100$)。

输出格式

对于每个测试用例，输出一个整数 —— 网格中所有单元格的最大成本。

样例输入

5
1
2
3
4
5

样例输出

1
9
29
56
95

样例说明

• 当 $n=1$ 时，只有一个单元格，成本为 $1$。
• 当 $n=2$ 时，数值为 $4$ 的单元格成本最大：$4+2+3=9$。
• 当 $n=3$ 时，数值为 $8$ 的单元格成本最大：$8+5+7+9=29$。
• 当 $n=4$ 时，数值为 $15$ 的单元格成本最大：$15+11+14+16=56$。
• 当 $n=5$ 时，数值为 $19$ 的单元格成本最大：$19+14+18+20+24=95$。

暴力AC代码

// Problem: CF 2170 A
// Contest: Codeforces - Educational Codeforces Round 185 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2170/problem/A
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int a[200][200];

void solve(){
    int n;
    cin>>n;
    int num=1;
    int ans=0;
    for(int i=1;i<=n+100;i++){
        for(int j=1;j<=n+100;j++){
            a[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=num++;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int sum=a[i][j]+a[i-1][j]+a[i+1][j]+a[i][j-1]+a[i][j+1];
            ans=max(ans,sum);
        }
    }
    printf("%d\n",ans);
    return ;
}


int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

题目整理：CF 2170 A - Maximum Neighborhood

1. 你的代码思路分析 (Brute Force Simulation)

你采用的是最直观、最稳健的模拟（Simulation）方法。

核心逻辑

1. 构建网格：按照题目规则，双重循环填充 $1$ 到 $n^2$ 的数字。

2. 边界处理（亮点）：你声明了 a[200][200]，并在循环中清零。因为题目最大 $n=100$，当你访问 a[i+1][j] 或 a[i][j+1] 时，如果越界，访问到的是填充的 0。这意味着你不需要写大量的 if 语句来判断是否在边界上（例如 if (i > 1) 或 if (j < n)）。这大大简化了代码逻辑。

3. 计算代价：再次遍历网格，暴力计算每个点的 数值 + 上 + 下 + 左 + 右，取最大值。

复杂度分析

• 时间复杂度：$O(T \times N^2)$。由于 $N \le 100$，每次测试用例运算量约为 $10^4$，总运算量约为 $10^6$，远低于 $2$ 秒的时间限制（通常 $2$ 秒可以跑 $10^8$ 次运算）。这种做法在比赛中是满分策略，因为它最不容易写错。

• 空间复杂度：$O(N^2)$，完全可以接受。

代码小细节建议

虽然代码已经 AC，但在 C++ 竞赛编程中有一些习惯可以改进：

• 清空数组：你使用了双重循环手动清零。更简便的方法是使用 memset(a, 0, sizeof(a));（需要头文件 <cstring>），或者由于 $N$ 很小，每次 solve 里直接重新覆盖其实也行（但在本题因为用了 padding 处理边界，必须保证 padding 处是 0，所以清空是必须的）。

---

2. 进阶分析：有没有 O(1) 的数学解法？

虽然 $N=100$ 暴力足够，但如果 $N=10^9$ 怎么办？这道题其实存在数学规律。

观察

我们要找 当前值 + 邻居和 的最大值。

• 随着行和列增加，数值变大。最大值一定出现在右下角区域。

• 我们需要平衡数值本身的大小和邻居的数量（2个、3个还是4个）。

候选点分析

实际上，最大值只可能出现在两个位置（当 $N$ 较大时）：

1. 最后一行倒数第二个 $(n, n-1)$：

   • 数值很大（$n^2-1$），有 3个 邻居。

   • 公式推导约为：$4n^2 - n - 4$。

2. 倒数第二行倒数第二个 $(n-1, n-1)$：

   • 数值稍小，但有 4个 邻居（被大数包围）。

   • 公式推导约为：$5(n^2 - n - 1) = 5n^2 - 5n - 5$。

规律验证（对应样例）

• $N=3$: 比较位置 $(3,2)$ 和 $(2,2)$。答案是 29（位置 $(2,2)$，数值8，4个邻居）。

• $N=4$: 比较位置 $(4,3)$ 和 $(3,3)$。答案是 56（位置 $(4,3)$，数值15，3个邻居）。

• $N=5$: 答案是 95（位置 $(4,4)$，数值19，4个邻居）。

结论

• 当 $N$ 较小时（$N < 5$），边缘的大数值点优势明显。

• 当 $N \ge 5$ 时，内部的那个点（$(n-1, n-1)$）因为多一个邻居，且邻居数值都很大，其总和反超边缘点。

• 数学解法：可以根据 $N$ 的大小分段输出公式，但这容易因为推导错误导致 WA。在数据范围允许的情况下，暴力模拟永远优于数学推导。

---

3. 知识点总结（Review）

这道题目虽然简单，但有一个非常重要的技巧值得在你的 Obsidian 笔记中记录：

📌 技巧：Padding（哨兵/填充法）处理网格边界

你代码中最棒的部分就是处理边界的方式。

• 问题：在网格题中，计算 $(x, y)$ 的上下左右时，通常需要写：

  C++

  int sum = val[x][y];
  if(x > 1) sum += val[x-1][y];
  if(x < n) sum += val[x+1][y];
  // ... 左和右同理
  

  这很繁琐且容易写错。

• 解法：

  开数组时稍微开大一点（例如 $N$ 是 100，开 a[105][105]），并初始化为 0（或其他对答案无影响的值，如求最小值时初始化为 INF）。

  这样你就可以直接写：

  C++

  int sum = a[i][j] + a[i-1][j] + a[i+1][j] + a[i][j-1] + a[i][j+1];
  

  因为越界访问到的都是预设好的 0，不会影响求和结果，也不会导致程序崩溃。

📌 策略：看数据范围选算法

• $N \le 100 \implies O(N^3), O(N^4)$ 都是安全的。

• 看到这种范围，不要想复杂的数学公式，直接模拟。

• 只有当 $N \ge 10^5$ 时，才需要去推导公式或找规律。

---

下一步建议

如果你想整理到 Obsidian，建议创建一个笔记叫 "Grid Problem Techniques" (网格题技巧)，把你的这段代码作为 "Padding Trick" (填充技巧) 的范例存进去。

需要我帮你写一段适合放入 Obsidian 的 Markdown 笔记片段吗？