UVA1608-Non-boring sequences（分治）

Problem UVA1608-Non-boring sequences

Accept: 227 Submit: 2541
Time Limit: 3000 mSec

Problem Description

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 ﬁrst 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 109.

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

1 1 1 1 1

1 2 3 2 1

1 1 2 1 1

Sample Output

non-boring

boring

non-boring

boring

题解：典型的分治，如果找到一个数只出现一次，那么所有跨过这个数的区间都已经成立了，因此只需判断这个数左边和右边的区间的所有子区间是否成立，这样分治的感觉就很明显了，每次在所要判断的区间内找只出现一次的数字，递归判断左右，找数字的时候从左右两边开始一起找，避免最差的情况下变成O(n^2).

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int maxn = 200000 + 100;
 6 
 7 map<int, int> mmap;
 8 
 9 int n, num[maxn];
10 int Next[maxn], Pre[maxn];
11 
12 bool dfs(int le, int ri) {
13     if (le >= ri) return true;
14 
15     int i = le, j = ri;
16     int mid;
17     while (i <= j) {
18         if (Pre[i] < le && Next[i] > ri) {
19             mid = i;
20             break;
21         }
22         if (Pre[j] < le && Next[j] > ri) {
23             mid = j;
24             break;
25         }
26         i++, j--;
27     }
28     if (i > j) return false;
29     return (dfs(le, mid - 1) && dfs(mid + 1, ri));
30 }
31 
32 int main()
33 {
34     //freopen("input.txt", "r", stdin);
35     int iCase;
36     scanf("%d", &iCase);
37     while (iCase--) {
38         scanf("%d", &n);
39         for (int i = 1; i <= n; i++) {
40             scanf("%d", &num[i]);
41         }
42 
43         mmap.clear();
44         for (int i = 1; i <= n; i++) {
45             if (!mmap.count(num[i])) {
46                 Pre[i] = 0;
47                 mmap[num[i]] = i;
48             }
49             else {
50                 int pos = mmap[num[i]];
51                 Pre[i] = pos;
52                 mmap[num[i]] = i;
53             }
54         }
55 
56         mmap.clear();
57         for (int i = n; i >= 1; i--) {
58             if (!mmap.count(num[i])) {
59                 Next[i] = n + 1;
60                 mmap[num[i]] = i;
61             }
62             else {
63                 int pos = mmap[num[i]];
64                 Next[i] = pos;
65                 mmap[num[i]] = i;
66             }
67         }
68 
69         bool ok = false;
70         if (dfs(1, n)) ok = true;
71 
72         if (ok) printf("non-boring
");
73         else printf("boring
");
74     }
75     return 0;
76 }