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 2002≤w,h≤200
题解
令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][j−k],sg[i][k]⊕sg[i][j−k]}
我们可以预处理出所有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个格子的长方形纸张,两个人轮流将当前的纸张中选一张,并沿着格子的边界将这张纸剪成两部分。最先切出只有一个格子的纸张(111\times 111的纸张)的玩家获胜。当双方都采用最…...
CTF-PHP反序列化漏洞1-基础知识
作者:Eason_LYC 悲观者预言失败,十言九中。 乐观者创造奇迹,一次即可。 一个人的价值,在于他所拥有的。可以不学无术,但不能一无所有! 技术领域:WEB安全、网络攻防 关注WEB安全、网络攻防。我的…...
【面试】记一次安恒面试及总结
文章目录SQL 注入sql注入的原理?如何通过SQL注入判断对方数据库类型?补充一下其他方法判断数据库类型时间盲注的函数XPath注入抓不到http/https包,怎么办?app无自己的ssl证书app有自己的ssl证书-证书绑定(SSL pinning)逻辑漏洞有哪…...
刹车制动(卡钳)TOP3供应商份额超50%,哪些本土供应商突围
作为中国本土底盘系统供应商最早切入的细分市场之一,乘用车(液压)刹车制动器(含卡钳)由连接到车轮的制动盘和位于制动盘边缘的卡钳组成。制动时,高压刹车油推动刹车片夹紧刹车盘,从而产生制动效…...
Go分布式爬虫笔记(二十二)
文章目录22 辅助任务管理:任务优先级、去重与失败处理设置爬虫最大深度避免请求重复设置优先队列设置随机User-Agent失败处理22 辅助任务管理:任务优先级、去重与失败处理 设置爬虫最大深度 目的: 防止访问陷入到死循环控制爬取的有效链接的数量 最大…...
跨线程修改主界面
winform 方式: public delegate void MyInvoke(string str1); private void check_Click(object sender, RoutedEventArgs e) { //跨现场调度1 delete委托 WIMFORM Task.Run(() > { …...
国内ChatGPt研发-中国chatGPT
人工智能软件chatGPT Chat GPT是一种自然语言处理算法,采用了深度学习技术,用于实现文本生成和自然语言处理任务。它可以实现自然而然的人机交互,在自然语言生成和问答领域应用广泛。 值得注意的是,Chat GPT本身并不是一款具体的…...
springboot的rest服务配置服务的根路径
如果不配置默认为空,如下是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是一种开源关系型数据库管理系统,被广泛应用于各种应用程序中。作为一种关系型数据库,MySQL使用B…...
100种思维模型之逆向思维模型-46
芒格思考问题总是从逆向开始!正如他经常提到的一句谚语:如果我能够知道我将死在哪里,那么我将永远不去那个地方。 马云有句口头禅:倒立看世界,一切皆有可能! 遇到难题时,不妨回头看看࿰…...
C/C++每日一练(20230413)
目录 1. 与浮点数A最接近的分数B/C 🌟 2. 比较版本号 🌟🌟 3. 无重复字符的最长子串 🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C每日一练 专栏 Java每…...
volatile和synchronized的区别
volatile和synchronized的区别并发编程三个特性:原子性有序性可见性ViolatedSynchronized区别对比并发编程三个特性: 原子性、有序性、可见性 原子性 volatile无法保证原子性。 synchronized是排它锁,被synchronzied修饰的代码不能被打断…...
Cadence Allegro 导出Unplaced Component Report报告详解
⏪《上一篇》 🏡《上级目录》 ⏩《下一篇》 目录 1,概述2,Unplaced Component Report作用3,Unplaced Component Report示例4,Unplaced Component Report导出方法4.1,方法14.2,方法2B站关注“硬小二”浏览更多演示视频...
面试了上百位性能测试后,我发现了一个令人不安的事实...
在企业中负责技术招聘的同学,肯定都有一个苦恼,那就是招一个合适的测试太难了!若要问起招哪种类型的测试最难时,相信很多人都会说出“性能测试”这个答案。 每当发布一个性能测试岗位,不一会就能收到上百份简历&#…...
天气预报查询 API + AI 等于王炸(一大波你未曾设想的天气预报查询 API 应用场景更新了)
前言 近年来,随着信息化进程的不断深入,人们对于信息的获取和处理需求越来越高。而其中,天气查询API是一个非常重要的服务,它能够帮助人们快速获取所在位置的天气情况,同时也为各类应用提供了必要的气象数据支持。 本…...
跨境电商的行业现状与发展趋势分析
随着互联网的不断发展,跨境电商作为一种全新的商业模式已经逐渐崭露头角。跨境电商的出现,让越来越多的商家看到了扩大市场的机会,也为消费者提供了更加便利、更加优质的购物体验。本文将从跨境电商的定义、行业现状、发展趋势等方面进行探讨…...
适配器设计模式
目录 前言: 适配器原理与实现 适配器模式的应用场景 1.封装有缺陷的接口 2.统一多个类的接口设计 3.替换依赖的外部系统 4.兼容老版本接口 5.适配不同格式的数据 代理、桥接、装饰器、适配器 4 种设计模式的区别 参考资料 前言: 适配器模式这个模…...
代码随想录算法训练营第三十五天-贪心算法4| ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球
860.柠檬水找零 参考视频:贪心算法,看上去复杂,其实逻辑都是固定的!LeetCode:860.柠檬水找零_哔哩哔哩_bilibili 解题思路: 只需要维护三种金额的数量,5,10和20。 有如下三种情…...
2023MathorcupC题电商物流网络包裹应急调运与结构优化问题建模详解+模型代码(一)
电商物流网络包裹应急调运与结构优化问题 第三次继续写数模文章和思路代码了,不知道上次美赛和国赛大家有没有认识我,没关系今年只要有数模比赛艾特我私信我,要是我有时间我一定免费出文章代码好吧!博主参与过十余次数学建模大赛…...
软件测试技术之跨平台的移动端UI自动化测试(上)
摘要:本文提出一种跨平台的UI自动化测试方案,一方面使用像素级的截图对比技术,解决传统UI自动化测试难以验证页面样式的问题;另一方面用统一部署在服务器端的JavaScript测试代码代替Android和iOS测试代码,大大提高编写…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...
【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...
