ETH官方钱包

切換
舊版
前往
大廳
主題

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

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

題目連結(jié):


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


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

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

假設(shè)現(xiàn)在一次取2個(gè)石頭,而石頭堆的石頭數(shù)從1開始增加。可以發(fā)現(xiàn)石頭數(shù)每到3的倍數(shù),先手的Jack一定會(huì)輸;相同的,假設(shè)一次取4顆。可以發(fā)現(xiàn)每到5的倍數(shù)也一定會(huì)輸。

因?yàn)槿绻^數(shù)為K+1的倍數(shù),不管先手取1~K的任意數(shù)字個(gè)數(shù),一定會(huì)讓石頭落在1~K顆之間。

而Jack取完之後,即可視為Jim是先手,Jack變?yōu)獒崾郑驗(yàn)槭^數(shù)落在1~K之間,因此Jim必勝。

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



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

創(chuàng)作回應(yīng)

更多創(chuàng)作