我们直接分析吧
Nim博弈中如果规定最后取光者输，情况是怎样的？ 初看起来问题要复杂很多（因为不能主动拿了，而要“躲着”拿，以免拿到最后一个物品），但对于Nim游戏来说，几乎是一样的：首先按照普通规则一样的策略进行，直到恰好有一个物品数大于1的堆x。在这样的情况下，只需要把堆x中的物品拿得只剩1个物品或者拿完，让对手面临奇数堆物品，这奇数堆物品每堆恰好1个物品。这样的状态显然是必败的。由于你每次操作后需要保证Nim和为0，因此不可能在你操作后首次出现“恰好有一个物品数大于1的堆”。
所以我们得出了这样的结论 先手必胜当且仅当
所有堆的石子数都为 1 且游戏的 SG 值为 0；有些堆的石子数大于 1 且游戏的 SG 值不为 0。进而贾志豪在论文中提出了针对Anti-SG的SJ定理
对于任意一个 Anti-SG 游戏 如果我们规定当局面中所有的单一游戏的 SG 值为 0 时，游戏结束 则先手必胜当且仅当
游戏的 SG 函数不为 0 且游戏中某个单一游戏的 SG 函数大于 1 游戏的 SG 函数为 0 且游戏中没有单一游戏的 SG 函数大于 1。注意当局面中所有的单一游戏的 SG 值为 0 时，游戏结束这一前提内容 但他太苛刻了 我见过只有nim是符合的吧 网上有个广为流传的ANTI-SG题 HDU 3590 PP and QQ 但这一做法是错的 这一游戏根本没有满足那个强的前提条件 手撸一组数据就叉掉了
1 5 1 2 2 3 1 4 4 5
但发现原来毕姥爷早就有留言了
扯远了 上1022的代码
#include<cstdio>using namespace std;int main(){ int T,n,f,a,s; scanf("%d",&T); while (T--){ scanf("%d",&n); f=s=0; for (int i=1;i<=n;i++) scanf("%d",&a),s^=a,f|=a>1; if ((!f && n%2==1) || (f && s==0)) PRintf("Brother/n"); else printf("John/n"); } return 0;}新闻热点
疑难解答
