B4448 [GESP202512 二级] 黄金格
题目描述
小杨在探险时发现了一张神奇的矩形地图，地图有HHH行和WWW列。每个格子的坐标是(r,c)(r, c)(r,c)，其中rrr表示行号从111到HHH，ccc表示列号111到WWW。
小杨听说地图中隐藏着一些“黄金格”，这些格子满足一个神秘的数学挑战：当格子坐标(r,c)(r, c)(r,c)代入特定的不等式关系成立时，该格子就是黄金格。具体来说，黄金格的条件是：r2+c2≤x+r−c\sqrt{r^2 + c^2} \leq x + r - cr2+c2≤x+r−c。
例如，如果参数x=5x = 5x=5，那么格子(4,3)(4, 3)(4,3)就是黄金格。因为左边坐标平方和的平方根42+32\sqrt{4^2 + 3^2}42+32算出来是555，而右边5+4−35 + 4 - 35+4−3算出来是666，555小于等于666，符合条件。
输入格式
三行，每行一个正整数，分别表示H,W,xH,W,xH,W,x。含义如题面所示。
输出格式
一行一个整数，代表黄金格数量。
输入输出样例 #1
输入 #1
4 4 2输出 #1
4说明/提示
样例解释
:::align{center}
:::
图中标注为黄色的四个格子是黄金格，坐标分别为(1,1)(1, 1)(1,1)，(2,1)(2, 1)(2,1)，(3,1)(3, 1)(3,1)，(4,1)(4, 1)(4,1)。
数据范围
对于所有测试点，保证给出的正整数不超过100010001000。
题解：B4448 [GESP202512 二级] 黄金格
一、题目分析
1. 核心需求
给定一个HHH行WWW列的矩形地图，每个格子坐标为(r,c)(r, c)(r,c)（1≤r≤H1 \leq r \leq H1≤r≤H，1≤c≤W1 \leq c \leq W1≤c≤W），统计满足黄金格条件的格子数量。黄金格的原始条件为：
r2+c2≤x+r−c\sqrt{r^2 + c^2} \leq x + r - cr2+c2≤x+r−c
2. 关键优化：避免浮点数精度误差
原始条件包含平方根运算，若直接使用sqrt函数计算，会引入浮点数存储和计算的精度误差（例如，某些本应成立的条件可能因精度丢失被判为不成立，反之亦然）。
由于不等式两边均为非负数（左边r2+c2\sqrt{r^2 + c^2}r2+c2必然非负；若右边x+r−c<0x + r - c < 0x+r−c<0，则不等式一定不成立，无需判断），因此可对两边同时平方，转化为等价的整数运算不等式，完全规避精度问题：
r2+c2≤(x+r−c)2r^2 + c^2 \leq (x + r - c)^2r2+c2≤(x+r−c)2
二、解题思路
- 输入读取：读取三个正整数HHH（行数）、WWW（列数）、xxx（题目参数）。
- 计数器初始化：定义计数器
cnt并初始化为 0，用于统计黄金格数量。 - 遍历所有格子：使用双重循环遍历所有格子坐标(r,c)(r, c)(r,c)（外层循环遍历行rrr，内层循环遍历列ccc）。
- 条件判断：对每个格子，验证转化后的整数不等式是否成立，若成立则计数器
cnt加 1。 - 输出结果：循环结束后，输出计数器
cnt的值，即黄金格总数。
三、代码解析
#include<iostream>usingnamespacestd;intmain(){inth,w,x;intcnt=0;// 初始化黄金格计数器为0cin>>h>>w>>x;// 读取行数h、列数w、参数x// 外层循环：遍历所有行（r从1到h，对应题目中的行坐标）for(intr=1;r<=h;r++){// 内层循环：遍历当前行的所有列（c从1到w，对应题目中的列坐标）for(intc=1;c<=w;c++){// 验证转化后的整数不等式，避免浮点数精度误差if(r*r+c*c<=(x+r-c)*(x+r-c)){cnt++;// 满足条件，计数器加1}}}cout<<cnt;// 输出黄金格总数return0;}逐行关键说明
int cnt=0;：计数器初始化为 0，确保统计从无到有准确累积。- 双重循环
for(int r=1;r<=h;r++)和for(int c=1;c<=w;c++)：严格对应题目中坐标从 1 开始的要求，遍历所有H×WH \times WH×W个格子。 - 条件判断
r*r+c*c<=(x+r-c)*(x+r-c)：核心优化点，用整数平方运算替代平方根运算，保证判断结果的绝对准确。 - 时间复杂度：O(H×W)O(H \times W)O(H×W)，由于HHH、WWW最大为 1000，最大运算量为1000×1000=1061000 \times 1000 = 10^61000×1000=106次，完全满足时间限制，不会超时。
四、样例验证
1. 样例输入
4
4
2
2. 样例输出说明
最终满足条件的格子数为 4，与样例输出一致。
五、注意事项
- 坐标起始值：题目中rrr和ccc从 1 开始，循环不可从 0 开始，否则会统计无效坐标。
- 精度问题：严禁直接使用
sqrt函数判断原始不等式，必须通过平方转化为整数运算。 - 数据范围：HHH、WWW、xxx不超过 1000，双重循环无性能压力，无需额外优化。