作者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/m.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