【BZOJ2066】[Poi2004]Gra

2015.08.17 20:30 Mon | 41次阅读 | 旧日oi | 固定链接 | 源码

Description

让我们考虑一个在m x 1 的板子上玩的游戏,板子被从1 到 m编号. 现在板子上有n 个棋子, 每个都严格占据板子上的一个格子. 没有一个棋子占据格子m. 每个单独的移动遵循以下原则: 移动的人选择一个棋子把它移动到比它大的格子中第一个未被占领的格子里去. 两个选手交替移动, 谁先占据格子m, 谁赢. 下面是一个例子(m = 7), 一个选手可以把2 移到 4, 把3 移到 4 或者把6 移动到 7.

我们说当前选手的移动是winning 当且仅当他移动以后令一选手无论如何都无法赢他.我们想知道先手有多少个移动是winning的.

Input

第一行有两个数m and n (2 <= m <= 109, 1 <= n <= 106, n < m) .然后接下来n个上升的整数表示初始被占据的格子编号.

题解

谁先移动到n-1谁就输了,也就是说终态是把n-2到n-m-1堆满,如果把棋子中间的空看做是石子的话就很像nim游戏了,事实上这就是阶梯nim游戏。
定义一堆棋子为连续的一段棋子,那么对于第i堆,如果i是奇数,把这堆的数量异或到答案里,否则不用异或。注意两堆之间的距离如果是1的话要特判。
输出策略的话根据nim来判断一下就好了。

我的程序

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=1000010;
using namespace std;
int n,m,a[maxn],cnt,b[maxn],ans,tot;char ch;
void read(int &x){
    for (ch=getchar();!isdigit(ch);ch=getchar());
    for (x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}
int main(){
    scanf("%d%d",&m,&n);
    for (int i=1;i<=n;i++) read(a[i]);
    if (a[n]==m-1){
        ans=1;
        for (int i=n;i&&a[i]-a[i-1]==1;i--,ans++);
        return printf("%d\n",ans),0;
    }
    a[n+1]=m-1;
    for (int i=n;i;i--)
        if (a[i+1]-a[i]==1) b[cnt]++;
        else if (a[i+1]-a[i]==2){
            if (cnt&1) ans=ans^b[cnt];
            b[++cnt]=1;
        }
        else{
            if (cnt&1) ans=ans^b[cnt];
            cnt+=3-((a[i+1]-a[i])&1),b[cnt]=1;
        }
    if (cnt&1) ans=ans^b[cnt];
    if (ans)
        for (int i=1;i<=cnt;i++)
            if ((i&1)&&(ans^b[i])<b[i]||i%2==0&&(ans^b[i-1])>b[i-1]&&(ans^b[i-1])<=b[i-1]+b[i])
                tot++;
    printf("%d\n",tot);
    return 0;
}```