切換
舊版
前往
大廳
主題

ZeroJudge - d265: 10165 - Stone Game 解題心得

Not In My Back Yard | 2018-09-15 23:39:33 | 巴幣 0 | 人氣 296

題目連結:

題目大意:
Jack跟Jim在玩取石頭的遊戲。遊戲一開始,有N堆石頭,每堆石頭有Pi顆石頭(i介於1~N)。Jack先開始取,每次只能選擇一堆石頭並取走當中任意數目的石頭。

現給定N和所有Pi,求Jack是否有必贏的策略。如果有,輸出「Yes」;反之,輸出「No」。

解題思維:
經典的Nim(拈)。

這題只要把所有Pi彼此取XOR運算(互斥或),如果最終結果為0,則Jack沒有必贏的策略;反之,結果 > 0, Jack一定可以贏(只要他一直走最佳的步數)。

至於為何可以這麼做,詳細原因可以參見這裡


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

創作回應

更多創作