TOAD 7 - The Gridville Garbash problem

Problem

有一个 \(n \times n\) 的矩阵，你可以任选 \(k < n\) 个格子并控制它们。任意时刻对于任意一个格子，如果它周围有不小于两个格子被控制，那么这个格子也会被控制。问是否存在一种初始选择 \(k\) 个格子的方案使得最后 \(n \times n\) 个格子都被控制？

Solution

不存在。

考虑任意时刻被控制的区域的周长。每次一个格子由未被控制转为被控制，由于这个格子至少与 2 个被控制的格子相邻，因此总周长是不会增加的。

初始时刻的总周长至多是 \(4k\) ，而如果所有格子都被控制的话总周长是 \(4n\) ，所以不存在。

不过初始时选择 \(n\) 个格子倒是可以控制所有格子。

当 \(n\) 为奇数时，选择 \((0, 2i), (2i, 0), (0, 0)\) 共 \(n\) 个格子，其中 \(0 \leq i < \frac{n}{2}\) 。

当 \(n\) 为偶数时，选择 \((0, 2i + 1), (2i + 1, 0)\) 共 \(n\) 个格子，其中 \(0 \leq i < \frac{n}{2}\) 。

nonsense

不声不响从 PNG 换到了 MathJax ，发现 MathJax 也不慢，这里公式不多，加载速度比 Disqus 还快真是不能多说。（可是字体颜色怎么是紫色的）

然后后端从 Makuru 切换到了 Rdiscount ，速度有了极大的提高。转义 ^, _ 真是蛋疼啊。我有 sed， 鼓瑟吹笙。

这几天鼓捣笔记本去了，一直没怎么看书做题。而且老师给的 deadline 快到了，感觉好囧啊。

这几天看了几道网络流的题，感觉被虐傻了完全不会网络流啊。哪天抽时间写写（喂喂喂立 flag 死得早）