博弈问题总集：Staircase Nim“编程题”

这一关我们上楼梯玩。。。

阶梯博弈是这样一个模型：有一个n层的台阶，每个台阶上都放有一定数量的石子。每次每个玩家可以选取某一层上任意数量的石子移动到下一层，不能操作的人输。

嗯这个问题看起来很复杂？我们先考虑简单的，显然石子在第一层推下去的话相当于是没有了。那么我们假设所有的石子都在第一层，那这是一个先手必胜态。如果石子都在第二层呢？可以这样考虑，先手每次把多少石头推到第一层，后手就把先手推下来的石头推下去，那这就是一个先手必败态

那我们就会发现一个问题啦，偶数层的楼梯算是一个中转，用来维护奇数层石子数量不变。只有奇数层的石子个数会对胜负产生影响，当前玩家没有必要维护偶数层的状态。因为有偶数层作为中转，所以先手和后手都可以维护奇数层数目不变，即维护自己的必胜态。只考虑奇数层求出SG值即可。

1、

[HDU5996] dingyeye loves stone

题解：

这就是最简单的模型转换啦，因为每次只能把当前节点的石子移动到它的父节点上，这和台阶的模型是类似的。注意台阶的第一层还能往下推一次，但这里推到根节点就已经GG了，所以根节点相当于偶数层（因为作用在这一层上也没什么用嘛）

代码：

#include 
#include 
using namespace std;
const int N=100005;
int tot,nxt[N],point[N],v[N],k,a[N];
void addline(int x,int y){++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}
void dfs(int x,int D)
{
    if (D) k^=a[x];
    for (int i=point[x];i;i=nxt[i]) 
      dfs(v[i],!D);
}
int main()
{
    int T,n,x;
    scanf("%d",&T);
    while (T--)
    {
        k=0; tot=0; memset(point,0,sizeof(point));
        scanf("%d",&n);
        for (int i=2;i<=n;i++)
        {
            scanf("%d",&x);x++;
            addline(x,i);
        }
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        dfs(1,0);
        if (!k) printf("lose\n");else printf("win\n");
    }
}

2、

[HDU4315] Climbing the Hill

题解：

显然为了让国王到达，他前面的所有人必须都到了

代码：

to be continued~