题解：P14041 [PAIO 2025] Towers

xyx404 · 2025-10-02 19:06:46 · 题解

思路：

通过将炮塔放置在行和列均为 K 的倍数的位置上，可以确保每个 K\times K 的子矩阵都包含至少一个这样的炮塔。

也就是说行方向需要 \lfloor N/K \rfloor 个炮塔，列方向需要 \lfloor M/K \rfloor 个炮塔，共需要 \lfloor N/K \rfloor \times \lfloor M/K \rfloor 个炮塔。

这样便是最优的。

代码：

::::success[代码一]

#define int32 int32_t
int32 solve(int32 N, int32 M, int32 K){
    int32 ans=0;
    for(int i=K;i<=N;i+=K){
        for(int j=K;j<=M;j+=K){
            ans++;
        }
    }
    return ans;
}

::::

::::success[代码二]

#define int32 int32_t
int32 solve(int32 N, int32 M, int32 K){
    return (N/K)*(M/K);
}

::::