自动搬运

查看原文

来自洛谷，原作者为

	Grand_Dawn 小WA撑小艇，偷采AC回

搬运于2025-08-24 23:04:52，当前版本为作者最后更新于2024-10-05 19:30:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

虽然这篇题解很长，但大部分都在证明简单的思路为什么是对的。

以下记黑点是被选中的格点，白点为未被选中的格点。

无限制条件

当不存在某个格点必须被选中/不选中时，答案为 $nm-\left\lfloor\frac{n+1}{2}\right\rfloor\left\lfloor\frac{m+1}{2}\right\rfloor$。考虑以下分析过程：

考虑相邻两行中各选取一个点，会有 $m^2$ 条连线，这些连线仅经过两个端点。因此，相邻两行中必须存在一行全部被染黑。对于列同理。

在 $n$ 行中，需要满足以上条件则最少需要 $\left\lfloor\frac{n}{2}\right\rfloor$ 行被染黑。方案为第 $2,4,6,...,2\left\lfloor\frac{n}{2}\right\rfloor$ 行被染黑。

而无论选取哪些行被涂黑后，每一列剩余的白格子数量相等，故可以用同样的方式选取第 $2,4,6,...,2\left\lfloor\frac{m}{2}\right\rfloor$ 染黑。

这样选取后时满足“相邻两行中必须存在一行全部被染黑”的最优解之一。以下证明这种选取方法是正确的：

由于所有的第 $2i$ 行，第 $2j$ 列被染黑，故此图内一个格子 $(x,y)$ 为白色当且仅当 $x\equiv y\equiv 1\pmod 2$。

如果连线端点处存在黑点则条件成立。则考虑任意两个不同的白点 $(2x_1+1,2y_1+1)$ 和 $(2x_2+1,2y_2+1)$ 的连线上：

• 考虑中点 $(x_1+x_2+1,y_1+y_2+1)$，如果此点为黑色，则该连线上存在黑点。

• 如果中点 $(x_1+x_2+1,y_1+y_2+1)$ 为白色点，则满足 $x_1+x_2+1=2x_3+1,y_1+y_2+1=2y_3+1$，考虑使用白点 $(2x_1+1,2y_1+1)$ 和 $(x_1+x_2+1,y_1+y_2+1)$ 递归调用此过程。

显然此过程中，中点不会落在端点上，故此过程一定会结束，即存在黑色点在连线上。

由以上过程，则任意两个不同的格点的连线上至少有一个黑点。此时选取的黑色点个数为 $\left\lfloor\frac{n}{2}\right\rfloor m+n\left\lfloor\frac{m}{2}\right\rfloor-\left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{m}{2}\right\rfloor=nm-(n-\left\lfloor\frac{n}{2}\right\rfloor)(m-\left\lfloor\frac{n}{2}\right\rfloor)=nm-\left\lfloor\frac{n+1}{2}\right\rfloor\left\lfloor\frac{m+1}{2}\right\rfloor$。

限制条件为黑点

考虑无限制条件的方案，增加限定点为黑色一定是一个合法方案，则答案 $ans$ 一定满足 $nm-\left\lfloor\frac{n+1}{2}\right\rfloor\left\lfloor\frac{m+1}{2}\right\rfloor\leq ans\leq nm-\left\lfloor\frac{n+1}{2}\right\rfloor\left\lfloor\frac{m+1}{2}\right\rfloor+1$。

则实际上仅需要考虑是否存在无限制条件的解 $(a,b)$ 被涂黑：

分别考虑行和列，是同理的。以下考虑行：

• 如果 $n\equiv 1\pmod 2$，则考虑相邻两行的关系共有 $n-1$ 对，而每涂黑一行仅会至多减少 $2$ 对限制。故最小值为 $\frac{n-1}{2}$ 行被涂黑。此时涂黑每一行都必须减少恰好 $2$ 对限制。因此必须填涂第 $2i(1\le i\le \left\lfloor\frac{n}{2}\right\rfloor)$ 行。

• 如果 $n\equiv 0\pmod 2$，且 $a\equiv 0\pmod 2$，则由无限制条件的方案，该点已被涂黑。

• 如果 $n\equiv 0\pmod 2$，且 $a\equiv 1\pmod 2$。由于 $n$ 行 $m$ 列的网格是上下对称的，则 $(a,b)$ 与 $(n+1-a,b)$ 的答案是相同的。而 $n+1-a\equiv 0\pmod 2$，故该点也可以被涂黑。

综上条件，再对于行和列的条件再取或，则不存在存在无限制条件的解 $(a,b)$ 被涂黑当且仅当 $n\equiv m\equiv a\equiv b\equiv 1\pmod 2$。

因此此时答案为 $\left\{\begin{aligned}&nm-\left\lfloor\frac{n+1}{2}\right\rfloor\left\lfloor\frac{m+1}{2}\right\rfloor+1,n\equiv m\equiv a\equiv b\equiv 1\pmod 2\\&nm-\left\lfloor\frac{n+1}{2}\right\rfloor\left\lfloor\frac{m+1}{2}\right\rfloor\quad\ \ \ ,\text{otherwise.}\end{aligned}\right.$。

限制条件为白点

考虑如果 $(a,b)$ 必须强制被涂白，则由条件“相邻两行中必须存在一行全部被染黑”，第 $a-1$ 行和第 $a+1$ 行必须全部被涂黑。第 $b-1$ 列和第 $b+1$ 列必须全部被涂黑。

考虑被涂黑行列夹着的四个区域 $\left\{\begin{aligned}&x=a\\&yb+1\end{aligned}\right.$ $\left\{\begin{aligned}&xa+1\\&y=b\end{aligned}\right.$ 和剩下 $4$ 个区域 $\left\{\begin{aligned}&x<a-1\\&y<b-1\end{aligned}\right.$ $\left\{\begin{aligned}&xb+1\end{aligned}\right.$ $\left\{\begin{aligned}&x>a+1\\&y>b+1\end{aligned}\right.$ $\left\{\begin{aligned}&x>a+1\\&y<b-1\end{aligned}\right.$，分别以 $(a,b)$ 点（沿四个方向）向外为正方向参考无限制条件的方案构造，依然是满足条件“相邻两行中必须存在一行全部被染黑”的最优解。</p>

此时的构造 $(x,y)$ 为白点当且仅当 $x\equiv a\pmod 2,y\equiv b\pmod 2$。使用类似前文的证明可得构造是正确的。

化简后答案为 $nm-\left\lfloor\frac{n+(a\bmod 2)}{2}\right\rfloor\left\lfloor\frac{m+(b\bmod 2)}{2}\right\rfloor$。