热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HDOJ1730NorthcottGame(nim博弈)

Northcott Game Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) T

Northcott Game
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3454    Accepted Submission(s): 1508





Problem Description

Tom和Jerry正在玩一种Northcott游戏,可是Tom老是输,因此他怀疑这个游戏是不是有某种必胜策略,郁闷的Tom现在向你求救了,你能帮帮他么?
游戏规则是这样的:
  如图所示,游戏在一个n行m列(1 ≤ n ≤ 1000且2 ≤ m ≤ 100)的棋盘上进行,每行有一个黑子(黑方)和一个白子(白方)。执黑的一方先行,每次玩家可以移动己方的任何一枚棋子到同一行的任何一个空格上,当然这过程中不许越过该行的敌方棋子。双方轮流移动,直到某一方无法行动为止,移动最后一步的玩家获胜。Tom总是先下(黑方)。图1是某个初始局面,图二是Tom移动一个棋子后的局面(第一行的黑子左移两步)。



图1




图2






Input

输入数据有多组。每组数据第一行为两个整数n和m,由空格分开。接下来有n行,每行两个数Ti,Ji (1 ≤ Ti, Ji ≤ m)分别表示Tom和Jerry在该行棋子所处的列数。
  注意:各组测试数据之间有不定数量的空行。你必须处理到文件末。





Output

对于每组测试数据输出一行你的结果。如果当前局面下Tom有必胜策略则输出“I WIN!”,否则输出“BAD LUCK!”。




Sample Input

3 6
4 5
1 2
1 23 6
4 5
1 3
1 2





Sample Output

BAD LUCK!
I WIN!




  对待这种题,需要有明确的思路,题目的条件怎么来利用,不然会很难敲出代码。要明确两个棋子相邻是必败态,因为后手可以一直紧贴前手,使其到最后无路可走,只要明确了这个问题的本质再用异或运算就so easy了

