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 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 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
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
non-boring
boring
non-boring
boring
题解：典型的分治，如果找到一个数只出现一次，那么所有跨过这个数的区间都已经成立了，因此只需判断这个数左边和右边的区间的所有子区间是否成立，这样分治的感觉就很明显了，每次在所要判断的区间内找只出现一次的数字，递归判断左右，找数字的时候从左右两边开始一起找，避免最差的情况下变成O(n^2).
#include <bits/stdc++.h> using namespace std; const int maxn = + ; map<int, int> mmap; int n, num[maxn];
int Next[maxn], Pre[maxn]; bool dfs(int le, int ri) {
if (le >= ri) return true; int i = le, j = ri;
int mid;
while (i <= j) {
if (Pre[i] < le && Next[i] > ri) {
mid = i;
break;
}
if (Pre[j] < le && Next[j] > ri) {
mid = j;
break;
}
i++, j--;
}
if (i > j) return false;
return (dfs(le, mid - ) && dfs(mid + , ri));
} int main()
{
//freopen("input.txt", "r", stdin);
int iCase;
scanf("%d", &iCase);
while (iCase--) {
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &num[i]);
} mmap.clear();
for (int i = ; i <= n; i++) {
if (!mmap.count(num[i])) {
Pre[i] = ;
mmap[num[i]] = i;
}
else {
int pos = mmap[num[i]];
Pre[i] = pos;
mmap[num[i]] = i;
}
} mmap.clear();
for (int i = n; i >= ; i--) {
if (!mmap.count(num[i])) {
Next[i] = n + ;
mmap[num[i]] = i;
}
else {
int pos = mmap[num[i]];
Next[i] = pos;
mmap[num[i]] = i;
}
} bool ok = false;
if (dfs(, n)) ok = true; if (ok) printf("non-boring\n");
else printf("boring\n");
}
return ;
}