思路
太猎奇
考虑我们应该会 \(\mathcal{O} (\textrm{障碍物数}^2)\) 的做一次问题
但是这类问题其实还有一种 \(\mathcal{O} (\textrm{面积})\) 的做法
具体的, 令 \(f_{i, j}\) 表示 \((i, j)\) 这个点作为右下角时的最大正方形边长
则转移如下
\[ \begin{gather*}
f_{i,j} =
\begin{cases}
0 & \text{if } a_{i,j} = 0 \\
\min(f_{i,j-1}, f_{i-1,j-1}, f_{i-1,j}) + 1 & \text{if } a_{i,j} = 1
\end{cases}
\end{gather*} \]
反正很牛啊
大概就是这样理解的
然后最终的答案是询问一个矩阵中的 \(f\), 注意不是简单的询问给出的矩阵中的最大值, 而是要稍微做一些处理
这题比较巧妙的地方还有一个将询问做二分转成判断可行性, 非常牛啊
总结
这个最大正方形真难想吧, 好像本质上就是个继承, 但是这个写法真的很美丽
把问题转成判断可行性