即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

【POJ2311】Cutting Game-SG博弈

编程语言 Maxwei_wzj 19℃ 0评论

测试地址:Cutting Game


题目大意:两个人在玩游戏,游戏规则是这样的:给定一张W×H的矩形方格纸,双方轮流行动,每次行动将方格纸切割成两部分,每部分也都是完整的矩形方格纸,每一个格子都要保持完整。除第一次行动外,后面的每一次行动都只要选取一个部分进行切割。也就是说,N次行动后应该会产生N+1个部分。率先切割出一个1×1方格的人获得胜利。给定WH,问先手必胜还是必败。


做法:这一题是一种SG博弈。


很容易想到用一个数对(i,j)(ij)来表示状态,但是要构成SG博弈,需要有终止节点,可是除了(1,1)外,所有的(1,n)都是N-position(先手必胜),SG函数无法确定,那么我们怎么办呢?那么我们想一想有哪些状态是全部指向N-position的,那这些状态就是P-position(先手必败),容易发现(2,2),(2,3),(3,3)就是这样的点,那么这些点的SG函数值为0,边界就确定下来了,那么在下面计算SG函数的过程中只需要考虑切割出的矩形的最小边2的情况即可。


再来看怎么求一个状态的SG函数值。我们发现在这个游戏中,一个状态的后继状态可以用两个状态的“组合”来表示,例如(2,4)的一个后继状态可表示为{(2,2),(2,2)},注意到分成的两个状态都可以看做一个子游戏,我们把这种组合称为两个游戏的和,那么这种和的SG函数值就是分成的各个子游戏的SG函数值的异或和。那么我们就可以用后继状态的SG函数值推出当前状态的SG函数值了,问题解决。


因为共有WH个状态,每个状态最多有W+H个后继状态,所以以上算法最终的时间复杂度为O((W+H)WH),可以通过此题。


以下是本人代码:

#include 
#include 
#include 
#include 
#include 
using namespace std;
int sg[210][210],srt[40010]={0},a,b;

void calc_sg()
{
  for(int i=2;i<=200;i++)
    for(int j=i;j<=200;j++)
    {
      if (i<=3&&j<=3) {sg[i][j]=0;continue;}
      for(int k=2;2*k<=i;k++)
        srt[sg[k][j]^sg[i-k][j]]++;
      for(int k=2;2*k<=j;k++)
      {
        int i1=i,i2=i,j1=k,j2=j-k;
        if (i1>j1) swap(i1,j1);
        if (i2>j2) swap(i2,j2);
        srt[sg[i1][j1]^sg[i2][j2]]++;
      }
      for(int k=0;;k++)
        if (!srt[k]) {sg[i][j]=k;break;}
      for(int k=2;2*k<=i;k++)
        srt[sg[k][j]^sg[i-k][j]]--;
      for(int k=2;2*k<=j;k++)
      {
        int i1=i,i2=i,j1=k,j2=j-k;
        if (i1>j1) swap(i1,j1);
        if (i2>j2) swap(i2,j2);
        srt[sg[i1][j1]^sg[i2][j2]]--;
      }
    }
}

int main()
{
  calc_sg();
  while(scanf("%d%d",&a,&b)!=EOF)
  {
    if (a>b) swap(a,b);
    if (sg[a][b]==0) printf("LOSE\n");
    else printf("WIN\n");
  }

  return 0;
}

转载请注明:CodingBlog » 【POJ2311】Cutting Game-SG博弈

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情