uva 1608（分治+中途相遇）

从左到右(超出时间限制)

// #include<bits/stdc++.h>
// using namespace std;
// const int maxn=200000;
// int A[maxn],pre[maxn],nex[maxn];
// map<int,int>cur;
// inline bool unique(int t,int L,int R){
    
// return (pre[t]<L && nex[t]>R);
// // return (pre[t]<L && nex[t]>R);
// }
// bool check(int l,int r){
    
// if(l>=r) return true;
// int i;
// for( i=0;l+i<=r-i;i++)
// {if(unique(l+i,l,r))// return check(l,l+i-1) && check(l+i+1,r);
// if(l+i==r-i)
// break;
// if(unique(r-i,l,r))
// return check(l,r-i-1)&& check(r-i+1,r);} 
// return false;
// }
// int main(){
    
// int T,n;
// scanf("%d",&T);
// while(T--){
    
// scanf("%d",&n);
// for(int i=0;i<n;i++) scanf("%d",&A[i]);
// // cout<<"T:"<<T--;
// cur.clear();
// for(int i=0;i<n;i++){
    
// if(!cur.count(A[i])) pre[i]=-1;
// else pre[i]=cur[A[i]];
// cur[A[i]]=i;// }
// cur.clear();
// for(int i=n-1;i>=0;i--){
    
// if(!cur.count(A[i])) nex[i]=n;
// else nex[i]=cur[A[i]];
// cur[A[i]]=i;
// }// // for(int i=0;i<n;i++)
// // cout<<pre[i]<<" ";
// // cout<<endl;
// // for(int i=0;i<n;i++)
// // cout<<nex[i]<<" ";
// // cout<<endl;// if(check(0, n-1)) printf("non-boring\n");
// else printf("boring\n");// }// return 0;
// }#include<bits/stdc++.h>
using namespace std;
const int maxn=200000;
int A[maxn],pre[maxn],nex[maxn];
map<int,int>cur;
inline bool unique(int t,int L,int R){
    return (pre[t]<L && nex[t]>R);
}
bool check(int l,int r){
    if(l>=r) return true;int i;for( i=l;i<=r;i++)if(unique(i,l,r))return check(l,i-1)&& check(i+1,r);// cout<<"i:"<<i<<endl;return false;
}
int  main(){
    int T,n;scanf("%d",&T);while(T--){
    scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&A[i]);// cout<<"T:"<<T--;cur.clear();for(int i=0;i<n;i++){
    if(!cur.count(A[i])) pre[i]=-1;else pre[i]=cur[A[i]];cur[A[i]]=i;}cur.clear();for(int i=n-1;i>=0;i--){
    if(!cur.count(A[i])) nex[i]=n;else nex[i]=cur[A[i]];cur[A[i]]=i;}// for(int i=0;i<n;i++)// cout<<pre[i]<<" ";// cout<<endl;// for(int i=0;i<n;i++)// cout<<nex[i]<<" ";// cout<<endl;if(check(0, n-1)) printf("non-boring\n");else printf("boring\n");}return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000;
int A[maxn],pre[maxn],nex[maxn];
map<int,int>cur;
inline bool unique(int t,int L,int R){
    return (pre[t]<L && nex[t]>R);// return (pre[t]<L && nex[t]>R);
}
bool check(int l,int r){
    if(l>=r) return true;int i;for( i=0;l+i<=r-i;i++){
    if(unique(l+i,l,r))return  check(l,l+i-1) && check(l+i+1,r);if(l+i==r-i)break;if(unique(r-i,l,r))return  check(l,r-i-1)&& check(r-i+1,r);}  return false;
}
int  main(){
    int T,n;scanf("%d",&T);while(T--){
    scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&A[i]);// cout<<"T:"<<T--;cur.clear();for(int i=0;i<n;i++){
    if(!cur.count(A[i])) pre[i]=-1;else pre[i]=cur[A[i]];cur[A[i]]=i;}cur.clear();for(int i=n-1;i>=0;i--){
    if(!cur.count(A[i])) nex[i]=n;else nex[i]=cur[A[i]];cur[A[i]]=i;}// for(int i=0;i<n;i++)// cout<<pre[i]<<" ";// cout<<endl;// for(int i=0;i<n;i++)// cout<<nex[i]<<" ";// cout<<endl;if(check(0, n-1)) printf("non-boring\n");else printf("boring\n");}return 0;
}