1608 – Non-boring sequences(折半递归。。暂且这么叫吧)
最后更新于:2022-04-01 15:52:28
该题给一个序列,让我们判断是不是不无聊序列(如果不明白请看样例), 我们可以将区间从大到小不断压缩来确定答案,首先要确定一个区间是否满足要求,只要看这个区间里是不是有一个只出现一次的数,受前面《唯一的雪花》一题的启发,我们可以在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;
}
~~~