發表新討論
#18964: 這題是難在要優化找組合的方式嗎？


k487237 (chenchen)

e358. Xor 運算(困難) -- π | From: [36.234.119.117] | 發表日期: 2019-08-18 16:11

想問一下

這題是要優化找組合的方式嗎？

還是優化XOR?

#18965: Re:這題是難在要優化找組合的方式嗎？


inversion (「我們所認識的可符香是個像天使的好女孩」之葉林 *Cries...)

e358. Xor 運算(困難) -- π | From: [49.158.83.43] | 發表日期: 2019-08-18 16:58

想問一下

這題是要優化找組合的方式嗎？

還是優化XOR?

本人的作法算是找組合的優化。可以觀察一下每個子集合生出來的 XOR 後的結果，其二進位表示法中的 0、1 數量。（把數字們由上至下排列比較好看）

會發現一些小性質，然後利用餘數的特性：先算後取餘 與 先取餘後算 的結果是同餘的。即可在 O(N) 下解決。

 

以上，希望這個提示可以幫助到您。 

#18969: Re:這題是難在要優化找組合的方式嗎？


k487237 (chenchen)

e358. Xor 運算(困難) -- π | From: [36.234.116.178] | 發表日期: 2019-08-18 19:42

想問一下

這題是要優化找組合的方式嗎？

還是優化XOR?

本人的作法算是找組合的優化。可以觀察一下每個子集合生出來的 XOR 後的結果，其二進位表示法中的 0、1 數量。（把數字們由上至下排列比較好看）

會發現一些小性質，然後利用餘數的特性：先算後取餘 與 先取餘後算 的結果是同餘的。即可在 O(N) 下解決。

 

以上，希望這個提示可以幫助到您。 

感謝，真的有提示到><

ZeroJudge Forum