题解:P14041 [PAIO 2025] Towers

封面


思路:

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

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

这样便是最优的。

代码:

#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;
}
#define int32 int32_t
int32 solve(int32 N, int32 M, int32 K){
return (N/K)*(M/K);
}