当前位置: 首页 > news >正文

POJ 2311 Cutting Game

POJ 2311 Cutting Game

题目大意

有一张有w×hw\times hw×h个格子的长方形纸张,两个人轮流将当前的纸张中选一张,并沿着格子的边界将这张纸剪成两部分。最先切出只有一个格子的纸张(1×11\times 11×1的纸张)的玩家获胜。当双方都采用最优策略时,问先手必胜还是必败。必胜则输出WIN,必败则输出LOSE。

有多组数据。

数据范围

2≤w,h≤2002\leq w,h\leq 2002w,h200


题解

sg[i][j]sg[i][j]sg[i][j]表示i×ji\times ji×j的纸张的状态,那么枚举剪的位置kkk,则

sg[i][j]=mex{sg[i][k]⊕sg[i][j−k],sg[i][k]⊕sg[i][j−k]}sg[i][j]=mex\{sg[i][k]\oplus sg[i][j-k],sg[i][k]\oplus sg[i][j-k]\}sg[i][j]=mex{sg[i][k]sg[i][jk],sg[i][k]sg[i][jk]}

我们可以预处理出所有sg[i][j]sg[i][j]sg[i][j]

然后,对于每一组w,hw,hw,h,答案即为sg[w][h]sg[w][h]sg[w][h],可以O(1)O(1)O(1)得出。

时间复杂度为O(n3)O(n^3)O(n3)


code

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,z[205],sg[205][205];
int main()
{for(int i=1;i<=200;i++){for(int j=1;j<=200;j++){for(int k=0;k<=200;k++) z[k]=0;for(int k=2;k<i-1;k++){z[sg[k][j]^sg[i-k][j]]=1;}for(int k=2;k<j-1;k++){z[sg[i][k]^sg[i][j-k]]=1;}int x=0;for(;z[x];x++);sg[i][j]=x;}}while(scanf("%d%d",&n,&m)!=EOF){if(sg[n][m]) printf("WIN\n");else printf("LOSE\n");}return 0;
}

相关文章:

POJ 2311 Cutting Game

POJ 2311 Cutting Game 题目大意 有一张有whw\times hwh个格子的长方形纸张&#xff0c;两个人轮流将当前的纸张中选一张&#xff0c;并沿着格子的边界将这张纸剪成两部分。最先切出只有一个格子的纸张&#xff08;111\times 111的纸张&#xff09;的玩家获胜。当双方都采用最…...

CTF-PHP反序列化漏洞1-基础知识

作者&#xff1a;Eason_LYC 悲观者预言失败&#xff0c;十言九中。 乐观者创造奇迹&#xff0c;一次即可。 一个人的价值&#xff0c;在于他所拥有的。可以不学无术&#xff0c;但不能一无所有&#xff01; 技术领域&#xff1a;WEB安全、网络攻防 关注WEB安全、网络攻防。我的…...

【面试】记一次安恒面试及总结

文章目录SQL 注入sql注入的原理&#xff1f;如何通过SQL注入判断对方数据库类型&#xff1f;补充一下其他方法判断数据库类型时间盲注的函数XPath注入抓不到http/https包&#xff0c;怎么办&#xff1f;app无自己的ssl证书app有自己的ssl证书-证书绑定(SSL pinning)逻辑漏洞有哪…...

刹车制动(卡钳)TOP3供应商份额超50%,哪些本土供应商突围

作为中国本土底盘系统供应商最早切入的细分市场之一&#xff0c;乘用车&#xff08;液压&#xff09;刹车制动器&#xff08;含卡钳&#xff09;由连接到车轮的制动盘和位于制动盘边缘的卡钳组成。制动时&#xff0c;高压刹车油推动刹车片夹紧刹车盘&#xff0c;从而产生制动效…...

Go分布式爬虫笔记(二十二)

文章目录22 辅助任务管理&#xff1a;任务优先级、去重与失败处理设置爬虫最大深度避免请求重复设置优先队列设置随机User-Agent失败处理22 辅助任务管理&#xff1a;任务优先级、去重与失败处理 设置爬虫最大深度 目的: 防止访问陷入到死循环控制爬取的有效链接的数量 最大…...

跨线程修改主界面

winform 方式&#xff1a; public delegate void MyInvoke(string str1); private void check_Click(object sender, RoutedEventArgs e) { //跨现场调度1 delete委托 WIMFORM Task.Run(() > { …...

国内ChatGPt研发-中国chatGPT

人工智能软件chatGPT Chat GPT是一种自然语言处理算法&#xff0c;采用了深度学习技术&#xff0c;用于实现文本生成和自然语言处理任务。它可以实现自然而然的人机交互&#xff0c;在自然语言生成和问答领域应用广泛。 值得注意的是&#xff0c;Chat GPT本身并不是一款具体的…...

springboot的rest服务配置服务的根路径

如果不配置默认为空&#xff0c;如下是application.yml文件只配置了端口号 server:port: 6868 那么访问时直接访问服务即可 如果配置了rest服务 RestController RequestMapping("/netLicense") public class NetLicenseController {RequestMapping("/getLice…...

