博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
暑假NOIP期末考试【1】—— Phantom
阅读量:5856 次
发布时间:2019-06-19

本文共 2180 字,大约阅读时间需要 7 分钟。

Phantom

•题目名称: phantom

•时间限制:1 秒
•空间限制:256 MiB

题目描写叙述

在一个无限大的棋盘上。排列着 n * n 枚棋子,形成一个 n 行 n 列的方阵。棋子能够横向或者纵向移动,移动方式是越过一个相邻的棋子,落入同一方向上的下一个空暇的格子里,同一时候。移除被越过的棋子。

如今。我们想知道,是否有可能通过若干次操作。使得棋盘上仅剩一枚棋子。

比如。当 n = 2 时,有例如以下操作方法:
…. …. …. ….
.OO. => …O => …O => ….
.OO. .OO. …O ….
…. …. …. …O

输入格式

输入文件的第一行包括一个整数,表示測试数据的数目。

每一个測试数据占一行,包括单独的一个整数 n。

输出格式

对于每一个測试数据。在单独的一行内输出答案。

假设有可能使得棋盘上仅剩一枚棋子,输出 YES ;否则输出 NO 。

例子输入2

2

3

例子输出YES

NO

数据范围与约定

•对于 30% 的数据,n ≤ 6。

•对于 100% 的数据,n ≤ 1 000 000 000,測试数据不超过 1000 组。


对于这道题非常多人最初的感觉就是搜索嘛,只是看看这大数据,n<=1 000 000 000,怎么可能。

仅仅能是O(1)的时间复杂度啊。所以。直觉告诉我。或者说是个人都会知道,这道题是一道有规律可循的题。。

All jokes aside,先说一下老师介绍的第一种方法:

对于一个N=2的4*4矩阵来说。我们非常easy的就能把它变成我们想要的情况,那么是不是能够把它作为一个基本模型,或者说让它成为我们的期望装态,这样的思想相似于数学中的“归纳法”(这一点能够好好体会一下)。

经过以上的分析后,如今我们能够动手实践一下了。

有句话叫什么来着“失败是通往成功的必经之路”,所以你会发现,当N=3的时候,怎么也不能实现。当时当你画4*4的情况的时候。或许在某种情况会出现一个完整的2*2。而这正是你想要的。

而我们知道仅仅剩下一个点当然也是能够的。所以同理,当N=5的时候就会出现以下的情况:
这时候大概就会找到一些规律了,也就是我们都是每三个三个消掉的。似乎仅仅要有三个连续的就能够弄掉,只是其实并不是这样简单,条件是得出现一个‘L’形状,也就是说这三个点的两端的两边至少要有一个点。这样这三个点才干够消掉。

并且我们举得4,5这两个例子大能够概括全部的情况(事实证明。不要问我为什么,自己试试就知道了)。

就像这个样子,对于随意的N(也并不是随意),都能够转化为4或5的形式。进而转化到我们的基本模型,1或2。

但到这里。可能你还会有些疑问,或许你还在问为什么为什么,由于我们越过了一个非常奇妙的数字,3。
由于。假设依照之前的思想,那么三是不是应该就没了?——只是这当然是不可能的啊,为什么呢?再花哨的语言也说不清事物的本质,因此这样的问题还是须要自己实践一下,这样自然会明确。

这回能够扩展到随意的N了,对于一个(N^2)不能被3整除的数,我们都会处理。而能被3整除的数终于不能化成1或2,所以不能够。

Ex——方法2

之前就说过,异或是一个非常奇妙的东西。在计算机中。异或属于位运算的一种。并且利用二进制能够非常快的计算出来。

只是我们在这道题用的并不是这个性质,而是以下的这三种关系:

1^2=3

2^3=1
3^1=2

也就是说,1,2,3的异或是互相转换的。

这样,我们能够把每一个格子标号
以N=6为例

1 2 3 1 2 3

3 1 2 3 1 2
2 3 1 2 3 1
1 2 3 1 2 3
3 1 2 3 1 2
2 3 1 2 3 1
无论你在这个矩阵中找到了什么规律。我想告诉你的是。每一个点的上下左右都是两个不同的数字,这样有什么优点呢?想想看。我们终于的状态是什么?1或者2或者3对吧,而我们知道如今的总亦或值为0。所以无论我们如何移动都不能出现单独的一个数字。

而这个结论正好与第一个方法中的能被3整除相调和。

PS:异或的性质非常重要,理解深刻的话对于做题来讲十分实用,假设一道题你能想出来能够用如异或一样的位运算方法的时候,你就是神犇。

最形象的方法——方法3

用最本质的想法, OO* —>**O 是我们移动的根本,那么是否我们能够抽象出一个模型(以5为例):

为什么这样做呢?能够看到。当我每次移动一步的时候,每一个颜色的点都会相应的添加一个或者降低一个。假设这个能够理解的话。那么我说它们的奇偶性都会随之改变。且同一时候变为相反的状态,依照上图:
BLUE: 8
BLACK: 8
WHILE:9
也就是”偶偶奇“,而我们的目的状态就是”001“—>‘偶偶奇’。

非常显然仅仅要我的黑、蓝、白三个数目不相等就好。这样就非常easy理解为什么能被3整除就不行了,由于在3*3的格子中,黑蓝白三种颜色的数目始终是相等的。因此这样的方法就非常好地攻克了我们方法1中可能存在疑惑的地方。

所以就非常好理解了为什么N%3==0就能够,else 不行。


Code:

太简单了,就不贴了。

Summary:

做题前一定要看看数据范围。往往数据范围就能提示你改用什么算法来作答,同一时候思想不能死板,不要往模板题上想,灵感可能就在电光火石间产生。

你可能感兴趣的文章
详解Microsoft.AspNetCore.CookiePolicy
查看>>
go与c互相调用
查看>>
如何优雅地用Redis实现分布式锁
查看>>
从零开始Docker化你的Node.js应用
查看>>
SCDPM2012 R2实战一:基于SQL 2008 R2集群的SCDPM2012 R2的安装
查看>>
SQL SERVER中字段类型与C#数据类型的对应关系
查看>>
保存对象、关系映射
查看>>
Java堆和栈的区别
查看>>
Linux lsof命令详解
查看>>
SVG path
查看>>
js判断checkbox是否选中
查看>>
【转】TabError:inconsistent use of tabs and spaces
查看>>
链路层
查看>>
多系统盘挂载
查看>>
MySQL函数怎么加锁_MYSQL 函数调用导致自动生成共享锁问题
查看>>
java map 写法_Java中List与Map初始化的一些写法
查看>>
python httpstr find_Python string.rfind方法代碼示例
查看>>
php怎么设置input大小,js实现input输入框点击变大缩小
查看>>
php 发布拼多多,拼多多补贴换增长的故事还能讲多久?
查看>>
matlab实现zca去白化,白化算法
查看>>