該題給一個序列，讓我們判斷是不是不無聊序列（如果不明白請看樣例）， 我們可以將區間從大到小不斷壓縮來確定答案，首先要確定一個區間是否滿足要求，只要看這個區間里是不是有一個只出現一次的數，受前面《唯一的雪花》一題的啟發，我們可以在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; } ~~~