CCF-GESP计算机学会等级考试2025年12月二级C++T2 黄金格-程序员充电站

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

说明/提示

样例解释

:::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次，完全满足时间限制，不会超时。