B - wall painting (C language)

One 、 subject

Sister Huaye went to the toy store to play with building blocks ！
Now there is a building block wall in front of her , Width is n Lattice , The height of each grid is ai Lattice . Now the flower girl wants to use 2×1 Building blocks to build walls .
If two adjacent grids have the same height , The flower girl can put the building blocks horizontally , Make the height of both grids increase by one .
Of course, the flower coconut girl can put the building blocks upright in any case , Increase the height of the current grid by two .
Now here you are n And all the ai , Could you please unify the height of all the lattices ？

Input format ：

The first line of input contains an integer n（2 ≤ n ≤ 2×105 ）. The second line of input includes n It's an integer , For the initial height of each grid ai​（2 ≤ ai ≤
109 ）.

Output format ：

For a given building block wall , If it can output “YES”, Otherwise output “NO”.

Inputcopy：

5
2 1 1 2 5

Outputcopy：

YES

Inputcopy：

2
10 10

Outputcopy：

YES

Inputcopy：

3
1 2 3

Outputcopy：

NO

————————————————

Two 、 Solution

1. Ideas

① Subject requirements ：
1、 If two adjacent grids have the same height , The flower girl can put the building blocks horizontally , Make the height of both grids increase by one .
2、 In any case, place the building blocks upright , Increase the height of the current grid by two .

 Convert to mathematical language （ The rules ）：
1、if a[i]=a[i+1] ,  Sure  a[i]++,a[i+1]++;     （ The rules 1）
2、a[i]+=2;                                     （ The rules 2）

 Rule analysis ：
1、 By the rules 2 know ： For any number +2 operation , Its parity does not change ;
         translate ： Two numbers with the same parity , You can use rules 2 Make it equal 
2、 By the rules 1 know ： If two adjacent numbers are equal , Then they can add one at the same time 
    By analysis 1 know , Two numbers with the same parity , Can be equal to 
         translate ： If two numbers have the same parity , The parity of two numbers can be changed at the same time 

② Sample analysis ：

1、2 1 1 2 5 accidentally p. p. accidentally
2 2 2 2 5
3 3 3 3 5
5 5 5 5 5
There are two odd numbers between two even numbers √
2、10 10 accidentally accidentally
There are zero odd numbers between two even numbers √
3、1 2 3 p. accidentally p.
3 2 3 / 1 4 3 / 1 2 5
There is an even number between two odd numbers ×
4、2 1 3
2 3 3
2 4 4
4 4 4
There are zero even numbers between two odd numbers √
5、2 1 1 4 4 3
There is an even number between two odd numbers
There is an odd number between two even numbers ×
6、2 1 1 2 5 7 9 2 2 11 2
If you start with an even number , The first pair of even numbers satisfies the condition , The first 3 Even numbers and the 2 Even numbers have even numbers and odd numbers , Then you can
here , Starting with an even number does not satisfy the condition ,
But if you start with an odd number , The middle of the first pair of even numbers Yes even numbers An odd number , Even and odd numbers can be paired in pairs ;
then The first 3 Even numbers and the 2 Even numbers directly Yes even numbers An odd number , It is also paired in pairs ;
Then the conditions are met .

③ Topic analysis ：

Between two numbers with the same parity ,
If there are even numbers with different parity , Then you can ;
conversely , No way. ;

④ Algorithm ：（ Start with an even number ）

Encounter odd numbers , skip ; Even numbers , Use one flag To store the starting point ,
flag There is an initial value , If you encounter even numbers for the first time ,flag Mark the starting point ,
If it's the second time , Then use len= End - The starting point , And then determine len Parity ;
And then put flag Set to initial value .

——————————————

2. Code

#include<stdio.h>
#define Max 200010

int n;                      // n  Lattice 
int i, j, k;                //  Traverse 
int a[Max];                 //  The height of each grid 

int check(int x);

int main()
{
    
    scanf("%d", &n);

    for (i = 1; i <= n; i++)
    {
    
        scanf("%d", &a[i]);
    }

    if (check(1) || check(0))
        printf("YES");
    else
        printf("NO");

    return 0;
}
int check(int x)
{
    
    int flag = 0;
    //  Start with an even number 
    for (int j = 1; j <= n; j++)
    {
    
        //  Encounter odd numbers 
        if (a[j] % 2 == x)
            continue;
        //  Even numbers 
        else
        {
    
            //  The starting point 
            if (flag == 0)
            {
    
                flag = j;
            }
            //  End 
            else
            {
    
                //  There are two even numbers  flag  An odd number 
                flag = j - 1 - flag;
                //  If there is   Odd number   An odd number 
                if (flag % 2 == 1)
                    return 0;
                //  hold flag Set to initial value 
                flag = 0;
            }
        }
    }
    //  Judge whether there is a beginning and an end 
    return flag == 0;
}