「CMOI R1」First Town of This Journey／Grid Covering
Grand_Dawn
·
·
题解
虽然这篇题解很长，但大部分都在证明简单的思路为什么是对的。
以下记黑点是被选中的格点，白点为未被选中的格点。
无限制条件
当不存在某个格点必须被选中/不选中时，答案为 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\\&y<b-1\end{aligned}\right. \left\{\begin{aligned}&x=a\\&y>b+1\end{aligned}\right. \left\{\begin{aligned}&x<a-1\\&y=b\end{aligned}\right. \left\{\begin{aligned}&x>a+1\\&y=b\end{aligned}\right. 和剩下 4 个区域 \left\{\begin{aligned}&x<a-1\\&y<b-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. \left\{\begin{aligned}&x>a+1\\&y<b-1\end{aligned}\right.，分别以 (a,b) 点（沿四个方向）向外为正方向参考无限制条件的方案构造，依然是满足条件“相邻两行中必须存在一行全部被染黑”的最优解。
此时的构造 (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。