HDU 2176(Nim博弈)

取(m堆)石子游戏

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 975 Accepted Submission(s): 582

Problem Description

m堆石子,两人轮流取.只能在1堆中取.取完者胜.先取者负输出No.先取者胜输出Yes,然后输出怎样取子.例如5堆 5,7,8,9,10先取者胜,先取者第1次取时可以从有8个的那一堆取走7个剩下1个,也可以从有9个的中那一堆取走9个剩下0个,也可以从有10个的中那一堆取走7个剩下3个.

Input

输入有多组.每组第1行是m,m<=200000. 后面m个非零正整数.m=0退出.

Output

先取者负输出No.先取者胜输出Yes,然后输出先取者第1次取子的所有方法.如果从有a个石子的堆中取若干个后剩下b个后会胜就输出a b.参看Sample Output.

Sample Input

2 45 45 3 3 6 9 5 5 7 8 9 10 0

Sample Output

No Yes 9 5 Yes 8 1 9 0 10 3

http://hi.baidu.com/sphinx1990/item/b2f7160d895aff64d45a119e

时间： 2024-09-26 13:37:32

HDU 2176(Nim博弈)的相关文章

poj 2068 NIM 博弈+dp

博弈题关键要把握3个基本属性: 1.确定末状态N,P状态 2.一定存在至少一种抉择使N->P 3.所有P->N 实现形式随意,这题是用记忆化搜索来实现 /* author:jxy lang:C/C++ university:China,Xidian University **If you need to reprint,please indicate the source** */ #include <iostream> #

POJ 1704

这题好像nim博弈的变形主要在于找到变成奇异局势的方式,那么可以想到最近的两个棋子移动到相邻如果n为奇数那么把0点也看作是一个棋子如果变完后那么后手只需要模仿先手就可以赢了所以之前是nim博弈 #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int main() { int t,n,a[1010]; scan

hdu 1849 （尼姆博弈）

http://acm.hdu.edu.cn/showproblem.php?pid=1849 简单的尼姆博弈: 代码如下: #include <iostream> #include <cstdio> using namespace std; int main() { int m,n,t; while(cin>>m,m) { int ans=0; for(int i=0; i<m; i++) { cin>>n; ans^=n; } if(ans==0)

hdu 1850 博弈入门

nim变形题,要求是第一种有多少种胜法,其实就是求去掉某一堆里的一些牌,后手有没有必输测量,也就是异或为0 /* author:jxy lang:C/C++ university:China,Xidian University **If you need to reprint,please indicate the source** */ #include <iostream> #include <cstdio> #include <cstdlib> #inclu

HDU 1846(巴什博弈)

Brave Game Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4050 Accepted Submission(s): 2644 Problem Description 十年前读大学的时候,中国每年都要从国外引进一些电影大片,其中有一部电影就叫<勇敢者的游戏>(英文名称:Zathura),一直到现在,我依然对于电影中的部

HDU 1538 A Puzzle for Pirates：博弈&amp;海盗分赃问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Description A bunch of pirates have gotten their hands on a hoard of gold pieces and wish to divide the loot. They are democratic pirates in their own way, and i

hdu 1079 Calendar Game 博弈

题目就是寻找有无必胜策略一开始看错题意了,一直想用dp预处理下,结果发现就是简单的逻辑判断. 无论向后一天还是向后一月,均会改变奇偶性,除了4.30,9.30,11.30和非润年的2.28,在几个特殊日期中向后可能会改变奇偶性. 目标日期为11.4,偶数. 因此,无特殊日期时奇数必胜而如果先手是偶数,其必然不会进入特殊日期,因为一旦奇偶改变,必胜变为必输-- 如果先手为奇数,因为不存在必改变奇偶性的日期,所以进入特殊日期后也无法改变

hdu 1527

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1527 hint:威佐夫博弈基本类似于模板 #include <iostream> #include <cmath> #include <cstdio> using namespace std; const double q = (1 + sqrt(5.0)) / 2.0; // 黄金分割数 int Wythoff(int a, int b) { if (a > b)

hdu 2147 kiki&#39;s game

http://acm.hdu.edu.cn/showproblem.php?pid=2147 这是一个巴什博弈的题,当两个数至少有一个数是偶数先手必胜代码如下: #include <iostream> #include <cstdio> using namespace std; int main() { int m,n; while(cin>>m>>n,m,n) { if(m%2 && n%2) puts("What a pity