#include
#include
using namespace std;
int main()
{int n,m,x,y;while(~scanf("%d%d",&n,&m)){int sum&#61;0;//要明确题意{scanf("%d%d",&x,&y);if(x>y)//相邻sum^&#61;x-y-1;else//不相邻sum^&#61;y-x-1;}if(sum)cout<<"I WIN!"<}






推荐阅读
  • HDU1176:免费馅饼问题的动态规划解法分析
    题目“免费馅饼”通过动态规划方法进行了解析。该问题的时间限制为 Java 2000ms 和其他语言 1000ms,内存限制为 Java 65536K 和其他语言 32768K。本文详细探讨了如何利用动态规划算法高效求解此问题,并对算法的时间复杂度和空间复杂度进行了深入分析。此外,还提供了具体的实现步骤和代码示例,帮助读者更好地理解和应用这一方法。 ... [详细]
  • 在HDU 1166敌军布阵问题中,通过运用线段树数据结构,可以高效地计算指定区间的敌军数量。该算法不仅能够在限定的时间和内存条件下快速求解,还能够灵活应对动态变化的战场局势,为实时决策提供支持。 ... [详细]
  • FastDFS Nginx 扩展模块的源代码解析与技术剖析
    FastDFS Nginx 扩展模块的源代码解析与技术剖析 ... [详细]
  • 如何高效启动大数据应用之旅?
    在前一篇文章中,我探讨了大数据的定义及其与数据挖掘的区别。本文将重点介绍如何高效启动大数据应用项目,涵盖关键步骤和最佳实践,帮助读者快速踏上大数据之旅。 ... [详细]
  • 在处理遗留数据库的映射时,反向工程是一个重要的初始步骤。由于实体模式已经在数据库系统中存在,Hibernate 提供了自动化工具来简化这一过程,帮助开发人员快速生成持久化类和映射文件。通过反向工程,可以显著提高开发效率并减少手动配置的错误。此外,该工具还支持对现有数据库结构进行分析,自动生成符合 Hibernate 规范的配置文件,从而加速项目的启动和开发周期。 ... [详细]
  • 本文探讨了利用Java实现WebSocket实时消息推送技术的方法。与传统的轮询、长连接或短连接等方案相比,WebSocket提供了一种更为高效和低延迟的双向通信机制。通过建立持久连接,服务器能够主动向客户端推送数据,从而实现真正的实时消息传递。此外,本文还介绍了WebSocket在实际应用中的优势和应用场景,并提供了详细的实现步骤和技术细节。 ... [详细]
  • 通过采用用户数据报协议(UDP),本研究设计并实现了一种高效的文件传输方法。在发送端,系统利用Java编程语言中的相关类库,如`File`和`FileInputStream`,实现了文件的读取与分段处理,确保了数据的快速传输。该方法不仅提高了传输效率,还降低了网络拥塞的风险,适用于大规模文件传输场景。 ... [详细]
  • [BZOJ1047] [HAOI2007] 单调队列在理想正方形问题中的应用与优化
    本文探讨了在解决理想正方形问题时,如何利用单调队列进行高效优化。具体而言,给定一个由整数组成的 \(a \times b\) 矩阵,目标是从中找到一个 \(n \times n\) 的子矩阵,使该子矩阵内所有元素的最大值与最小值之差最小。输入部分首先提供三个整数,分别表示矩阵的行数、列数以及子矩阵的边长。通过引入单调队列,算法能够显著提高搜索效率,从而快速找到最优解。 ... [详细]
  • 本文详细介绍了使用C语言和C++实现的动态规划算法来解决数塔问题。通过具体的代码示例和算法解析,展示了如何高效地计算数塔的最大路径和。该方法不仅适用于数塔问题,还可应用于其他类似的组合优化问题。 ... [详细]
  • 题目链接:http://codeforces.com/gym/101190/attachments题意:在一个共享三轮车站点,某些用户需要租用车辆。该问题涉及如何通过离线查询和排序优化策略来高效地管理和分配车辆资源。具体来说,需要设计一种算法,在满足所有用户需求的同时,最小化总等待时间和资源浪费。通过合理的数据结构和算法优化,可以显著提高系统的整体性能和用户体验。 ... [详细]
  • 本文介绍了如何利用Apache POI库高效读取Excel文件中的数据。通过实际测试,除了分数被转换为小数存储外,其他数据均能正确读取。若在使用过程中发现任何问题,请及时留言反馈,以便我们进行更新和改进。 ... [详细]
  • 本文详细解析了九度编程平台上的斐波那契数列高效算法挑战(题目编号:1387)。该挑战要求在1秒的时间限制和32兆的内存限制下,设计出高效的斐波那契数列计算方法。通过多种算法的对比和性能分析,本文提供了优化方案,帮助参赛者在限定资源条件下实现高效计算。 ... [详细]
  • jQuery插件验证与屏幕键盘功能的集成解决方案
    本文介绍了一种集成了验证功能和屏幕键盘的jQuery插件解决方案。该插件不仅提供了强大的表单验证功能,还引入了一个高度可定制的屏幕键盘,以增强用户体验。通过这一集成方案,开发者可以轻松实现复杂的表单验证逻辑,并为用户提供便捷的输入方式,特别适用于移动设备或特殊输入场景。 ... [详细]
  • 在 Windows 10 环境中,通过配置 Visual Studio Code (VSCode) 实现基于 Windows Subsystem for Linux (WSL) 的 C++ 开发,并启用智能代码提示功能。具体步骤包括安装 VSCode 及其相关插件,如 CCIntelliSense、TabNine 和 BracketPairColorizer,确保在 WSL 中顺利进行开发工作。此外,还详细介绍了如何在 Windows 10 中启用和配置 WSL,以实现无缝的跨平台开发体验。 ... [详细]
  • 在晴朗天气条件下,对一种神奇的魔法现象进行了深入分析。该题目为原创,基准时间限制为1秒,空间限制为131072KB,分值20,属于3级难度的算法题。研究发现,这种魔法现象在阳光明媚的环境中表现得尤为显著,进一步探讨了其背后的科学原理和技术实现方法。 ... [详细]
author-avatar
mobiledu2502885977
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有