HDU 3389 阶梯博弈

题目大意:

盒子的序号为1~n,每次从序号A>B的盒子,且(A+B)%2=1,(A+B)%3=0,从A中取任意个物品放入B中,知道不能操作

很容易能看出的是只能是(A+B)%6==3的时候成立

也就是 i % 6 =0 与 i % 6 = 3

i % 6 = 1 与 i % 6 = 2

i % 6 = 4 与 i % 6 = 5

三种情况

也就是说把整个大游戏分解成了3个小型的nim游戏,每一个小型游戏之间互不影响,所以sg值3个游戏异或一下即可

每个小的游戏都可以看作是 前一种类型的盒子到另一种盒子交错的阶梯

这里可以这样判断哪个属于奇数位阶梯还是偶数位阶梯

比如第一种游戏 我从 i % 6 = 3 中取物品到 i % 6 = 0 中 ,那么这里 i % 6 = 0 中  i 最小为6,也就是交替到最后,始终能够找到它前面还有一个 i % 6 = 3 (最小为3)的梯子可以重新还回来刚才给的物品,所以这里 i % 6 = 0 为奇数阶梯, i % 6 = 3 对游戏不产生影响

同理可证  i % 6 = 2 和  i % 6 = 5 分别是它们那个小型游戏中的奇数位阶梯

奇偶阶梯判好了,再来看sg值,对于一个 奇数位阶梯上含有a[i]个数, 那从中可以取任意个到下一个偶数位阶梯,所能剩下的有 0~a[i]-1 a[i]种情况

从前往后推,0对应结束态 sg[0]=0 , 1可到达0,所以sg[1]=1,2可到达0,1,所以sg[2] = 2 。。。。那么sg[a[i]]=a[i]

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int main()
{
  //  freopen("a.in" , "r" , stdin);
    int T,cas=0;
    scanf("%d" , &T);
    while(T--)
    {
        int n,a;
        int ans=0;
        scanf("%d" , &n);
        for(int i=1 ; i<=n ; i++){
            scanf("%d",&a);
            if(i%6==0||i%6==2||i%6==5)
                ans^=a;
        }
        if(ans) printf("Case %d: Alice
" , ++cas);
        else printf("Case %d: Bob
" , ++cas);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/CSU3901130321/p/4257041.html