CF2111F Puzzle

首先观察到一个小方格只有四个边，所以 $\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$ 即可。