CF2111F Puzzle

LinkZelda · 2025-06-06 15:40:22 · 题解

首先观察到一个小方格只有四个边，所以 \frac ps\leq 4。

然后考虑对于确定的 s 怎么样构造出最大的 p。

容易发现一定是构造成一个 1\times s 的矩形，因为这样在 s 增大 1 的时候可以让 p 增大 2。（因为一定要联通所以让 p 增大 2 已经时最优的了）此时 \frac p s=\frac{2s+2}{s}=2+\frac 2s。

如果我们想要构造出其他的不能表达成这种形式的且 \frac p s\geq 2 的图形，那么一定会在某一次加入某个小方格的时候和其他两个小方格相邻，此时 p 没有增加而 s 增加 1，那么 \frac p {s+1}=\frac{2s+2}{s+1}=2。

所以对于 \frac{p}{s}\geq 2 的情况一定是上面两者之一，否则无解。

接下来考虑 \frac{p}{s}<2 的情况，我们从上面这种让 p 加 2，s 加 1 的构造中得到启发。我们设 k 满足 p-2k<2,p-2k>0，那么问题就转化为先构造一个 \frac{1}{s-k} 或者 \frac{2}{s-k} 的图案，然后加上一个矩形。

对于 \frac{2}{s-k}，我们可以构造一个 2(s-k)\times 2(s-k) 的正方形。

对于 \frac{1}{s-k}，我们可以构造一个 4(s-k)\times 4(s-k) 的正方形。

然后加上一个矩形还原成 \frac ps 即可。