黄金格 题解

题目分析

我们有一个 $H$ 行 $W$ 列的矩形地图，行号 $r$ 从 $1$ 到 $H$，列号 $c$ 从 $1$ 到 $W$。
对于一个给定的参数 $x$，格子 $(r,c)$ 被称为“黄金格”当且仅当满足以下不等式：

[
\sqrt{r^2 + c^2} \ \le\ x + r - c
]

题目要求统计地图中所有黄金格的数量。

举例：若 $x=5$，格子 $(4,3)$ 满足 $\sqrt{4²⁺³2}=5$，而右侧 $5+4-3=6$，$5\le 6$ 成立，因此 $(4,3)$ 是黄金格。

解题思路

本题的 $H,W,x$ 均不超过 $1000$，枚举所有格子的总数量为 $H\times W$，在最坏情况下仅 $10^6$ 级别。
因此，最直接的方法就是 暴力枚举：遍历所有可能的 $(r,c)$ 坐标，逐一检查不等式是否成立，并累加计数器。

是否需要避免浮点运算？

不等式左边是一个开平方运算，结果是浮点数。由于本数据范围较小，直接调用 sqrt 函数完全可行，且精度足够（在 $r,c \le 1000$ 时，$r^2+c2$ 最大为 $2\times 10^6$，sqrt 的结果在 double 下可以精确表示，误差可以忽略）。
如果担心浮点误差，也可以将不等式两边平方来消除根号，但需要注意符号问题。不过本题采用直接调用 sqrt 的写法已经稳定通过。

算法说明

1. 读入三个正整数 $H,W,x$。
2. 初始化答案变量 ans = 0。
3. 双重循环：r 从 $1$ 到 $H$，c 从 $1$ 到 $W$。
4. 在循环内计算：
   • left = sqrt(r*r + c*c) （注意类型：sqrt 返回 double）。
   • right = x + r - c。
   • 若 left <= right，则 ans 增加 $1$。
5. 循环结束后输出 ans。

时间复杂度分析

• 双重循环枚举所有格子，循环体内部为常数次四则运算与一次开方运算。
• 总时间复杂度为 $O(H \times W)$，在最大数据范围下约 $10^6$ 次运算，完全可以在 1 秒内完成。

空间复杂度为 $O(1)$，只使用了几个变量。

参考代码及解释

以下是 C++ 的实现：

cpp
复制
1#include <iostream>
2#include <cmath>
3using namespace std;
4
5int main() {
6    int H, W, x;
7    cin >> H >> W >> x;          // 输入行数、列数、参数 x
8    int ans = 0;                 // 黄金格计数器
9
10    for (int r = 1; r <= H; ++r) {
11        for (int c = 1; c <= W; ++c) {
12            // 计算左侧：sqrt(r^2 + c^2)
13            double left = sqrt(r * r + c * c);
14            // 计算右侧：x + r - c
15            int right = x + r - c;
16            if (left <= right) {
17                ans++;            // 满足条件则计数
18            }
19        }
20    }
21
22    cout << ans << "\n";         // 输出答案
23    return 0;
24}

代码说明

• #include <cmath> 用于使用 sqrt 函数。
• double left 保存开方后的结果，因为 sqrt 返回浮点数。
• int right 存储右侧的整数值。
• 比较时 left <= right，编译器会将 right 自动转换为 double 再比较，符合预期。
• 双重循环遍历所有格子，对每个格子判断一次，更新 ans。
• 最后输出答案并换行。

能否优化？

对于 $H,W \le 1000$ 的数据范围，上述 $O(HW)$ 算法已经足够高效，无需进一步优化。若数据范围扩大，则可能需要数学推导减少枚举量，但本题完全不需要。

总结

本题是一道基础的枚举练习题。只要理解题意，利用双重循环对全部格子进行条件判断，就能快速得到答案。注意数据类型的选择以及浮点运算的正确使用即可。