当前位置: 代码迷 >> 综合 >> poj 1063 找规律题目
  详细解决方案

poj 1063 找规律题目

热度:17   发布时间:2024-01-11 15:14:26.0

题意:在一个椭圆轨道上放有黑、白两种颜色的碟子,要求碟子总数最少为10个,最多为30个,通过FLIP和SHIFT两种转换方式将黑、白两种颜色的碟子完全分居开来。

    思路:FLIP和SHIFT两种转换方式一起使用可以理解为:将位置为i某个碟子与位置为i-2或i+2上的某个碟子交换。

    这样理解起来方便许多,若椭圆轨道上的凹槽个数N为奇数,则一定可以将两种颜色的碟子完全分开(取一黑色的碟子,假如这个黑碟原来在偶数位置上,那么当它沿某一固定方向与其他碟子交换一周后会位于奇数位置上。如:原来有11个凹槽,该黑碟原来在位置2上(凹槽起始位置为1),按i+2的方向交换,换到10号位置时,再交换一次便到1号位置上了。所以说,若N为奇数,则某个碟子可以位于任意位置,则一定可以分开。

    若椭圆轨道上的凹槽个数N为偶数,当奇数位置上的黑碟数与偶数位置上的黑碟数相差<=1时,一定可以完全分开(奇偶相嵌)。


多说一句:如果是盘子个数是偶数的话,在接口处不可以改变奇偶性,但是如果是奇数就可以改变奇偶性,所以有了上面的结论 

 

代码:

#include<iostream>
using namespace std;
int main()
{
   int n,count,even,odd;
   cin>>n;
   while(n--)
   {
       even=odd=0;
       cin>>count;
       int *disk=new int [count];
       for(int i=0;i<count;i++)
       {
           cin>>disk[i];
           if(i%2==0&&disk[i]==0)even++;
           else if(i%2!=0&&disk[i]==0)odd++;
       }
       delete disk;
       if(count%2!=0){ cout<<"YES"<<endl;continue;}
       else if(even-odd<2&&even-odd>-2)cout<<"YES"<<endl;
       else cout<<"NO"<<endl;
   }
   return 0;
}

 

 

 

另附一段较为精简的代码:

#include <stdio.h>
#include <math.h>
int main()
{
   int t, n, i, j, arr[2];
   scanf("%d", &t);
   while (t--) 
   {
       scanf("%d", &n);
       arr[0] = arr[1] = 0;
       for (i = 0; i < n; i++) 
       {
           scanf("%d", &j);
           arr[i & 1] += j;
       }
       printf("%s\n", (n & 1) || abs(arr[0] - arr[1]) <= 1 ? "YES" : "NO");
   }
   return 0;
}