首页 > 代码库 > 洛谷P1247 取火柴游戏 数学题 博弈论

洛谷P1247 取火柴游戏 数学题 博弈论

这题就是NIM取石子游戏,但是NIM取石子方案并不是单一的,而是有多种方案的,
现在让我们求字典序最小的方案,其实还是简单的,
作为先手,如果是必胜局面,那我们肯定第一步把所有子异或和变为零 ,这样对于对方,
这就是一个必败局面了
2、那我们来考虑怎么把局面变成必败局面呢,换句话说,怎么判断这一堆取不取呢,

假设a[ i ]不取他们的异或值为 y ,那么如果我们把a[ i ]变成 y 那么 y^y=0 就必胜了
那就只要判断 if a[ i ]>=y 就可知在这一位上改变可不可行了,要字典序最小那就
i从小到大枚举过去就行了,逐位判断下去当前位是否可行

3、然后我来证明一下为什么若当前异或值为零为必败局面(蒟蒻的证明大神请无视QwQ)
当前异或值为零,那我们改变一步肯定破坏了这个平衡,然后异或值就不为 0 了,
那么对方就可以把异或值变为 0 然后一直这么下去,直到变为0(0的异或值也为 0)

 

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 #include <iomanip>
 9 using namespace std ;
10 
11 int n,sum,pos,val,y ;
12 int a[500011] ;
13 
14 int main() 
15 {
16     scanf("%d",&n) ;
17     for(int i=1;i<=n;i++) 
18         scanf("%d",&a[ i ]) , sum^=a[ i ] ;
19     if(!sum) 
20     {
21         printf("lose\n") ;
22         return 0 ;
23     }
24     for(int i=1;i<=n;i++)  
25     {
26         y = sum^a[ i ] ;
27         if(a[ i ]<y) continue ;
28         pos = i ;
29         val = a[ i ] - y ;
30         a[ i ]-=val ;
31         break ;
32     }
33     printf("%d %d\n",val,pos) ;
34     for(int i=1;i<=n;i++) 
35         printf("%d ",a[ i ]) ;
36     return 0 ; 
37 }

 

洛谷P1247 取火柴游戏 数学题 博弈论