寒假训练营 寒冬信使 博弈论
寒冬信使2
https://ac.nowcoder.com/acm/contest/23481/H
解题思路： 对于先手 对一个状态而言，如果一步能到达的状态里面有一个是必败态，那么该状态就是必胜态了。反之，如果一步能到达的状态里全是必胜态，那么该状态就是必败态。 实现： 利用二级制，把白色格子记为1，黑色格子记为0，进行压缩，然后枚举。 1，开一个2^11次方的数组，f[x] = 1表示x状态必胜，反之必败。 2，如何进行枚举：利用下一步肯定比这一步小这个性质，直接从小到大枚举。 容易想到0肯定是必败态，那么从1开始枚举，首先如果是奇数（即第一个格子是白色）先特判，之后对1的位置进行枚举就行。
查看23道真题和解析