J Cunning Friends

三个人的nim博弈有趣有趣
我的思考过程如下

  1. 全是1的时候，n如果能整除3，那么必输，否则必赢

  2. 只有一个不是1的时候 ，如果n%3 == 0 ，就把不是1的取成1，这样对于第二个人必输，如果 n%3 == 1||n%3 == 2 取走不是1的一堆必赢

  3. 如果有小于n-2 个1，那么根据nim博弈，后面两个人总是能轻松的转移到任何状态，这时候 第一个人必输

  4. 通过上面的讨论我们n%3 是一个必输态，我们必须避免这种状态

  5. 如果有n-2个1，剩下至少有一个2，

  6. 如果 n% 3 == 0 ，我们把 最后一堆取的只剩下一个，这样剩下的状态等价于 n % 3 == 1,如果 取走一个2的堆或这一个1的堆，都不能改变n%3 == 1，如果取走2的堆里面的一个，那么这样就是 n%3 == 2 的状态还是必赢如果 n% 3 == 0 ，我们把 最后一堆取的只剩下一个，这样剩下的状态等价于 n % 3 == 1,如果 取走一个2的堆或这一个1的堆，都不能改变n%3 == 1，如果取走2的堆里面的一个，那么这样就是 n%3 == 2 的状态还是必赢

  7. 如果 n% 3 == 1,那么我们把最后一个取完，这样剩下两个人可以把状态改变成 n%3 == 2，或者保持n% 3==1这样都是必胜态

  8. 如果 n% 3 == 2，无论怎么取，剩下一个人都可以转化成n%3 == 0

代码参考

1.全是1时候  n%3 == 2||n%3==1都是必胜
9. 只有一个不是1的时候 必胜
10. 1,1,2,2 
 bool solve(int a,int b,int n){
    if(a < n-2) return 0;
    if(a == n)
        return (n%3 != 0);
    if(a == n-1) return 1;
    if(n%3 != 2&& b) return 1;
    return 0; 
}
int main(void)
{
    int n;
    int a;
    cin>>n;
    int cnt1 = 0;
    int cnt2 = 0;
    rep(i,1,n+1){
        scanf("%d",&a);
        if(a == 1)  cnt1++;
        else if(a == 2) cnt2++;
    }
    if(solve(cnt1,cnt2,n))
        puts("Win");
    else
        puts("Lose");

   return 0;
}