題目連結(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)各位大大撥冗討論。