UyHiP-2011-Mar

UyHiP 的题目感觉很杂，相对来说 TOAD 就好玩多了嘛。

Problem

给定一个无向图，点有黑白两种颜色。每次你可以选择一个点，并把这个点以及所有和它相邻的点的颜色取反。初始时所有点的颜色是白色。

是否能在有限步内把所有的点全部变成黑色？

原题链接如下

Solution

可以证明一定是可行的。

基于构造的证明

数学归纳法。对点数 \(n\) 进行归纳。

当 \(n = 1\) 时显然。

假设 \(n\) 时成立，我们要证明 \(n + 1\) 也成立。我们在其中选任意 \(n\) 个点。由假设知，对于这 \(n\) 个点存在一个方案使得全部变为黑色。如果这个方案顺便把没被选中的点变为黑色，则找到一组解了。否则我们可以取反任意 \(n\) 个点的颜色。

如果 \(n\) 为偶数，我们对于任意 \(n\) 个点均反色一次，可以知道每个点被反色了 \(n - 1\) 次为奇数，即现在每个点都是黑色。

如果 \(n\) 为奇数，易知必定有一个点的度数为偶数（奇数个点，度数和为偶数），我们一开始对于这个点操作一次，则现在还剩下偶数个点是白色的。对于这偶数个点，我们可以使用与 \(n\) 为偶数时类似的方法，每个点都有一次不被取反的机会。所以操作后所有点都是黑色的。

基于线代的证明

看到线代我就吓尿了。但是看完解法我觉得好简单 →_→

考虑证明高斯消元（ over GF2 ）是有解的。我们把原图的邻接矩阵加单位矩阵记为 \(M\) ，用 \(Diag(M)\) 表示矩阵 \(M\) 的对角线。我们要证明的是，若 \(M = M^T\) （即对称），则 \(xM = Diag(M)\) 一定存在解。

无解的充要条件是存在一个向量 \(v\) 使得 \(v^T M = 0\) 而 \(v^T Diag(M) = 1\) 。但是，我们有

\[ 0 = v^T M v = v^T (L + D + U) v = v^T L v + v^T D v + v^T U v = v^T L v + v^T D v + (v^T L v)^T = v^T L v + v^T D v + v^T L v = v^T D v = v^T Diag(M)\]

\(L, D, U\) 分别是 \(M\) 的下三角、对角矩阵、上三角。所以我们知道这种情况是不可能的，原方程必定有解。

nonsense

看维基百科果然是 dfs 。

我就想查查线性代数的东西结果居然查到 \(e^{\pi}\) 去了 →_→

blahtex 居然不支持 array 。似乎它自己写了个后端。于是重新搞了个后端。网上下载了一个 tex2png ，发现居然是 bash 写的真是太好了。改了改就可以用了。模仿 blahtex 给 Maruku 写了个后端，感觉蛮简单的。但是 tex2png 的 png 输出惨不忍睹，主要是 dvipng 的调用参数写抽了，所以就下载了 blahtex 的源代码看看它是怎么调用 dvipng 的。 总之差不太多啦。