2012年3月30日 星期五

tioj 1616 快樂植樹遊戲

其實這是一題痛苦的質數遊戲
一看之下就覺得是game theory的題目
好像是先找到斷點,再用NP規則回推就可以知道了
但想了想,發現會找不到斷點OoO
怎麼辦勒!?這時妁豔神出現把我捏爆了XD

重新敘述一下題目,第一個戳 0 ,接下來輪流戳一個比前一個數大的質數,但是之間的差不能大於K,問不能再戳下一個點的是先手還是後手。(理想情況下)

其實這題要換一個想法,因為先手一定要戳 0 ,所以一點先手的優惠都沒有,其實後手比較像先手,這時我們就來假設在很遙遠的某個點是斷點,種在那裡的人就 win 了,但這要是能夠踩在那裡的人才是贏的,這樣我們就來看,會不會在某個數以後,先手根本就踩不到任何一個點(或是說他沒辦法選擇,若某點是win點,後手必定可以先踩到),只能任後手宰割,於是我就記錄,先手可以踩到的範圍(或說先手可以選擇比後手早踩到的範圍),如果到了後面發現,先手可以踩到的範圍是零,那就代表先手輸定了,但是其實有些情況你會發現,找不到讓他範圍變零,所以我假設這些情況先手會贏,而這種情況只有十種。所以其實我還是用猜的,只是就剛好也AC了XD

http://codepad.org/55dRfIfj

沒有留言:

張貼留言