首页 > 代码库 > 洛谷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 取火柴游戏 数学题 博弈论
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。