hdu6139 Galaxy at War【阶梯Nim】

45 阅读 0 评论 30 点赞

我是靠谱客的博主瘦瘦树叶，最近开发中收集的这篇文章主要介绍hdu6139 Galaxy at War【阶梯Nim】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意：

一张n*m的表格上有一些格子有一些水晶球，两个人轮流进行游戏

每次选择一个有水晶球的格子，选择其中至少一个水晶球将它右移或者下移，不能出界

还有一些格子上有M(Meditations)或者P(pollutant sources)，对应的作用为
当你选择的格子上有M时，若你选择移动 t 个水晶球，那么会将2*t 个水晶球平分到可以移动到的格子内
当t个水晶被移动到有P的格子上时，t 变成 [t/2] (向下取整)

(n,m)处一定有P，(n-1,m)处一定有M

任意含M(x,y)和含P(a,b)的格子的位置关系满足式子的值为奇数
Max(|(x-a)+(y-b)|,|(x-y)-(a-b)|)

无法操作的玩家输掉比赛，给定局势，询问先手胜负
1≤n,m≤1000

解题思路：

先分析给出的位置关系的式子，可以发现所有含有M的格子和含有P的格子的奇偶关系不同。
如果没有M和P的设定，这个问题就是一个简单的阶梯博弈，只用考虑离终点的距离为奇数的点。然后打一发暴力……就A了！
冷静下来分析一波：
含有P的位置离终点的距离一定为偶数，所有对答案没有影响
含有M的位置离终点的距离一定为奇数，它每次会将一个奇数步上的 t 变成偶数步上的2*t，一定可以选择其中的 t 重新移动到奇数步上，所以对答案同样没有影响。
所以答案就是所有距离终点奇数步的格子的水晶数异或值

#include<bits/stdc++.h>
using namespace std;
int getint()
{
    int i=0,f=1;char c;
    for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());
    if(c=='-')c=getchar(),f=-1;
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
    return i*f;
}
const int N=1005;
int T,n,m,k;
int main()
{
    //freopen("lx.in","r",stdin);
    T=getint();
    while(T--)
    {
        n=getint(),m=getint();
        int ans=0,x,y,w,d;
        k=getint();
        while(k--)
        {
            x=getint(),y=getint(),w=getint(),d=n-x+m-y;
            if(d&1)ans^=w;
        }
        k=getint();
        while(k--)x=getint(),y=getint();
        k=getint();
        while(k--)x=getint(),y=getint();
        ans?puts("win"):puts("lose");
    }
    return 0;
}