其實這是一題痛苦的質數遊戲
一看之下就覺得是game theory的題目
好像是先找到斷點，再用NP規則回推就可以知道了
但想了想，發現會找不到斷點OoO
怎麼辦勒！？這時妁豔神出現把我捏爆了XD
重新敘述一下題目，第一個戳 0 ，接下來輪流戳一個比前一個數大的質數，但是之間的差不能大於K，問不能再戳下一個點的是先手還是後手。（理想情況下）
其實這題要換一個想法，因為先手一定要戳 0 ，所以一點先手的優惠都沒有，其實後手比較像先手，這時我們就來假設在很遙遠的某個點是斷點，種在那裡的人就 win 了，但這要是能夠踩在那裡的人才是贏的，這樣我們就來看，會不會在某個數以後，先手根本就踩不到任何一個點（或是說他沒辦法選擇，若某點是win點，後手必定可以先踩到），只能任後手宰割，於是我就記錄，先手可以踩到的範圍（或說先手可以選擇比後手早踩到的範圍），如果到了後面發現，先手可以踩到的範圍是零，那就代表先手輸定了，但是其實有些情況你會發現，找不到讓他範圍變零，所以我假設這些情況先手會贏，而這種情況只有十種。所以其實我還是用猜的，只是就剛好也AC了XD
http://codepad.org/55dRfIfj
沒有留言:
張貼留言