Uva1608 Non-boring sequences 【分治+中途相遇】【例题8-16】

题目：Non-boring sequences

题意：给一个序列，如果此序列中的任意子序列中至少寻找一个唯一的值就说明此序列为不无聊序列，否则为无聊序列。注意，任意子序列即所有的子序列都满足才行！

思路：依然是参考了紫书+代码库！

（1）预处理：分别从左边和右边来一遍，从左边扫，当没有出现重复值时，当前位置都赋值为-1，如果出现重复值了，将上一个值的位置记录到当前出现重复的位置上，这里可以用一个map集合实现保存每个值对应的位置。同理，从右往左再扫一遍，没有出现重复值时赋值最大值n，出现重复值同上！

（2）分治递归：从序列的左边和右边同时开始，往中间相遇，每次寻找当前子序列的一个值进行判断它是否是唯一值，根据上面的预处理数组，判断当前值的左数组出现重复值是否在当前范围内，右边同理也是。然后如果存在唯一值就继续从这个唯一值的位置分开左右部分，再将左右部分同时进行分治递归，直到左边界大于右边界时即所有的子序列都有唯一值了！

参考：紫书-例8-16-P + 紫书代码库

代码：

#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++){//预处理从左边起出现重复值的前一个值的位置
        if(!cur.count(arr[i]))pre[i] = -1;//当前arr[i]还是唯一值，将此位置赋为-1
        else pre[i] = cur[arr[i]];//arr[i]出现重复值，当此值的前一个的位置赋给当前记录位置数组
        cur[arr[i]] = i;//记录每个值的位置
    }
    cur.clear();
    for(int i=n-1;i>=0;i--){//预处理从右边起出现重复值的前一个值的位置
        if(!cur.count(arr[i])) nex[i] = n;//同上，只不过赋值为最大n，因为一会儿判断唯一性时需要
        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;//判断当前值在当前范围中的唯一性
}
bool check(int L,int R){
    if(L >= R) return true;//达到中间点，说明所有都成立了
    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);//从左开始 当前值时唯一性后进行分治
        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;
}