MySQL B+Tree 索引优化技巧

文章目录前言一、BTree索引的基本原理二、BTree索引的性能优化技巧1.索引列的选择2.索引列的顺序3.索引长度4.索引的覆盖性5. 索引的唯一性总结前言 MySQL是一种开源关系型数据库管理系统&#xff0c;被广泛应用于各种应用程序中。作为一种关系型数据库&#xff0c;MySQL使用B…...

100种思维模型之逆向思维模型-46

芒格思考问题总是从逆向开始&#xff01;正如他经常提到的一句谚语&#xff1a;如果我能够知道我将死在哪里&#xff0c;那么我将永远不去那个地方。 马云有句口头禅&#xff1a;倒立看世界&#xff0c;一切皆有可能&#xff01; 遇到难题时&#xff0c;不妨回头看看&#xff0…...

C/C++每日一练(20230413)

目录 1. 与浮点数A最接近的分数B/C &#x1f31f; 2. 比较版本号 &#x1f31f;&#x1f31f; 3. 无重复字符的最长子串 &#x1f31f;&#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练 专栏 C/C每日一练 专栏 Java每…...

volatile和synchronized的区别

volatile和synchronized的区别并发编程三个特性&#xff1a;原子性有序性可见性ViolatedSynchronized区别对比并发编程三个特性&#xff1a; 原子性、有序性、可见性 原子性 volatile无法保证原子性。 synchronized是排它锁&#xff0c;被synchronzied修饰的代码不能被打断…...

Cadence Allegro 导出Unplaced Component Report报告详解

⏪《上一篇》   🏡《上级目录》   ⏩《下一篇》 目录 1,概述2,Unplaced Component Report作用3,Unplaced Component Report示例4,Unplaced Component Report导出方法4.1,方法14.2,方法2B站关注“硬小二”浏览更多演示视频...

面试了上百位性能测试后,我发现了一个令人不安的事实...

在企业中负责技术招聘的同学&#xff0c;肯定都有一个苦恼&#xff0c;那就是招一个合适的测试太难了&#xff01;若要问起招哪种类型的测试最难时&#xff0c;相信很多人都会说出“性能测试”这个答案。 每当发布一个性能测试岗位&#xff0c;不一会就能收到上百份简历&#…...

天气预报查询 API + AI 等于王炸(一大波你未曾设想的天气预报查询 API 应用场景更新了)

前言 近年来&#xff0c;随着信息化进程的不断深入&#xff0c;人们对于信息的获取和处理需求越来越高。而其中&#xff0c;天气查询API是一个非常重要的服务&#xff0c;它能够帮助人们快速获取所在位置的天气情况&#xff0c;同时也为各类应用提供了必要的气象数据支持。 本…...

跨境电商的行业现状与发展趋势分析

随着互联网的不断发展&#xff0c;跨境电商作为一种全新的商业模式已经逐渐崭露头角。跨境电商的出现&#xff0c;让越来越多的商家看到了扩大市场的机会&#xff0c;也为消费者提供了更加便利、更加优质的购物体验。本文将从跨境电商的定义、行业现状、发展趋势等方面进行探讨…...

适配器设计模式

目录 前言&#xff1a; 适配器原理与实现 适配器模式的应用场景 1.封装有缺陷的接口 2.统一多个类的接口设计 3.替换依赖的外部系统 4.兼容老版本接口 5.适配不同格式的数据 代理、桥接、装饰器、适配器 4 种设计模式的区别 参考资料 前言&#xff1a; 适配器模式这个模…...

代码随想录算法训练营第三十五天-贪心算法4| ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球

860.柠檬水找零 参考视频&#xff1a;贪心算法&#xff0c;看上去复杂&#xff0c;其实逻辑都是固定的&#xff01;LeetCode&#xff1a;860.柠檬水找零_哔哩哔哩_bilibili 解题思路&#xff1a; 只需要维护三种金额的数量&#xff0c;5&#xff0c;10和20。 有如下三种情…...

2023MathorcupC题电商物流网络包裹应急调运与结构优化问题建模详解+模型代码(一)

电商物流网络包裹应急调运与结构优化问题 第三次继续写数模文章和思路代码了&#xff0c;不知道上次美赛和国赛大家有没有认识我&#xff0c;没关系今年只要有数模比赛艾特我私信我&#xff0c;要是我有时间我一定免费出文章代码好吧&#xff01;博主参与过十余次数学建模大赛…...

软件测试技术之跨平台的移动端UI自动化测试(上)

摘要&#xff1a;本文提出一种跨平台的UI自动化测试方案&#xff0c;一方面使用像素级的截图对比技术&#xff0c;解决传统UI自动化测试难以验证页面样式的问题&#xff1b;另一方面用统一部署在服务器端的JavaScript测试代码代替Android和iOS测试代码&#xff0c;大大提高编写…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...