解題區/解題區 - UVa

UVa 1608 - Non-boring sequences

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem

We were afraid of making this problem statement too boring, so we decided to keep it short. A sequence is called non-boring if its every connected subsequence contains a unique element, i.e. an element such that no other element of that subsequence has the same value.
Given a sequence of integers, decide whether it is non-boring.

Input

The first line of the input contains the number of test cases T. The descriptions of the test cases follow:
Each test case starts with an integer n (1 <= n <= 200000) denoting the length of the sequence. In the next line the n elements of the sequence follow, separated with single spaces. The elements are non-negative integers less than 10^9.

Output

Print the answers to the test cases in the order in which they appear in the input. For each test case print a single line containing the word non-boring or boring.

Sample Input

1
2
3
4
5
6
7
8
9
4
5
1 2 3 4 5
5
1 1 1 1 1
5
1 2 3 2 1
5
1 1 2 1 1

Sample Output

1
2
3
4
non-boring
boring
non-boring
boring

Solution

題目描述：

對於所有連續區間，都符合至少有一個獨特的數字。即每個區間中都會有一個數字不重複。

題目解法：

對於一個區間 [l, r] 來說，符合條件時，會存在一個獨特的數字位於 m，則對於 i in [l, m-1] and j in [m+1, r]，所有 [i, j] 產生的區間必然會符合，則遞歸下去查找 [l, m-1] 和 [m+1, r] 有沒有符合。

這題有趣的地方在於－如何快速得到這個獨特數字，不過也不難想地，建出數字的前一個相同和下一個相同。判斷該數字在區間是獨特時，則前一個和下一個皆不會在區間中。

這樣仍不會通過測資，如果是想要接近中間的方式去切割，則會接受 TLE 的殘酷事實，當初在想是不是遞迴太深還怎麼的，這裡留下困惑，根據快速排序的經驗，如果切割點在中間是比較好的，複雜度為 O(n log n)。

lang: cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h> 
#include <algorithm>
#include <map>
using namespace std;
int A[262144];
int NEXT[262144], PREV[262144];
map<int, int> R;
int dfs(int l, int r) {
    if(l >= r)	return 1;
    for(int i = 0; i <= (r-l+1)/2; i++) {
        if(NEXT[l+i] > r && PREV[l+i] < l)
            return dfs(l, l+i-1) && dfs(l+i+1, r);
        if(NEXT[r-i] > r && PREV[r-i] < l)
            return dfs(l, r-i-1) && dfs(r-i+1, r);
    }
    return 0;
}
int main() {
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
            NEXT[i] = n+1;
            PREV[i] = 0;
        }
        R.clear();
        for(int i = 1; i <= n; i++) {
            PREV[i] = R[A[i]], NEXT[PREV[i]] = i;
            R[A[i]] = i;
        }
        puts(dfs(1, n) ? "non-boring" : "boring");
    }
    return 0;
}
/*
20
6
1 2 3 1 2 3
5
1 2 3 4 5
5
1 1 1 1 1
5
1 2 3 2 1
5
1 1 2 1 1
*/