inaba. Ancient Duper

inaba. Ancient Duper

ZOJ3377. 远古的骗术

downloadsource code (ZOJ3377.cpp) [博弈(game theory)]

一道以永远亭的受兔Reisen和腹黑兔子Tewi为主角的博弈题。玩过天朝的同人RPG《东方夜神雪》的朋友也许还记得里面帝兔坑爹的抓硬币游戏,规则是一次拿1到3个硬币,拿最后一个的输,而每次初始硬币个数都是4k+1,于是先手必败。题目标题“远古的骗术”是东方永夜抄中帝的Last Word的Spell Card名称。这张SC正如其名,如果传统的选择下避,必死无疑(当然“正直者之死”都有人用大回转拿到了),而选择中避掌握节奏之后却是相当的轻松,附上我自己玩的replay :D 有兴趣的可以搜搜有关视频

载图 编号 213: 「エンシェントデューパー」
「Ancient Duper (远古的骗术)」
使用者: 因幡帝
Last Word — Last Word
注解: 根っからの詐欺師。人を騙す度に報復を受けるが、全く懲りてない。
耳は白く、髪の毛は黒い……。これは白兎なのかどうか判らない。

生性就是个欺诈师。虽然每次骗人都会遭到报复,但完全没有悔过之意。
白白的耳朵,黑黑的毛发……。不知道这到底算不算是白兔。

解开条件:看过符卡编号209、210和211最少一次(不必获取这些符卡)。

  • 狂気の月の兎/鈴仙・優曇華院・イナバ(れいせん・うどんげいん・イナバ)
  • 幸運の素兎/因幡てゐ(いなば てゐ)因幡帝

题目说的是一个叫AnotherPeg(笑)的游戏,规则就取自ZOJ1815. Peg Game。简单来说就是一个peg可以像跳棋一样跳过一个或连续的多个相邻peg,落到一个空位置,被跳过的peg就消失了。两个人轮流玩,没有peg可移动的一方就输了。帝兔总是欺负老实的铃仙,对于每个初始局面,她会选己先手还是让铃仙先手以保证自己必胜呢?

题目就是最基本的博弈,如果初始局面是必胜态,输出”Tewi first”;否则初始局面是必败态,输出”Reisen first”。有关博弈最基本的结论就是:如果一个局面的所有后继局面都是必胜态,包括没有后继局面的情况,那么它是必败态;否则,一个局面至少有一个后继局面是必败态,那么它是必胜态。只要利用这一基本结论,这题暴力搜索就能过,当然还可以利用hash_map优化成记忆化搜索。





©2010 Zhejiang University ACM/ICPC Team
©2010 http://watashi.ws/acm_x_touhou/

Leave a Reply