題目：Non-boring sequences

題意：給一個(gè)序列，如果此序列中的任意子序列中至少尋找一個(gè)唯一的值就說(shuō)明此序列為不無(wú)聊序列，否則為無(wú)聊序列。注意，任意子序列即所有的子序列都滿足才行！

思路：依然是參考了紫書+代碼庫(kù)！

（1）預(yù)處理：分別從左邊和右邊來(lái)一遍，從左邊掃，當(dāng)沒有出現(xiàn)重復(fù)值時(shí)，當(dāng)前位置都賦值為-1，如果出現(xiàn)重復(fù)值了，將上一個(gè)值的位置記錄到當(dāng)前出現(xiàn)重復(fù)的位置上，這里可以用一個(gè)map集合實(shí)現(xiàn)保存每個(gè)值對(duì)應(yīng)的位置。同理，從右往左再掃一遍，沒有出現(xiàn)重復(fù)值時(shí)賦值最大值n，出現(xiàn)重復(fù)值同上！

（2）分治遞歸：從序列的左邊和右邊同時(shí)開始，往中間相遇，每次尋找當(dāng)前子序列的一個(gè)值進(jìn)行判斷它是否是唯一值，根據(jù)上面的預(yù)處理數(shù)組，判斷當(dāng)前值的左數(shù)組出現(xiàn)重復(fù)值是否在當(dāng)前范圍內(nèi)，右邊同理也是。然后如果存在唯一值就繼續(xù)從這個(gè)唯一值的位置分開左右部分，再將左右部分同時(shí)進(jìn)行分治遞歸，直到左邊界大于右邊界時(shí)即所有的子序列都有唯一值了！

參考：紫書-例8-16-P + 紫書代碼庫(kù)

代碼：

#include <iostream>#include <stdio.h>#include <map>using namespace std;const int maxn = 200005;int PRe[maxn],nex[maxn],arr[maxn];map<int,int>cur;int n;void init(){    cur.clear();    for(int i=0;i<n;i++){//預(yù)處理從左邊起出現(xiàn)重復(fù)值的前一個(gè)值的位置        if(!cur.count(arr[i]))pre[i] = -1;//當(dāng)前arr[i]還是唯一值，將此位置賦為-1        else pre[i] = cur[arr[i]];//arr[i]出現(xiàn)重復(fù)值，當(dāng)此值的前一個(gè)的位置賦給當(dāng)前記錄位置數(shù)組        cur[arr[i]] = i;//記錄每個(gè)值的位置    }    cur.clear();    for(int i=n-1;i>=0;i--){//預(yù)處理從右邊起出現(xiàn)重復(fù)值的前一個(gè)值的位置        if(!cur.count(arr[i])) nex[i] = n;//同上，只不過賦值為最大n，因?yàn)橐粫?huì)兒判斷唯一性時(shí)需要        else nex[i] = cur[arr[i]];//同上        cur[arr[i]] = i;    }}inline bool unique(int p,int L,int R){    return pre[p] < L && nex[p] > R;//判斷當(dāng)前值在當(dāng)前范圍中的唯一性}bool check(int L,int R){    if(L >= R) return true;//達(dá)到中間點(diǎn)，說(shuō)明所有都成立了    for(int i=0;i+L <= R-i;i++){        if(unique(L+i,L,R)) return check(L,L+i-1) && check(L+i+1,R);//從左開始 當(dāng)前值時(shí)唯一性后進(jìn)行分治        if(i+L == 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;    scanf("%d",&t);    while(t--){        scanf("%d",&n);        for(int i=0;i<n;i++) scanf("%d",&arr[i]);        init();        if(check(0,n-1)) printf("non-boring/n");        else printf("boring/n");    }    return 0;}