题意： 如果一个序列的任意连续子序列中至少有一个只出现一次的元素 则称这个序列是 不无聊序列 输入一个n个元素的序列a 判断是不是不无聊序列
一开始想当然 以为只要 2位的子序列都满足即可 题目果然没有那么脑残 1212 就是一个反例。。。。
有一个重要的优化结论: 在总的序列找出一个 只出现一次的元素a[p] 如果没有 则无解 否则 继续递归寻找 a[L]-a[p-1] 和 a[p+1] -a[R] ！！！ 再一次巧妙运用递归
其中 判断是否为 唯一元素的方法 ： 先算出每个元素的左边和右边最近的相同元素！！
从左边向右边找 最坏情况 n2
从右边同理
从两边向中间找 最坏情况每次都在中间找到 tn=2 t 0.5n 所以复杂度为nlogn
#include<bits/stdc++.h> using namespace std; #define N 200000+5 int a[N]; int n,left1[N],right1[N]; bool uniqu(int x,int L,int R) { return left1[x]<L&&right1[x]>R; } bool check(int L,int R) { if(L>=R)return true; for(int d=0;L+d<=R-d;d++) { if(uniqu(L+d,L,R)) return check(L,L+d-1)&&check(L+d+1,R); if(L==R)break; if(uniqu(R-d,L,R)) return check(L,R-d-1 )&&check(R-d+1,R ); } return false; } int main() { int cas;cin>>cas; while(cas--) { cin>>n; map<int,int>mp; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(!mp.count(a[i])) left1[i]=-1; else left1[i]=mp[a[i]]; mp[a[i]]=i; } mp.clear(); for(int i=n;i>=0;i--) { if(!mp.count(a[i]))right1[i]=n+1; else right1[i]=mp[a[i]]; mp[a[i] ]=i; } if(check(1,n)) printf("non-boring\n"); else printf("boring\n"); } return 0; }