Imprecise Computer - ( 思維 / 遞推 )

題目描述

The Imprecise Computer (IC) is a computer with some structural issue that it can compare two integers correctly only when their difference is at least two. For example, IC can always correctly answer ‘4 is larger than 2’, but it can answer either ‘2 is larger than 3’ or ‘3 is larger than 2’ (in this case, IC arbitrarily chooses one of them). For two integers x and y, we say ‘x defeats y’ when IC answers ‘x is larger than y’.

Given a positive integer n, let Pn = {1, 2, … , n} be the set of positive integers from 1 to n. Then we run a double round-robin tournament on Pn using IC. The double-round-robin tournament is defined as follows:
1.The tournament is composed of two rounds (the 1st round and the 2nd round).
2.For each round, each element in Pn is compared to every other element in Pn.
Now for each element k in Pn, let ri(k) be the number of wins of k in the i-th round of the tournament. We also define the ‘difference sequence’ D = d1d2…dn where for each 1 ≤ k ≤ n, dk = |r1(k) ? r2(k)|.

The following shows an example when n = 5.

In the example above, r1(1) = 0, r1(2) = 1, r1(3) = 3, r1(4) = 3, r1(5) = 3, and r2(1) = 1, r2(2) = 1, r2(3) = 1, r2(4) = 3,r2(5) = 4. Therefore, the difference sequence is D = 1 0 2 0 1 in this example.

Given a sequence of n nonnegative integers, write a program to decide whether the input sequence can be a difference sequence of Pn.

輸入

Your program is to read from standard input. The input starts with a line containing an integer n, (3 ≤ n ≤ 1,000,000), where n is the size of Pn. In the following line, a sequence of n integers between 0 and n is given, where each element in the sequence is separated by a single space.

輸出

Your program is to write to standard output. Print exactly one line. Print YES if the sequence can be the difference sequence of Pn, and print NO otherwise.

樣例輸入

【樣例1】
5
1 0 2 0 1
【樣例2】
5
1 1 2 1 0

樣例輸出

【樣例1】
YES
【樣例2】
NO

題意

集合 Pn = { 1，2，3 … n }，兩輪游戲 , 每輪游戲 ，集合中的數兩兩對決，r1 ( k ) 代表數字 k 在 第一輪 游戲中勝利的次數 ， r2 ( k ) 代表數字 k 在 第二輪 游戲中勝利的次數 ，d ( k ) = | r1 ( k ) - r2 ( k ) | ;
對決的規則：
如果 | 數x - 數y | >= 2 , 那么兩個數中大的數勝利；
如果 | 數x - 數y | == 1 ，那么有兩種可能（ x 勝利 或者 y 勝利 ）
給你數字 n ，再給你一個 d ( i ) ( 1 <= i <= n ) 的序列，問這個序列是否合法

思路

對于 1 , 只受 2 的影響；
對于 i ( 2 <= i <= n - 1 ) 只受 i - 1 和 i + 1 的影響；
對于 n 只受 n - 1 的影響；
取變數 pre 為 i - 1 對 i 產生的影響：

如果第一輪與第二輪 i - 1 與 i 的大小關系不一樣，那么 i - 1 將對 i 產生 1 的影響（ 單看這兩個，差值為 1 ）；
如果第一輪與第二輪 i - 1 與 i 的大小關系一樣，那么 i - 1 將對 i 產生 0 的影響（ 單看這兩個，差值為 0 ）；

對于每個位置的數 d ( i ) = d ( i - 1 ) 的影響 + d ( i + 1 ) 的影響；
因此 d ( i + 1 ) 的影響 = d ( i ) - d ( i - 1 ) 的影響；
即：

如果當前位置的數 d ( i ) == pre ，說明只有 d ( i - 1 ) 對它起了影響，d ( i + 1 ) 對它的影響為 0 ,也就是 d ( i ) 對 d ( i + 1 ) 的影響為 0 ,所以更新 pre 取值 0 ；

如果當前位置的數 d ( i ) == pre + 1 ，說明 d ( i - 1 ) 和 d ( i + 1 ) 都對它起了影響，d ( i + 1 ) 對它的影響為 1 ,也就是 d ( i ) 對 d ( i + 1 ) 的影響為 1 ,所以更新 pre 取值 1 ；
（例：1，2，3，第一輪：1 > 2 , 2 < 3 , 第二輪：1 < 2 , 2 > 3 , d 序列為，1，2，1）（ 3 對 2 產生正影響 ）

如果當前位置的數 d ( i ) == pre - 1 ，說明 d ( i - 1 ) 和 d ( i + 1 ) 都對它起了影響，d ( i + 1 ) 對它的影響為 1 ,也就是 d ( i ) 對 d ( i + 1 ) 的影響為 1 ,所以更新 pre 取值 1 ；
（例：1，2，3，第一輪：1 > 2 , 2 > 3 , 第二輪：1 < 2 , 2 < 3 , d 序列為，1，0，1）（ 3 對 2 產生負影響 ）

通過遞推更新 pre 的值，來確定序列 d 的合法性

代碼

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int n,a[maxn],flag,pre;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n; 
    for(int i=1;i<=n;i++)    
        cin>>a[i];
    for(int i=1;i<n;i++)
    {
        if(a[i]==pre) 
            pre=0;
        else if(abs(a[i]-pre)==1)
            pre=1;
        else
        {
            flag=1;
            break;  
        }
    }
    if(flag) cout<<"NO";
    else
    {
        if(a[n]!=pre) flag=1;
        if(!flag) cout<<"YES";
        else cout<<"NO";
    }
    return 0;
}