B4429 [语言月赛 202511] 曼波 No More

· · 题解

来源

2025 年 11 月语言月赛，由洛谷网校提供。

考察顺序结构。

文字题解

题目给定了一个 n\times m 的网格，左上角格子的坐标为 (0,0)，右下角格子的坐标为 (n-1,m-1)，划分为若干个 r\times c 的子网格。

根据题意，将划分出 \dfrac{n}{r} 行 \dfrac{m}{c} 列的子网格。为了方便表述，并与原题中的坐标区分，在下面，我们用 [i,j] 表示划分出的，第 i 行第 j 列的子网格，在这里，i,j 均从 0 开始计数。

很容易发现，[i,j] 对应的原网格坐标，横坐标范围为 i\times r\sim i\times r + r-1，纵坐标范围为 j\times c\sim j\times c + c - 1。因此，(x,y) 将属于子网格 [\dfrac{x}{r}, \dfrac{y}{c}]。

现在，给定了左上角为 (x_1,y_1)，右下角为 (x_2,y_2) 的矩形区域。很容易计算出左上角属于子网格[\dfrac{x_1}{r}, \dfrac{y_1}{c}]，右下角属于子网格 [\dfrac{x_2}{r}, \dfrac{y_2}{c}]。

因此，包含或相交的子网格共有 (\dfrac{x_2}{r}-\dfrac{x_1}{r}+1)\times(\dfrac{y_2}{c}-\dfrac{y_1}{c}+1) 个。

需要额外注意的是，这里的除法均为 C/C++ 中向 0 取整的整数除法，因而不能将答案式化简为 \dfrac{x_2-x_1+r}{r}\times\dfrac{y_2-y_1+c}{c}。