G2024 [GESP202512 二级] 黄金格 题解

知识点：双重枚举、不等式、整数范围。

解题思路

逐格枚举行i、列j，将距离不等式整理为√(i²+j²)≤x+i-j。先判断右端非负，再比较平方。

为什么正确

右端非负时平方保持大小关系；负数不可能大于等于非负距离，须提前排除。

易错点

不能直接对负的右端平方；坐标平方和及平方比较用long long。

复杂度

时间O(hw)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long h,w,x,ans=0;
    cin>>h>>w>>x;
    for(long long i=1;i<=h;i++)for(long long j=1;j<=w;j++) {
        long long z=x+i-j;
        ans+=(z>=0&&i*i+j*j<=z*z);
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。