作者ckc1ark (伪物)
看板Prob_Solve
标题Re: [问题] UVa 11464 : Even Parity
时间Mon Apr 15 02:33:53 2019
※ 引述《nicknick0630 (NICK)》之铭言：
: UVa 连结 :
: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2459
: 短网址 : https://is.gd/NYytBw
: 题目:
: 给一 N x N 的矩阵，里面每个元素皆为 0 或 1
: 且每个元素的 parity 定义为该元素位置的上、下、左、右四个位置中 1 的数目
: 题目要求我们要把其中一些 0 改成 1，让所有元素的 parity 皆为偶数
: 也就是 0、2、4个，并输出改变次数最少的值 ( 若无法的话输出 -1 )
: 解法:
: 列举出第一列，若题目给定的矩阵的第一列无法转换成列举的情况的话，删除此种情况
: 然後将所有合法的列举情况用第一列推导出第二列
: 再用 Row 2 推导出 Row 3，依序推导到 Row N
: 最後再用题目的矩阵与这些列举情况推导出来的矩阵做比较
: 找出最少 0 转换成 1 的次数
: 我的问题:
: 为甚麽可以保证 Row N 会是正确的? 也就是说 Row N 的 parity 也会是偶数个
: 若是考虑 Row 1 ~ Row N-1 ，因为都可以用他的下一列来修正
: 使自己一定为偶数 parity，但是 Row N 不能用 Row N+1 来修正自己
: 所以想请问要如何证明呢?
: 这是我写的文章，里面有更清楚的描述，我的问题就是在 "证明" 那一个段落
: 文章连结 : https://is.gd/eN7WyK
: 谢谢各位大大
: 感激不尽
用n=5来当范例思考
已知给定第一个row可以一路推到最後一个row(先不管正确与否) 且为唯一推法
也已知第一个row都是0的时候 可以得到一组符合条件的解
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
那可以试着每次flip一个位置就好 规则蛮容易看出来的 也会得到符合parity的解
1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0
0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0
又已知 两个符合parity的解 xor 起来也会是一个符合parity的解
所以给定任意个第一个row 一定有办法是这n个解的xor组合 (且为唯一可能)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.30.51
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1555266835.A.DFA.html
1F：→ ckc1ark: 对於这任意bit的规则可能需要再补充一下 会比较完整 04/15 02:35
※ 编辑: ckc1ark (140.112.30.51), 04/15/2019 02:43:08
2F：推 cutekid: 推(Y) 04/15 13:34
3F：推 nicknick0630: 谢谢大大的回复 04/15 16:15
4F：推 nicknick0630: 那这样就变成是要证明 2 个符合偶数 parity 的解 xo 04/15 16:16
5F：→ nicknick0630: r 後还是符合parity，不过我想了很久还是不知道怎 04/15 16:16
6F：→ nicknick0630: 麽下手QQ 04/15 16:16
7F：→ ckc1ark: 假设a,b,c,d是even parity e,f,g,h也是 两两xor起来ae,bf 04/15 19:11
8F：→ ckc1ark: ,cg,dh 也会是even 这应该很直觉?(xor有交换律和结合律) 04/15 19:11