洛谷1288 取数游戏II 博弈论-白红宇

洛谷1288 取数游戏II 博弈论

阅读量：5833 次

发布时间：2019-06-18

本文共 1109 字，大约阅读时间需要 3 分钟。

洛谷1288 取数游戏II 博弈论

最优策略一定是你一步把值走完，然后我再走完，这样不给别人留后路

然后这样走只要自己从左走或者从右走其中有一个有奇数步可走，则说明是必胜局

如果都是只能走偶数步的，就是必败局、

另一个题解

首先，对于一条链a1,a2,a3,a4......0 如果是偶数条边，那么现手一定赢，因为他每一次都只

用把后面一条取完，例如

5 4 3 6 5 0

先手取完5，后手没法回到前一个位置，而无论接下来后手去多少，先手继续取完3，再然后取

完5，后手没办法再去，先手赢。就这样，如果从起点到第一个出现0的地方一共有偶数条边，先

手可以一步一步将后手被迫向前逼近，直到无法移动（由于是环，还应该考虑向后逼近）。

同样的，如果这有奇数个，那么先手第一步无论怎么取，都将自己置于一个必败状态（此时对于

后手来说边数变成偶数），就一定没有必胜状态

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 using namespace std ; 10 11 const int maxn = 21 ; 12 int n,x ; 13 int a[maxn] ; 14 15 int main() 16 {17 scanf("%d",&n) ; 18 for(int i=1;i<=n;i++) scanf("%d",&a[ i ]) ; 19 x = 0 ; 20 for(int i=1;i<=n;i++) 21 if(a[ i ]) x++ ;22 else break ; 23 if(x&1) 24 {25 printf("YES\n") ; 26 return 0 ;27 } 28 x = 0 ; 29 for(int i=n;i>=1;i--) 30 if(a[ i ]) x++ ;31 else break ; 32 if(x&1) 33 {34 printf("YES\n") ; 35 return 0 ; 36 }37 printf("NO\n") ; 38 return 0 ; 39 }