hdu 3389 阶梯博弈

题意是盒子的编号为a,b的,要求a>b,(a+b)%2==1,(a+b)%3==0,容易看出1,3,4的位置不能动, 每个位置移到下个位置后奇偶性改变,模3结果也有固定变化(0->0,1->2,2->1),比如模3为1的奇数可以移到模3为2的偶数或者再移到模3为1的奇数,但最终只可能移到模3为1的奇数,也就是1(因为1、3、4中没有模3为2的),其他类型的数的最终位置也可如此得到。由于移到的最终位置是固定的,本身的奇偶性也是固定的,那么移动步数的奇偶性也是固定的。

利用此性质容易求出若最终可移动步数为奇数步则((i%3==0 && i%2==0) || i%3 == 2)

 也容易得出移动位置是偶数步的位置上的牌数是无关紧要的:因为不论对方将偶数步位置上的牌作如何操作,我都可以把他移动的牌再往后移动一步。也就是说偶数步上的位置的牌我可以保证两个人对其的操作数是偶数次,从而不影响到奇数步位置上的牌的状态。

那奇数步位置上的牌呢?临时再来个无关紧要的结论:奇数步位置上的牌可以直接移到最终位置

那么就相当于奇数步位置上的石子进行nim博弈

然后看代码

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;
int main()
{
    int T;
    int n;
    int a;
    scanf("%d",&T);
    int iCase = 0;
    while(T--)
    {
        iCase++;
        scanf("%d",&n);
        int sum = 0;
        for(int i = 1;i <= n;i++)
        {
            scanf("%d",&a);
            if((i%3==0 && i%2==0) || i%3 == 2)
                sum ^= a;
        }
        if(sum)printf("Case %d: Alice
",iCase);
        else printf("Case %d: Bob
",iCase);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/shimu/p/5700398.html