A. 树林 详细题解

题目核心理解

在一块 $n\times n$ 的正方形草坪上种树，树只能种在整数坐标 $(x,y)$ 处。 每棵树以种植点为圆心、半径 $r$ 的圆必须完全在草坪内，且任意两个圆只能相切、不能重叠（圆心距 $\ge 2r$）。 要求输出最多能种多少棵树，以及任意一种最优方案。

核心思路

1. 关键性质

• 设 $\delta=\lceil r\rceil$，合法坐标必须满足 $\delta\le x,y\le n-\delta$，保证圆不超出草坪。
• 两点 $(x_1,y_1)$、$(x_2,y_2)$ 合法条件：$$(x_1-x_2)^2+(y_1-y_2)^2\ge (2r)^2$$
• 问题等价于：在合法点集中选出最多的点，两两互不冲突 → 求图的最大团。

2. 递归构造思路

用 $f(a_\delta,\dots,a_{n-\delta})$ 表示只使用满足 $x\le a_y$ 的点时的最优方案。 每次取最大横坐标 $\overline{x}$ 及其所在列 $\overline{y}$，分两种决策：

1. 不种：将该列上限减 $1$，递归求解。
2. 种：把所有列的上限更新为与该点距离合法的最大值，再递归求解。

3. 小半径特判

• $r\le \dfrac12$：所有内部整点都能种。
• $\dfrac12<r<\dfrac{\sqrt2}{2}$：种 $x+y$ 为偶数的点。
• 更小 $r$ 可直接按网格规律构造。

算法流程

1. 计算 $\delta=\lceil r\rceil$，筛出所有合法整点。
2. 建立冲突图：两点距离不足 $2r$ 则连边。
3. 使用 最大团算法 求出最多可种点数。
4. 输出点数及对应坐标。

公式与复杂度分析

距离约束公式：

复杂度

• 合法点数：$O(n^2)$
• 最大团算法：指数级，但 $n\le 20$ 加剪枝可轻松通过
• 总体：可在 $4$ 秒时限内处理所有数据

可轻松处理 $n\le 20$、$r$ 为 $1\sim3$ 位小数的所有数据范围。