题目地址：HDU 2147
又是一道NP状态转换的巴什博弈。这题根据NP状态转移最好画个表格，规律就很直观了。
博弈么，从左下角往前推：
P→到达该点后，下一个人必败。
N→到达该点后，下一个人必胜。
显然，最左下角的点是P。
然后根据经过一步操作可到达必败状态的都是必胜状态，下一步操作都是必胜状态，那么这步操作时必败状态的原则一步步的去画表格就可以了。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
由于1,6和2,7位置只能向1,7位置移动，所以1,6与2,7为N。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
P |
N |
|
|
|
|
|
同理，第1列和第7行就可以填充完毕。
|
P |
|
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
P |
N |
P |
N |
P |
N |
P |
|
P |
|
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
|
N |
N |
|
|
|
|
|
|
P |
N |
P |
N |
P |
N |
P |
|
P |
N |
P |
N |
P |
N |
P |
|
N |
N |
N |
N |
N |
N |
N |
|
P |
N |
P |
N |
P |
N |
P |
|
N |
N |
N |
N |
N |
N |
N |
|
P |
N |
P |
N |
P |
N |
P |
|
N |
N |
N |
N |
N |
N |
N |
|
P |
N |
P |
N |
P |
N |
P |
此图填完，可以找到规律：
只有在行列数均为奇数时，为P，其他情况均为N。
所以此题：若行列均为奇数则Kiki无法赢得比赛。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
