題目連結:
題目大意:
Jack跟Jim在玩取石頭的遊戲。遊戲一開始,有N堆石頭,每堆石頭有Pi顆石頭(i介於1~N)。Jack先開始取,每次只能選擇一堆石頭並取走當中任意數目的石頭。
現給定N和所有Pi,求Jack是否有必贏的策略。如果有,輸出「Yes」;反之,輸出「No」。
解題思維:
經典的Nim(拈)。
這題只要把所有Pi彼此取XOR運算(互斥或),如果最終結果為0,則Jack沒有必贏的策略;反之,結果 > 0, Jack一定可以贏(只要他一直走最佳的步數)。
至於為何可以這麼做,詳細原因可以參見
這裡。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。