博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 1063 Flip and Shift
阅读量:5823 次
发布时间:2019-06-18

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

数学,规律,构造类问题

题意,就是以任意一个点为中心,交换它左右两个点的位置。

一开始想这题,有个地方错了,所以一直想不到,就是把所有黑子当成一样的,白子当成一样,这样想也不是说错,但是这样想会限制了思维

然后换一种思维,给所有棋子按1到n编号,就算颜色相同,编号也不同,是不同的棋子。

然后我们看看交换的时候会发生什么事情

以点a为中心,那么a-1和a+1发生交换,那么也就是说,编号a-1的点去了a+1的位置,如果继续交换的话,它还可以去到a+3,a+5……的位置,这里有一个突破点就是,它所在的位置的奇偶性不行,如果它一开始就在奇数的位置,无论怎么交换它还是在奇数位置,偶数亦然。

但!不要这么轻易下结论,看看在结尾成环的地方会发生什么

如果以1为中心,那么n和2就可以交换位置

如果以n为中心,n-1和1就可以交换位置

这时候如果主要到了n的奇偶性的话,就能发现问题

 

如果n是奇数:

以1为中心的时候,n和2交换,那么也就是说编号为n的点,原本在奇数的位置,现在去了2,就在偶数位置了,而2号点本来在2的位置现在去了n位置,位置的奇偶性也发生了变化

同样的,如果以n为中心,交换n-1和1,它们所在的位置的奇偶性也会发生变化

结合上面的,如果不在借口处,交换,一个点所在的位置的奇偶性不变,如果在接口处交换,位置的奇偶性就会发生变化。那么,一个点其实能去到任何它想去到的位置?对的没错!

一个点如果在偶数位,那么不断交换,它始终只能去到偶数位,但是到了接口处,却改变了它位置的奇偶性,下一轮它就去到了奇数位置,在这一轮中它又始终在奇数位置…………依次不断循环下去!所以很幸运的,这个点,只要它愿意,只要循环次数足够多,那么它能去到任何一个它想去到的位置

如果n是偶数:

以1为中心,n和2交换,会发现n和2都是偶数,即使交换了,它们所在位置的奇偶性不会发生变化

以n为中心,n-1和1交换,会发现n-1和1都是奇数,即使交换了,它们所在的位置的奇偶性不会发生变化

所以对于n是偶数的情况则没那么幸运了,一个点一开始在偶数位置的话,无论怎么交换,即使到了接口处继续交换,都不能改变它所在位置的奇偶性。一开始的位置就是奇数亦然

 

有了上面这两条很重要结论,我们的问题其实变为了一个构造类问题,并且仅仅是判断这个构造能否成功

结论1:如果序列长度为奇数,对于序列中的任意一个点,它能去到任何位置

结论2:如果序列长度为偶数,对于序列中一开始就在奇数位置的点,它能去到任意奇数位置但去不到偶数位置,对于一开始就在偶数位置的点,它能去到任何偶数位置但去不到奇数位置

 

我们构造的目的是将所有黑色点聚集在一起:

当n为奇数的时候,这太容易了,因为我们能将任意一个黑色点移动到我们想让它去的地方,所以要它们聚集在一起,那是一定能做到的,所以n为奇数,一定为YES

当n为偶数的时候,如果黑色点一开始就在偶数位置,我们能将它移到任意偶数位置,奇数亦然。所以我们只要保证,一开始,处在奇数位置的黑点和处在偶数位置的黑点的个数相差不超过1,那么就能聚集在一起。因为如果个数相差超过了1,那么必然必然导致一些黑点能聚集在一起,但是另一些黑点则隔着放,因为他们所在位置的奇偶性不能改变!

 

#include 
using namespace std;inline int abs(int a ,int b){ return a-b > 0 ? a-b : b-a;}int main(){ int cas,n,a,b,x; cin >> cas; while(cas--) { cin >> n; a = b = 0; for(int i=1; i<=n; i++) { cin >> x; if(x && i&1) a++; else if(x && !(i&1)) b++; } if(n&1 || abs(a,b)<=1) cout << "YES" << endl; else cout << "NO" << endl; } return 0;}

 

转载于:https://www.cnblogs.com/scau20110726/archive/2013/06/12/3133078.html

你可能感兴趣的文章
富士通全面升级ETERNUS存储系统
查看>>
大数据时代的安全边界
查看>>
云栖大会首开Tech Insight首场爆棚
查看>>
如何区分块存储和文件存储?
查看>>
漫谈深度学习 这个领域有点火!
查看>>
成就世界上首个数码单反相机的图像传感器
查看>>
《数字视频和高清:算法和接口》一2.2EOCF标准
查看>>
IoT设备网络会削减开支提高生产力吗?
查看>>
大数据的下一个五年:Hadoop将推动数据平民化
查看>>
SDN,新十年,再反思:变革已露锋芒,智能初现曙光
查看>>
PHP垃圾回收机制详解
查看>>
Java Spring中同时访问多种不同数据库
查看>>
移动云应用的开发与管理
查看>>
选择云主机前,你需要知道这些安全问题
查看>>
云计算快速崛起 云安全服务市场将达48亿美元
查看>>
产学互补合作共赢 中科曙光携手重庆交通大学共建大数据联合实验室
查看>>
Android后台保活实践总结:即时通讯应用无法根治的“顽疾”
查看>>
成小胖学习微服务架构·基础篇
查看>>
Windows10系统下如何将chm文件转换成txt文件?
查看>>
未来:只懂计算机的黑客不是好黑客
查看>>