切換
舊版
前往
大廳
主題

ZeroJudge - b569: 總之就是一串燈泡 解題心得

Not In My Back Yard | 2019-06-13 13:23:00 | 巴幣 0 | 人氣 186

題目連結:


題目大意:
給定兩個字串(兩字串長度一樣,且皆不超過 10, 000, 000 個字元),字串裡的字元只會是「0」或是「1」,分別代表一串燈泡的初始狀態與目前狀態。「1」代表對應位置的燈泡為亮著的;「0」則是關閉的。

設一燈泡串為 S ……,而其中的 S 每 1 秒變換一次狀態(開變關,關變開)、 S 每 2 秒變換一次、 S 每 4 秒變換一次、…… 、S 每 2 ^ (k - 1) 秒變換一次。

求現在狀態下一秒的狀態為何?



範例輸入:
00000
00000

----------------
10111
11111


範例輸出:
10000

----------------
01111


解題思維:
其跟二進位制的數字 + 1 是一樣的想法,只是所需的二進位數字被隱藏在初始與目前狀態裡。

該數字實際上為初始狀態與目前狀態的差距。例,初始 = 11100 ,目前 = 10110 ,則其隱含的數字為 01010 (一樣表示沒有變換,不一樣表示有變換)。而根據燈泡變換的規律之定義,即為一個二進位數字。

接著就是將其加一。

加完之後的結果,再利用類似於上面的邏輯,將其轉回燈泡的狀態。並輸出即可。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作