取(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

写下你的评论吧 !

吐个槽吧,看都看了

会员登录 | 用户注册

推荐阅读

• case

  CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

  本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

  蜡笔小新   2024-12-25 17:47:23
• js

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

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

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

  在Android中排列多行小部件 - Arranging Rows of Widgets in Android

  本文介绍如何使用布局文件在Android应用中排列多行TextView和Button，使其占据屏幕的特定比例，并提供示例代码以帮助理解和实现。 ... [详细]

  蜡笔小新   2024-12-25 10:33:17
• js

  使用 NSTimer 实现倒计时功能

  本文介绍如何使用 NSTimer 实现倒计时功能，详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器，确保在指定时间间隔内执行特定任务。 ... [详细]

  蜡笔小新   2024-12-26 19:08:19
• list

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

  

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

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

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

  

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

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

  解析JSON格式文本并处理数据

  本文介绍如何使用阿里云的fastjson库解析包含时间戳、IP地址和参数等信息的JSON格式文本，并进行数据处理和保存。 ... [详细]

  蜡笔小新   2024-12-26 16:06:09
• default

  android知识杂记（三）

  andr ... [详细]

  蜡笔小新   2024-12-26 13:29:32
• js

  基于双Xilinx Kintex-7 FPGA的高性能6U VPX存储板

  VPX611是北京青翼科技推出的一款采用6U VPX架构的高性能数据存储板。该板卡搭载两片Xilinx Kintex-7系列FPGA作为主控单元，内置RAID控制器，支持多达8个mSATA盘，最大存储容量可达8TB，持续写入带宽高达3.2GB/s。 ... [详细]

  蜡笔小新   2024-12-26 11:41:58
• list

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

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

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

  并发编程：深入理解设计原理与优化

  

  本文探讨了并发编程中的关键设计原则，特别是Java内存模型（JMM）的happens-before规则及其对多线程编程的影响。文章详细介绍了DCL双重检查锁定模式的问题及解决方案，并总结了不同处理器和内存模型之间的关系，旨在为程序员提供更深入的理解和最佳实践。 ... [详细]

  蜡笔小新   2024-12-26 01:14:06
• case

  解决JAX-WS动态客户端工厂弃用问题并迁移到XFire

  

  在处理Java项目中的JAR包冲突时，我们遇到了JaxWsDynamicClientFactory被弃用的问题，并成功将其迁移到org.codehaus.xfire.client。本文详细介绍了这一过程及解决方案。 ... [详细]

  蜡笔小新   2024-12-25 18:48:34
• case

  GDI基础介绍之几何绘图

  使用GDI的一些AIP函数我们可以轻易的绘制出简 ... [详细]

  蜡笔小新   2024-12-25 18:23:37
• list

  毕业设计：基于机器学习与深度学习的垃圾邮件（短信）分类算法实现

  

  本文详细介绍了如何使用机器学习和深度学习技术对垃圾邮件和短信进行分类。内容涵盖从数据集介绍、预处理、特征提取到模型训练与评估的完整流程，并提供了具体的代码示例和实验结果。 ... [详细]

  蜡笔小新   2024-12-25 17:38:50
• match

  优化局域网SSH连接延迟问题的解决方案

  

  本文介绍了解决局域网内SSH连接到服务器时出现长时间等待问题的方法。通过调整配置和优化网络设置，可以显著缩短SSH连接的时间。 ... [详细]

  蜡笔小新   2024-12-25 11:31:48

DZ2017

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

Tags | 热门标签

• spring
• schema
• bytecode
• rsa
• emoji
• java
• email
• testing
• import
• audio
• c语言
• httpclient
• shell
• php7
• httprequest
• md5
• heatmap
• js
• default
• vbscript
• match
• usb
• yaml
• dll
• list
• web3
• runtime
• replace
• cmd
• case

RankList | 热门文章

• 1Android 基础知识再次理解
• 2编写Java TCP客户端(C#服务器)的最佳方法是什么？
• 3com.twitter.common.zookeeper.testing.ZooKeeperTestServer.createClient()方法的使用及代码示例
• 4加密你的php源代码,加密你的php源代码错误
• 5传统c语言开发,C语言系统开发
• 6博客中知识点梳理
• 7我是惠普台式电脑.怎么进入BIOS高级设置啊.我设置电脑从USB启动,一直没找到？:惠普重要设置
• 8Netty网络编程NIO基础
• 9CCF CSP 2015031 图像旋转
• 10Ubuntu 12.04下SSD的配置
• 11MyBatis笔记04分页查询、resultMap的简单使用
• 12【51nod】1006 最长公共子序列Lcs
• 13惠普hp3015打印机打印时不断进纸该怎么解决?
• 14部署 Graylog 日志系统 每天5分钟玩转 Docker 容器技术（92）
• 15我为什么参加DevOps Master俱乐部？