1608 – Non-boring sequences（折半递归。。暂且这么叫吧）

该题给一个序列，让我们判断是不是不无聊序列（如果不明白请看样例）， 我们可以将区间从大到小不断压缩来确定答案，首先要确定一个区间是否满足要求，只要看这个区间里是不是有一个只出现一次的数，受前面《唯一的雪花》一题的启发，我们可以在O（n）时间内求出当前数离他最近的与他相同的数的位置，用数组保存，那么可以在O（1）的时间快速判断，这样就将时间复杂度降到O（n^2） 但是这样还是不够的，会超时。  紫书上给出了一个很巧妙的方法，那就是在递归的时候折半枚举   ， 时间复杂度变成了 T(n) = 2*T(n/2) + O(n)  。 让我们变一下形式，T(n)/n = T(n/2)/(n/2) + 2;  令T(n)/n = C(n); 则C(n) - C(n/2) = 2; 令n = 2^k;   则令k = 1,2,3.....  然后累加就得到 C(2^k) = C(1) + 2*k   ，所以C(n) = C(1）+ 2*logn    （以2为底） 所以时间复杂度是n*logn 这个公式叫主定理，大家可以自己查阅。 ~~~ #include<bits/stdc++.h> using namespace std; const int maxn = 200000+5; int T,n,a[maxn],pre[maxn],nex[maxn]; map<int,int> cur ; bool is_unique(int p,int l,int r){ return pre[p]<l&&nex[p]>r; } bool check(int l,int r){ if(l>=r) return true; for(int i=l;i-l<=r-i;i++){ //折半递归 if(is_unique(i,l,r)){ return check(i+1,r)&&check(l,i-1); } if(is_unique(r-i+l,l,r)) return check(r-i+l+1,r)&&check(l,r-i+l-1); } return false; } int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); 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; } if(check(0,n-1)) printf("non-boring\n"); else printf("boring\n"); } return 0; } ~~~