總結(jié): OI 不是白學(xué)的.

注: 下面的方法看上去很復(fù)雜, 但是如果熟練的話能做到很快. (不過大概還是比不過原神玩家.)

容易發(fā)現(xiàn)一個很強的性質(zhì), 就是按開關(guān)的順序?qū)顟B(tài)沒有影響.

所以我們設(shè)九個開關(guān)的狀態(tài)分別為??(從上到下, 從左到右, 0 表示未按下, 1 表示按下), 方格的狀態(tài)分別為 (同理).

我們考慮每個方格會如何被其周圍的方格影響.

以??為例, 我們發(fā)現(xiàn)它會被??決定.?

具體地, 我們有?.

信息技術(shù)課學(xué)的好的同學(xué)會知道這里的??指的就是異或運算.

因為這里 , 我們可以簡單理解成模 2 的加法.

也就是說上面的式子等價于這個式子:

很好理解吧.

所以我們只需要枚舉 ?把方程組列出來, 解就完事了!

所以下面是方程組構(gòu)成的增廣矩陣 (已經(jīng)代入了 ):

簡單解釋一下.

每一行表示一個方程. 前九個數(shù)表示九個未知數(shù)? 的系數(shù)(實際上系數(shù)應(yīng)該都是1和0, 但是那樣容易寫串), 最后一個數(shù)就是?.

比如第一行就表示,?, 其中已知?.

列完了方程組, 考慮消元!

我們知道一般的線性方程組消元人力算起來是很費勁的. 但是這是異或方程組, 有性質(zhì):

?, (容易證明).

也就是說異或兩次就相當(dāng)于什么都沒做, 并且 0 不會造成影響.

?并且因為異或是有交換律和結(jié)合律的, 我們的消元操作實際上非常簡單. 只需要把兩個方程異或一下, 都出現(xiàn)的未知數(shù)就沒了.

多說無用. 直接對上面的矩陣進(jìn)行消元.

首先我們消?.

我們將第二行的方程異或上第一行:

很簡單吧. 注意最后一行是要算的.

如法炮制消第四行:

這樣就消完一個未知數(shù)了!

當(dāng)然我們也沒有必要就執(zhí)著于按順序消. 我們可以通過選取恰當(dāng)?shù)南樞? 使消元的效果更好.

比如對于上面的方程組, 我們可以用第二行來消:

先別急. 我們會神奇的發(fā)現(xiàn), 用第三行消第五行:

即得?.

或許這樣幾步就消出來一個未知數(shù)有點碰運氣的嫌疑. 不過實際上即便沒有這樣的觀察, 因為這里矩陣的特殊性質(zhì)(band-matrix), 樸素進(jìn)行消元也會有不小的概率會遇到這種情況. 即使就是暴力消, 最終的運算量也不會有多大, 在草稿紙上用鉛筆橡皮不用幾分鐘就能消完.

回到具體計算上. 將??代入下面三個方程中 (之后不再用顏色區(qū)分正在進(jìn)行消元操作的兩行):

溫馨提示:?.

用第九行消第六行,?第六行消第二行:

此時得到?.

. 代入, 然后用第四行消第三行:

故?. 由此依次得?

整理得??(并不規(guī)范的寫法),

容易驗證成立.

由解的唯一性易知最少操作步數(shù)為5.

這道題就這么做完了. 因為本人之前也獨立搞出過這種東西(畢竟也算是經(jīng)典謎題了),?做起來還是問題不大的. 但是高考方向出這種題未免有點抽象了.?

不過作為OI選手, 必須指出的是這種東西真的就是異或方程組板子.

https://www.luogu.com.cn/problem/P2962

還有一些類似的應(yīng)用.

https://www.luogu.com.cn/problem/P3164

https://www.luogu.com.cn/problem/P2447

(方法都是類似的, 不講了)