zoj 1028 Flip and Shift(数学)-白红宇

zoj 1028 Flip and Shift(数学)

阅读量：4956 次

发布时间：2019-06-12

本文共 2519 字，大约阅读时间需要 8 分钟。

Flip and Shift

Time Limit: 2 Seconds
Memory Limit: 65536 KB

This puzzle consists of a random sequence of m black disks and n white disks on an oval-shaped track, with a turnstile capable of flipping (i.e., reversing) three consecutive disks. In Figure 1, there are 8 black disks and 10 white disks on the track. You may spin the turnstile to flip the three disks in it or shift one position clockwise for each of the disks on the track (Figure 1).

Figure 1. A flip and a shift

The goal of this puzzle is to gather the disks of the same color in adjacent positions using flips and shifts. (Figure 2)

Figure 2. A goal sequence

You are to write a program which decides whether a given sequence can reach a goal or not. If a goal is reachable, then write a message ��YES��; otherwise, write a message ��NO��.

Input
The input consists of T test cases. The number of test cases ) (T is given in the first line of the input. Each of the next T lines gives a test case. A test case consists of an integer, representing the sum of m and n, and a sequence of m+n 0s and 1s, representing an initial sequence. A 0 denotes a white disk and a 1 denotes a black disk. The sum of m and n is at least 10 and does not exceed 30. There is a space between numbers.
Output
The output should print either ��YES�� or ��NO�� for each test case, one per line.
Sample Input
2
18 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 1
14 1 1 0 0 1 1 1 0 0 1 1 0 1 0

Output for the Sample Input

YES
NO

Source: Asia 2001, Taejon (South Korea)

题意：在一个圆形的首尾相连的容器中放两种球，以任意一个球为中心，交换相邻两球的位置，问是否可以将颜色相同的球放在一起。

其实这题主要考察的是你运用数学知识分析问题的能力。设位置编号为1,2,3,...,n,n为小球的总数目。

若n为偶数,则不管如何交换小球,各个小球的位置编号奇偶性保持不变,因为交换的步长为2。如果黑球

是连续,当且仅当奇位置上的黑球个数与偶位置上的黑球个数相差不大于1。

若n为奇数,则不管如何小球

的布局如何,一定能使黑白球各自连续。因为在这种情况下,奇位置上的小球通过交换可以移动到偶位置上。

这样通过交换就可以使当前布局满足连续的必要性了

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              11 #define N 50001512 #define INF 100000013 #define ll long long14 using namespace std;15 16 int main(void)17 {18 int t,odd,even,n;19 scanf("%d",&t);20 while(t--)21 {22 even = odd = 0;23 scanf("%d",&n);24 for(int i = 0; i < n; i++)25 {26 int tp;27 scanf("%d",&tp);28 if(i & 1)29 odd += tp;30 else31 even += tp;32 }33 if(n & 1)34 printf("YES\n");35 else36 {37 if(abs(odd - even) < 2)38 printf("YES\n");39 else40 printf("NO\n");41 }42 }43 return 0;44 }