这道题是POJ1063,这里找了一篇解释详细的报告:

题意:给定一个数N (10 <=N <= 30),然后给你N个数,这N个数由0和1组成,这N个数可以看做是一个环.然后现在又一种操作,可以将连续的三个数进行翻转,也可以将整个序列顺时针旋 转一圈.现在问是否存在通过一个操作来是的实现将所有的1都靠在一起.

这题刚开始分析的时候只注意到连续的三个数的8种组合情况,然后只有四种情况是在翻转过程中产生变化的.但是这样的想法还是没有多大帮助.实在是不 会了.因为我的整个思路在于去构造一个方法能够使得所有的1都连在一起.而题目只要我们输出YES或者是NO.参看了题解后恍然大悟:这里只要从奇偶性方 面去思考就可以了.

当我们从奇偶性去看一个状态的时候,最后的状态是什么呢,所有的1都连在一起,如果是奇数个1的话,那么1所有位置的奇偶性之差为1,偶数个1则为 零.我们在观察其实所谓的翻转就是将某个点的坐标+或者是-2,这并不影响其奇偶性. 当N为奇数的时候,那么一直+2的话,那么最后的时候会出现N和1两个奇数连着的情况,因此奇偶性发生了突变.也就是我如果N是奇数的话,那么我们能够构 造出1在奇数位置和偶数位置的差不超过1.如果N为偶数的话,那么无论如何翻转,奇偶性终将不变,因此如果初始状态不满足的话就输出NO了.

综上所述:

1.当N为奇数的时候,总是输出YES

2.当N为偶数的时候,如果出现在奇数位上的1和偶数位上的1之差不超过1的话输出YES,否则输出NO

思路明白了,代码也不难了,参考代码网上可以搜!

在此顺便对12级集训队训练赛(七) C – 兔子繁殖 的测试数据不足感到抱歉,现已更正~

发表评论

电子邮件地址不会被公开。

Post Navigation