#18964: 這題是難在要優化找組合的方式嗎?


k487237 (chenchen)

School : 國立臺中第一高級中學
ID : 75487
IP address : [140.113.90.32]
Last Login :
2019-09-26 23:06:28
e358. Xor 運算(困難) -- π | From: [36.234.119.117] | Post Date : 2019-08-18 16:11

想問一下

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

還是優化XOR?

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


inversion (「拳願」葉林之熱血模式!)

School : 國立中央大學
ID : 43537
IP address : [49.158.83.43]
Last Login :
2019-05-15 23:34:03
e358. Xor 運算(困難) -- π | From: [49.158.83.43] | Post Date : 2019-08-18 16:58

想問一下

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

還是優化XOR?


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

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

 

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

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


k487237 (chenchen)

School : 國立臺中第一高級中學
ID : 75487
IP address : [140.113.90.32]
Last Login :
2019-09-26 23:06:28
e358. Xor 運算(困難) -- π | From: [36.234.116.178] | Post Date : 2019-08-18 19:42

想問一下

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

還是優化XOR?


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

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

 

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


感謝,真的有提示到><

 
ZeroJudge Forum