题解

问题分析

我们需要找到一个平移向量 $(dx, dy)$，使得当纪念碑底座平移后，覆盖的瓷砖数量最少。瓷砖的布局具有特殊的周期性结构。

关键观察

1. 瓷砖布局的周期性：

   • 瓷砖左下角坐标为 $(i \cdot k + j, j)$
   • 在 $x$ 方向上，周期为 $k$
   • 在 $y$ 方向上，周期为 $1$
   • 因此只需要考虑 $dx \in [0, k)$ 和 $dy \in [0, 1)$ 的平移

2. 多边形覆盖的瓷砖计数：

   • 由于多边形边平行于坐标轴，可以分解为多个矩形区域
   • 对于每个矩形区域，可以计算覆盖的瓷砖数量

算法思路

步骤1：多边形矩形化

将轴对齐多边形分解为不相交的矩形：

• 使用扫描线算法，在 $y$ 坐标变化时记录 $x$ 范围
• 对于每个连续的 $y$ 区间 $[y_{\text{min}}, y_{\text{max}}]$，确定多边形的 $x$ 范围 $[x_{\text{left}}, x_{\text{right}}]$

步骤2：瓷砖覆盖计算

对于每个矩形区域 $[x_l, x_r] \times [y_b, y_t]$，计算覆盖的瓷砖数量：

由于瓷砖左下角为 $(i \cdot k + j, j)$，对于固定的 $y = j$，瓷砖的 $x$ 坐标为：

$$x = j, k+j, 2k+j, \ldots$$

因此对于 $y$ 坐标区间 $[y_b, y_t]$ 和 $x$ 坐标区间 $[x_l, x_r]$，覆盖的瓷砖数量为：

$$\sum_{j=\lceil y_b \rceil}^{\lfloor y_t \rfloor} \left( \left\lfloor \frac{x_r - j}{k} \right\rfloor - \left\lceil \frac{x_l - j}{k} \right\rceil + 1 \right) $$

步骤3：最优平移搜索

由于周期性，只需要枚举 $dx = 0, 1, \ldots, k-1$：

• 对于每个 $dx$，计算平移后的多边形覆盖的瓷砖总数
• 找出覆盖瓷砖数量最少的 $dx$

优化：不需要枚举所有 $k$ 个平移，可以利用前缀和或数论性质进一步优化。

复杂度分析

• 多边形矩形化：$O(n \log n)$
• 单个平移的瓷砖计数：$O(\text{矩形数量} \cdot \text{平均y范围})$
• 总复杂度：对于小子任务可接受，对于大数据需要进一步优化

样例验证

对于样例：

12 3
2 3
1 3
1 2
3 2
3 1
8 1
8 2
10 2
10 3
8 3
8 4
2 4

多边形可以分解为多个矩形，通过计算发现最优平移时覆盖7块瓷砖。

实现细节

1. 多边形处理：

   # 提取所有y坐标，排序去重
   y_coords = sorted(set(y for x,y in vertices))
   
   # 对于每个y区间，计算x范围
   for i in range(len(y_coords)-1):
       y_bottom = y_coords[i]
       y_top = y_coords[i+1]
       x_left, x_right = get_x_range_at_y(y_bottom)
   

2. 瓷砖计数：

   def count_tiles_in_rect(xl, xr, yb, yt, k, dx):
       total = 0
       for j in range(ceil(yb), floor(yt)+1):
           # 调整x范围考虑平移dx
           adj_xl = xl - dx
           adj_xr = xr - dx
           # 计算该y行覆盖的瓷砖数量
           first_tile = ceil((adj_xl - j) / k)
           last_tile = floor((adj_xr - j) / k)
           total += max(0, last_tile - first_tile + 1)
       return total
   

优化策略

对于大数据（$n \leq 100,000, k \leq 100,000$）：

1. 数学优化：将双重求和转化为单重求和
2. 前缀和技巧：预处理模 $k$ 的余数信息
3. 数论分解：利用 $i \cdot k + j$ 的结构性质

总结

本题的核心在于：

1. 理解瓷砖布局的周期性结构
2. 将多边形分解为矩形区域
3. 利用数学公式高效计算覆盖的瓷砖数量
4. 在有限的平移空间中搜索最优解

通过合理的几何分解和数学优化，可以在大规模数据下高效解决问题。