思路：
此题一个字：
难!
不啰嗦了，来讲该讲的。
读入$T$、$n$和后面的序列。先预处理出每个元素之前和之后相同元素出现的位置，就可以在$O(1)$的时间判断出一个元素在一个区间内是否唯一。每次从大的序列中找一个唯一元素，包含这个元素的就不用判断了，那么以这个元素为分界线，在分别判断两边的序列。如果只从一遍找的话，最坏的情况是唯一元素在另一头$T(n)=T(n-1)+O(n)>=O(n^2)$的。所以应该从两边开始找，$T(n)=2T(n/2)+O(n)$， 渐进复杂度是O(nlogn)。
代码：
1 #include<iostream> 2 #include<map> 3 #include<cstring> 4 using namespace std; 5 const int maxn=200005; 6 int T,n,a[maxn],pre[maxn],nex[maxn]; 7 map<int,int> mp; 8 bool judge(int l,int r) 9 { 10 if(l>=r) return true; 11 int i=l,j=r; 12 while(i<=j) 13 { 14 if(pre[i]<l&&nex[i]>r) return judge(l,i-1)&&judge(i+1,r); 15 if(pre[j]<l&&nex[j]>r) return judge(l,j-1)&&judge(j+1,r); 16 i++; 17 j--; 18 } 19 return false; 20 } 21 int main() 22 { 23 cin>>T; 24 while(T--) 25 { 26 cin>>n; 27 memset(nex,0x3f,sizeof(nex)); 28 mp.clear(); 29 map<int,int>::iterator it; 30 for(int i=0;i<n;i++) 31 { 32 cin>>a[i]; 33 it=mp.find(a[i]); 34 if(it!=mp.end()) 35 { 36 pre[i]=it->second; 37 nex[it->second]=i; 38 } 39 else pre[i]=-1; 40 mp[a[i]]=i; 41 } 42 if(judge(0,n-1)) cout<<"non-"; 43 cout<<"boring"<<endl; 44 } 45 return 0; 46 } View Code转载于:https://www.cnblogs.com/lyonlu/p/10229520.html
