UVA - 1608 Non-boring sequences

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

题意:一个序列被称作是不无聊的,当且仅当,任意一个连续子区间,存在一个数字只出现了一次,问给定序列是否是不无聊的。

#include<bits/stdc++.h>
using namespace std;
#define maxn 200010
int a[maxn],pre[maxn],lat[maxn]; 
map<int,int>mp; 
bool check(int L,int R){
	if(L>=R) return true;
	int l=L,r=R;
	for(int i=L;i<=R;i++){
		if(i&1){
			if(pre[l]<L&&lat[l]>R) return check(L,l-1)&&check(l+1,R);
			l++;
		}
		else{
			if(pre[r]<L&&lat[r]>R) return check(L,r-1)&&check(r+1,R);
			r--;
		}
	}
	return false;
}
int main(){
	int t; scanf("%d",&t);
	while(t--){
		mp.clear();
        int n; scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            lat[mp[a[i]]]=i;
            pre[i]=mp[a[i]];
            mp[a[i]]=i;
        }
        for(int i=1;i<=n;i++) lat[mp[a[i]]]=n+1;
        if(check(1,n)) puts("non-boring");
        else puts("boring");
	} 
	return 0;
}
上一篇:python – 如何定义和填充列表的词典


下一篇:UVA - 1608 Non-boring sequences(分治法)