hdu4994 博弈，按顺序拿球

题意：

给你n堆东西，两个人博弈的去拿，每次最少一个，最多是一堆，必须按顺序那，也就是只有把第一堆的东西拿完了才能去拿第二堆东西，谁先拿完谁胜，问新手是否能胜利。

思路：

显然是博弈，既然是博弈那么我们首先要干的事就是找必胜状态（或者必败状态），对于任意一组数据（先假设里面没有某一堆里面的个数是1的时候）先手肯定是必胜的，因为先手可以每一次都只给这一堆留一个，让后手去拿这一个，到最后一堆的时候一下子全部拿走，现在把有1的情况加进去，如果在开始就遇到连续的1的话就有可能失去主动权，只有开头连续个1的个数是偶数的时候最后主动权才还是自己的，中间部分有1的情况不用考虑，我们可以先手可以通过全拿完或者给后手留一个来调节自己的必胜状态，还有一个就是全是1的时候记得特判一下。

#include<stdio.h>



int main ()

{

   int t ,n ,i ,num;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d" ,&n);

      int mk = 0;

      for(i = 1 ;i <= n ;i ++)

      {

         scanf("%d" ,&num);

         if(num != 1 && !mk) mk = i;

      }

      if(!mk && n % 2 || mk && (mk - 1) % 2 == 0)

      printf("Yes\n");

      else printf("No\n");

   }

   return 0;

}

巴特西

hdu4994 博弈，按顺序拿球

最新文章

热门文章