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


k487237 (chenchen)

學校 : 國立臺中第一高級中學
編號 : 75487
來源 : [140.113.90.32]
最後登入時間 ：
2020-04-15 01:15:32
e358. Xor 運算(困難) -- π | From: [36.234.119.117] | 發表日期 : 2019-08-18 16:11

想問一下

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

還是優化XOR?

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


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

學校 : 國立清華大學
編號 : 43537
來源 : [49.159.6.107]
最後登入時間 ：
2022-05-28 19:29:12
e358. Xor 運算(困難) -- π | From: [49.158.83.43] | 發表日期 : 2019-08-18 16:58

想問一下

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

還是優化XOR?

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

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

 

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

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


k487237 (chenchen)

學校 : 國立臺中第一高級中學
編號 : 75487
來源 : [140.113.90.32]
最後登入時間 ：
2020-04-15 01:15:32
e358. Xor 運算(困難) -- π | From: [36.234.116.178] | 發表日期 : 2019-08-18 19:42

想問一下

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

還是優化XOR?

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

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

 

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

感謝，真的有提示到><

 
ZeroJudge Forum