取(m堆)石子游戏

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

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

 

 

Author

Zhousc

 

 

Source

ECJTU 2008 Summer Contest

 

 

通常的Nim游戏的定义是这样的：

有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

 

结论：

必败状态：a1^a2^......^an=0

必胜状态：a1^a2^.......^an=k (其中k不为零)

 

证明：

terminal position只有一个，就是全0，异或仍然是0。

 

对于某个局面(a1,a2,...,an)，若a1^a2^...^an!=0，一定存在某个合法的移动，将ai改变成ai‘后满足a1^a2^...^ai‘^...^an=0。不妨设a1^a2^...^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k

 

对于某个局面(a1,a2,...,an)，若a1^a2^...^an=0，一定不存在某个合法的移动，将ai改变成ai‘后满足a1^a2^...^ai‘^...^an=0。因为异或运算满足消去率，由a1^a2^...^an=a1^a2^...^ai‘^...^an可以得到ai=ai‘。所以将ai改变成ai‘不是一个合法的移动

 

所以在这道题中如果当前是必胜的话，那么就要下一个移动的人必败，所以就要改变一个ai变成ai‘使得原本的a1^...ai^...^an!=0变成a1^...ai‘...^an=0

可以利用ai^k

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL __int64
using namespace std;
const int MAXN=200000+50;
const int INF=0x3f3f3f3f;
const double EPS=1e-9;
int dir4[][2]={{0,1},{1,0},{0,-1},{-1,0}};
int dir8[][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
int dir_8[][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
int a[MAXN];
int main()
{
int n;
while(scanf("%d",&n) && n)
{
int sum=0;
for(int i=0;i)
{
scanf("%d",&a[i]);
sum^=a[i];
}
if(sum==0) printf("No\n");
else
{
printf("Yes\n");
for(int i=0;i)
{
int s=sum^a[i];
if(s<a[i])
printf("%d %d\n",a[i],s);
}
}
}
return 0;
}

View Code

 

• android
• asp.net
• ios
• php
• jsp
• 数据库
• java
• io
• windows

写下你的评论吧 !

吐个槽吧,看都看了

会员登录 | 用户注册

推荐阅读

• text

  Android LED 数字字体的应用与实现

  

  本文介绍了一种适用于 Android 应用的 LED 数字字体（digital font），并详细描述了其在 UI 设计中的应用场景及其实现方法。这种字体常用于视频、广告倒计时等场景，能够增强视觉效果。 ... [详细]

  蜡笔小新   2024-12-27 10:34:22
• text

  优化ListView性能

  

  本文深入探讨了如何通过多种技术手段优化ListView的性能，包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]

  蜡笔小新   2024-12-28 10:36:30
• format

  移动 UI 设计基础：打造简洁高效的用户界面

  本章将深入探讨移动 UI 设计的核心原则，帮助开发者构建简洁、高效且用户友好的界面。通过学习设计规则和用户体验优化技巧，您将能够创建出既美观又实用的移动应用。 ... [详细]

  蜡笔小新   2024-12-27 08:43:40
• text

  RecyclerView初步学习(一)

  

  RecyclerView初步学习(一)ReCyclerView提供了一种插件式的编程模式，除了提供ViewHolder缓存模式，还可以自定义动画，分割符，布局样式，相比于传统的ListVi ... [详细]

  蜡笔小新   2024-12-26 20:24:01
• text

  扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

  

  学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

  蜡笔小新   2024-12-26 20:04:36
• hash

  2023年京东Android面试真题解析与经验分享

  

  本文由一位拥有6年Android开发经验的工程师撰写，详细解析了京东面试中常见的技术问题。涵盖引用传递、Handler机制、ListView优化、多线程控制及ANR处理等核心知识点。 ... [详细]

  蜡笔小新   2024-12-26 17:45:48
• hash

  从 .NET 转 Java 的自学之路：IO 流基础篇

  

  本文详细介绍了 Java 中的 IO 流，包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据，并结合编码机制确保字符数据的正确读写。同时，文中还涵盖了装饰设计模式的应用，以及多种常见的 IO 操作实例。 ... [详细]

  蜡笔小新   2024-12-26 17:37:25
• format

  Python学习笔记：使用pydoc工具查询文档

  本文介绍了在Windows环境下使用pydoc工具的方法，并详细解释了如何通过命令行和浏览器查看Python内置函数的文档。此外，还提供了关于raw_input和open函数的具体用法和功能说明。 ... [详细]

  蜡笔小新   2024-12-26 17:05:56
• search

  深入理解Android中的ADB Shell Input命令：模拟滑动、按键和点击事件

  在维护公司项目时，发现按下手机的某个物理按键后会激活相应的服务，并在屏幕上模拟点击特定坐标点。本文详细介绍了如何使用ADB Shell Input命令来模拟各种输入事件，包括滑动、按键和点击等。 ... [详细]

  蜡笔小新   2024-12-26 13:43:24
• list

  Android 模拟用户交互：点击与滑动操作的实现

  本文介绍如何在 Android 中通过代码模拟用户的点击和滑动操作，包括参数说明、事件生成及处理逻辑。详细解析了视图（View）对象、坐标偏移量以及不同类型的滑动方式。 ... [详细]

  蜡笔小新   2024-12-28 12:12:22
• char

  深入理解KMP算法中的next数组：北大OJ 2406题解

  本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

  蜡笔小新   2024-12-28 11:30:01
• text

  深入解析Android自定义View面试题

  

  本文探讨了Android Launcher开发中自定义View的重要性，并通过一道经典的面试题，帮助开发者更好地理解自定义View的实现细节。文章不仅涵盖了基础知识，还提供了实际操作建议。 ... [详细]

  蜡笔小新   2024-12-28 11:15:04
• text

  Android 渐变圆环加载控件实现

  

  本文介绍了如何在 Android 中创建一个自定义的渐变圆环加载控件，该控件已在多个知名应用中使用。我们将详细探讨其工作原理和实现方法。 ... [详细]

  蜡笔小新   2024-12-27 13:34:19
• require

  XNA 3.0 游戏编程：从 XML 文件加载数据

  

  本文介绍如何在 XNA 3.0 游戏项目中从 XML 文件加载数据。我们将探讨如何将 XML 数据序列化为二进制文件，并通过内容管道加载到游戏中。此外，还会涉及自定义类型读取器和写入器的实现。 ... [详细]

  蜡笔小新   2024-12-27 11:39:44
• require

  从零构建递归神经网络：仅用NumPy实现

  尽管使用TensorFlow和PyTorch等成熟框架可以显著降低实现递归神经网络（RNN）的门槛，但对于初学者来说，理解其底层原理至关重要。本文将引导您使用NumPy从头构建一个用于自然语言处理（NLP）的RNN模型。 ... [详细]

  蜡笔小新   2024-12-26 11:29:15

DZ2017

这个家伙很懒，什么也没留下！

Tags | 热门标签

• nodejs
• list
• datetime
• char
• bitmap
• regex
• php7
• sum
• go
• php5
• java
• erlang
• vba
• chat
• runtime
• tags
• hash
• python3
• text
• controller
• hashtable
• foreach
• format
• search
• httpclient
• split
• require
• c语言
• jar
• node.js

RankList | 热门文章

• 1MySQL8的数据库，8.0.11驱动的逆向工程的坑的解决方法
• 2mysql环形复制加HA_MySQL互为主从复制实现HA功能
• 3iqooneo3 如何不用vivo账号下载外部应用_vivo新推黄金会员九折特权，快来看看你可以省多少？...
• 4Spark+Kafka+WebSocket+eCharts实时分析完全记录（4）
• 5AppStore 1.0.24 版本被拒原因分析
• 6remote 移除_remote模块的使用(四)
• 7struts2 中JSON的弹出窗口
• 82、标题、段落
• 9在线英语词典
• 10【微信小程序】view顶部固定或底部固定 + scrollview中的元素view也可以使用position:fixed;固定选中元素位置...
• 11Telnet命令检测远程主机上的端口是否开启
• 12课程资源共享平台功能规格说明（第四组）
• 13如何使用ConvertToXml和SelectXml加载或读取XML文件？
• 14【Azure 应用服务】探索在Azure上设置禁止任何人访问App Service的默认域名(Default URL)
• 15抖音小尼姑她走上独木桥歌名叫什么?歌曲孽海记完整版介绍