首页 > 代码库 > HDU 2176 取(m堆)石子游戏 尼姆博弈
HDU 2176 取(m堆)石子游戏 尼姆博弈
题目思路:
对于尼姆博弈我们知道:op=a[1]^a[2]……a[n],若op==0先手必败
一个简单的数学公式:若op=a^b 那么:op^b=a;
对于第i堆a[i],op^a[i]的值代表其余各个堆值的亦或值。
我们现在希望将a[i]改变成某个更小的值使得,op^a[i]=0,反过来a[i]=op^0,输出它就好了
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<iostream> #include<algorithm> #define INF 0x3f3f3f3f #define MAXSIZE 1000005 using namespace std; int a[MAXSIZE]; void Game(int n) { int op=0; for(int i=1; i<=n; i++) op^=a[i]; if(op==0) { printf("No\n"); return; } else { printf("Yes\n"); for(int i=1; i<=n; i++) { op=op^a[i]; int k=op^0; if(k < a[i]) { printf("%d %d\n",a[i],k); } op=op^a[i]; } } } int main() { int n; while(scanf("%d",&n),n) { for(int i=1; i<=n; i++) scanf("%d",&a[i]); Game(n); } return 0; }
HDU 2176 取(m堆)石子游戏 尼姆博弈
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。