切換
舊版
前往
大廳
主題

ZeroJudge - d246: Stone Game(跟d265不同喔) 解題心得

Not In My Back Yard | 2018-09-17 19:34:27 | 巴幣 0 | 人氣 153

題目連結:


題目大意:
很接近d265。但是這一題,Jack和Jim每一次取石頭不能超過K顆(K ≦ 200)。其他變數的範圍一致。


解題思維:
d265的作法確實差不了多少。只是輸入每一堆石頭時,要先把現在輸入的那一堆取K+1的餘數,再去做XOR運算。

至於為何是取K+1的餘數,可以看單堆石頭的情況就好。

假設現在一次取2個石頭,而石頭堆的石頭數從1開始增加。可以發現石頭數每到3的倍數,先手的Jack一定會輸;相同的,假設一次取4顆。可以發現每到5的倍數也一定會輸。

因為如果石頭數為K+1的倍數,不管先手取1~K的任意數字個數,一定會讓石頭落在1~K顆之間。

而Jack取完之後,即可視為Jim是先手,Jack變為後手,而正因為石頭數落在1~K之間,因此Jim必勝。

因此每堆石頭都要取K+1的餘數,再做XOR。



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

創作回應

更多創作