题解报告:hdu 1850 Being a Good Boy in Spring Festival(尼姆博弈)
Problem Description
春节回家 你能做几天好孩子吗
寒假里尝试做做下面的事情吧
陪妈妈逛一次菜场
悄悄给爸爸买个小礼物
主动地 强烈地 要求洗一次碗
某一天早起 给爸妈用心地做回早餐
如果愿意 你还可以和爸妈说
咱们玩个小游戏吧 ACM课上学的呢~
下面是一个二人小游戏:桌子上有M堆扑克牌;每堆牌的数量分别为Ni(i=1…M);两人轮流进行;每走一步可以任意选择一堆并取走其中的任意张牌;桌子上的扑克全部取光,则游戏结束;最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负,我只想问大家:
——“先手的人如果想赢,第一步有几种选择呢?”
Input
Output
Sample Input
Sample Output
如果我们面对的是一个非奇异局势(a,b,c),要如何变为奇异局势呢?假设 a < b< c,我们只要将 c 变为 a(+)b,即可,因为有如下的运算结果: a(+)b(+)(a(+)b)=(a(+)a)(+)(b(+)b)=0(+)0=0。要将c 变为a(+)b,只要从 c中减去 c-(a(+)b)(解题重点)即可。
例1:(14,21,39),14(+)21=27,39-27=12,所以从39中拿走12个物体即可达到奇异局势(14,21,27)。
例2:(55,81,121),55(+)81=102,121-102=19,所以从121中拿走19个物品就形成了奇异局势(55,81,102)。
例3:(29,45,58),29(+)45=48,58-48=10,从58中拿走10个,变为(29,45,48)。
例4:我们来实际进行一盘比赛看看:
甲7,8,9)->(1,8,9)奇异局势
乙1,8,9)->(1,8,4)
甲1,8,4)->(1,5,4)奇异局势
乙1,5,4)->(1,4,4)
甲1,4,4)->(0,4,4)奇异局势
乙0,4,4)->(0,4,2)
甲0.4,2)->(0,2,2)奇异局势
乙0,2,2)->(0,2,1)
甲0,2,1)->(0,1,1)奇异局势
乙0,1,1)->(0,1,0)
甲0,1,0)->(0,0,0)奇异局势
甲胜。结论:①a1^a2^......^an==0,则后手必赢;②若a1^a2^...^an!=0,一定存在某个合法的移动,将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。若S=a1^a2^...^an,则一定存在某个ai,使得(S^ai<ai)一定成立,那么我们可以将ai改变成ai'=ai^k,则a1^a2^...^ai'^...^an=a1^a2^...^an^S=0,局面转化成①状态,则此时先手必赢。
证明可以参考一下这篇博文:尼姆博弈(Nimm's Game)
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
int m,ans,cnt,a[maxn];
int main()
{
while(cin>>m && m){
ans=cnt=;
for(int i=;i<m;++i){
cin>>a[i];
ans^=a[i];
}//把所有数都异或起来,存在ans里面
for(int i=;i<m;++i){
if((ans^a[i])<a[i])
cnt++;
}//这里把ans跟a[i]异或,可以得到出a[i]外所有数异或的结果。此结果若小于a[i],则只要在a[i]中取出一定的值,就能形成奇异局势,先手将必赢
cout<<cnt<<endl;
}
return ;
}
最新文章
- 如何在CentOS 7上安装Percona服务器
- [js开源组件开发]js轮播图片支持手机滑动切换
- Notepad++ Shortcuts 快捷键
- 《Python 学习手册4th》 第九章 元组、文件及其他
- vijosP1902学姐的清晨问候
- 【转】显示Ubuntu文件浏览器的地址栏--不错
- windows、linux创建子进程
- UVa 524 - Prime Ring Problem
- 比较三个 CSS 预处理器:Sass、LESS 和 Stylus(下)
- 团队作业8——第二次项目冲刺(Beta阶段)第二天
- 在AspNetCore中使用极验做行为认证
- R2CNN项目部分代码学习
- java之代码复用
- saltstack自动化运维系列④之saltstack的命令返回结果mysql数据库写入
- PHP——explode的应用(获取字符串,拆为下拉列表)
- Python3基础 str capitalize 返回新字符串,第一个字母大写
- 负margin
- PHP核心技术——反射
- 很开心! 纪念一下 ^_^ 考勤系统(weX5+echarts3.0+Baas )
- ERROR: cannot launch node of type [robot_pose_publisher/robot_pose_publisher]: robot_pose_publisher