hdu 4315 Climbing the Hill && poj 1704 Georgia and Bob阶梯博弈--尼姆博弈

﹏ヽ暗。殇╰゛Y 2023-10-11 09:38 3阅读 0赞

[参考博客][Link 1]

先讲一下Georgia and Bob：

题意：

给你一排球的位置（全部在x轴上操作），你要把他们都移动到0位置，每次至少走一步且不能超过他前面（下标小）的那个球，谁不能操作谁就输了

题解：

当n为偶数的时候，假设当每个球都相互挨着没有间隙，那么两两一组，一组中前面那个走到哪，后面那个跟上就可以了，先手必输

如果球与球之间有间隙，那么俩俩球之间的距离可以当作尼姆博弈中取石子游戏中一堆石子的石子数，用尼姆博弈判断一下就可以了

可以说先手赢不赢光和两球之间的距离有关，如果俩俩球之间的的距离都是0的话，那么谁胜利就已经知道了

当n为奇数的时候，可以先把第一个球走到终点（那么第一个球到终点的距离可以算成尼姆博弈的一堆石子），假设后面的球还是两两挨着，那么只需要用尼姆博弈判断一下第一个球怎么走就可以了

如果后面的球有间隔，那么可以把球与球之间的距离一起异或就可以了

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 
     3 #include<iostream>
     4 
     5 #include<algorithm>
     6 
     7 #include<cstring>
     8 
     9 using namespace std;
    10 
    11 int a[1010],b[1010];
    12 
    13 int main()
    14 
    15 {
    16 
    17     int t;
    18 
    19     scanf("%d",&t);
    20 
    21     while(t--)
    22 
    23     {
    24 
    25         int n;
    26 
    27         b[0]=0;
    28 
    29         scanf("%d",&n);
    30 
    31         for(int i=1; i<=n; i++)
    32 
    33             scanf("%d",&a[i]);
    34 
    35             sort(a+1,a+n+1);
    36 
    37         for(int i=1; i<=n; i++)
    38 
    39             b[i]=a[i]-a[i-1]-1;
    40 
    41         int s=0;
    42 
    43         for(int i=n; i>0; i-=2)
    44 
    45             s^=b[i];
    46 
    47         if(s==0)
    48 
    49             puts("Bob will win");
    50 
    51         else
    52 
    53             puts("Georgia will win");
    54 
    55     }
    56 
    57     return 0;
    58 
    59 }

Climbing the Hill题意：

给你n个球的位置（x坐标），每一个球可以往前（下标减小的位置）移动，但是不能超过他前面那个球的位置，除了0这个位置之外其他位置只能有一个球，看谁能把红球移到0位置，Alice先走，Bob后走，谁把红球移动到0位置，就输出那个人的名字（第k个球就是红球）

题解：

当k==1的时候先手必胜

当n为偶数，k！=1的时候，那么根据上一道题我们只需要对所有球两两分组，对每一组球的间距异或一下，如果是0，那么Bob赢，反之亦然

你可能要问了，上一道题目所有球都要到达0这个位置，这一道题红球到了就结束了，这没有区别吗？

其实是没有区别的，因为一旦每一组球的间距都变成0的话，那么一组之间的移动不改变谁获胜

举个例子如果

n==4   k==3 那么 先手怎么走你怎么走即可，你只需要把第2个棋子在要进入山顶的时候把他放在靠近山顶一步的位置。那么相当于这一步给了对方，剩下的还是对方走什么你走什么就可以。对两两之间的配对异或就行。

n==4  k==4这样的话两两配对，对方走第一个你走第二个就可以。对两两之间的配对异或就行。

当总数n为奇数时（k！=1），先吧第一个点走道终点，然后就是偶数的情况了，然后考虑怎么将他们两两挨在一起（注意不用所有点都挨在一起）

这是就是当n为偶（k！=1）计算a\[i+1\]与a\[i\]的距离，for（i+=2），这样我们就将它化成几点nim游戏问题，将a\[i+1\]与a\[i\]的距离左为每堆石子的个数

当n为奇数，就是a自己当作一个堆，然后还是将a\[i+1\]与a\[i\]的距离左为每堆石子的个数，轮到谁没有石子取了，谁就输啦！当然注意特殊情况就是当n为奇数的时候，k如果为2，前面我们说当n为奇数是直接将第一个直接走到终点，但因为第二哥是k了，所以第一个a\[i\]不能走道终点，只能走道里终点最近的位置也就是只能走a\[i\]-1步，所以就是将a\[i\]-1当作一个堆。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 using namespace std;
     6 const int maxn=1005;
     7 int v[maxn];
     8 int main()
     9 {
    10     int n,k;
    11     while(~scanf("%d%d",&n,&k))
    12     {
    13         for(int i=1;i<=n;++i)
    14         {
    15             scanf("%d",&v[i]);
    16         }
    17         if(k==1)
    18             printf("Alice\n");
    19         else
    20         {
    21             if(n%2==0)
    22             {
    23                 int flag=0;
    24                 for(int i=2;i<=n;i+=2)
    25                 {
    26                     flag^=(v[i]-v[i-1]-1);
    27                 }
    28                 if(flag==0)
    29                     printf("Bob\n");
    30                 else printf("Alice\n");
    31             }
    32             else if(n%2)
    33             {
    34                 int flag=v[1];
    35                 if(k==2) flag-=1;
    36                 for(int i=3;i<=n;i+=2)
    37                 {
    38                     flag^=(v[i]-v[i-1]-1);
    39                 }
    40                 if(flag==0)
    41                     printf("Bob\n");
    42                 else printf("Alice\n");
    43             }
    44         }
    45     }
    46     return 0;
    47 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11375703.html

[Link 1]: https://blog.csdn.net/wweiainn/article/details/43797241
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif