b066. 熵用魔法 (Entropy Magic)

內容

作為一個物理大師，小Y盡力想避免這個宇宙產生「熱寂」。他從小P那邊學到了一個可以降低熵的魔法，希望能夠拯救整個世界。但是這個魔法的使用存在某些限制，為了簡單起見，我們將整個宇宙視為一個長度為N 的序列$a_1, a_2,a_3,
,a_N$，每一個元素都是0或1，這個魔法可以選擇一個長度為3並非全部都是0或1的區間 $a_i, a_{i+1}, a_{i+2}(1 ≤i≤
N-2）$，之後將其換成 $a_{i+1} \oplus a_{i+2},a_i \oplus a_{i+2}, a_{i} \oplus a_{i+1} $

$\oplus$ 代表 XOR

小Y想問你是否可以使用這個魔法將整個序列變成0，把熵降到最低。可以證明如果能用魔法將整個序列變成0，那麼必定可以使用 2N 次以内的魔法就達成，因此假如可以用這個魔法將整個序列變成0，請輸出一個長度不超過 2N 的操作序列如果有很多個操作序列滿足條件，請輸出任意一個。

輸入說明

輸人的第一行包含一正整數N，代表小Y將整個宇宙視為一個長度為N的序列。
下一行包含一個長度為N的序列$a_1, a_2, ..., a_N$，代表宇宙被轉換成的序列

$N ≤ 10^6$

輸出說明

第一行輸出 “YES” 或“NO” 代表是否可以使用這個魔法將整個序列變成 0。

如果是 “YES” 的話，第二行輸出一個整數M，代表你可以使用恰好M次魔法將整個序列變成0。

第三行請輸出 M 個正整數b，代表第i個操作會對 $a_i, a_{i+1}, a_{i+2}$ 使用魔法。如果有多種使用魔法的方式可以滿足條件，請輸出任意一個。若不需任何魔法即可滿足，則輸出0。
如果 M ＞2N 或是依序使用這些魔法並不會讓整個序列變成 0，你將會獲得 WA

範例輸入 #1

5
0 0 0 0 0

範例輸出 #1

YES
0

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 1.0s , <10M
公開測資點#1 (10%): 1.0s , <10M
公開測資點#2 (10%): 1.0s , <10M
公開測資點#3 (10%): 1.0s , <10M
公開測資點#4 (10%): 1.0s , <10M
公開測資點#5 (10%): 1.0s , <10M
公開測資點#6 (10%): 1.0s , <10M
公開測資點#7 (10%): 1.0s , <1M
公開測資點#8 (10%): 1.0s , <1M
公開測資點#9 (10%): 1.0s , <1K

提示：

標籤:

ytp

出處:

ytp_2021 [管理者：

Ching367436 (Ching367436)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」