題目連結:
題目大意:
很接近
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。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。