[分治] UVa1608 Non-boring sequences 不无聊序列 (分治与中途相遇法的结合)

时间:2021-07-02 22:08:38

题目

[分治] UVa1608 Non-boring sequences 不无聊序列 (分治与中途相遇法的结合)

思路

1.主要思路:如果有一个只出现一次的元素A[p],那么所有包含此元素的所有连续子序列都满足不无聊。那么只需分治判断A[0~p-1]和A[p+1~n]是否不无聊即可。
2.分治方向的选择:(上界分析

  1. 从左往右找:最坏情况是唯一元素恰好在最右边。 T ( n ) = T ( n 1 ) + O ( n ) = O ( n 2 )
  2. 从右往左找:最坏情况是唯一元素恰好在最左边。 T ( n ) = T ( n 1 ) + O ( n ) = O ( n 2 )
  3. 从两头往中间找(中途相遇法):最坏情况是唯一元素恰好在最中间。 T ( n ) = 2 T ( n / 2 ) + O ( n ) = O ( n l o g n )
    (此处其实有点类似快排的方法)

代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
using namespace std;

const int maxn = 200000+10000;
int n, A[maxn], myprev[maxn], mynext[maxn];
map<int, int> cur;

void init(){
    cur.clear();
    for (int i = 0; i<n; i++){
        if (!cur.count(A[i]))
            cur[A[i]] = -1;
        myprev[i] = cur[A[i]];
        cur[A[i]] = i;
    }
    cur.clear();
    for (int i = n-1; i>=0; i--){
        if (!cur.count(A[i])){
            cur[A[i]] = -1;
        }
        mynext[i] = cur[A[i]];
        cur[A[i]] = i;
    }
}

bool solve(int L, int R){
    //printf("%d %d\n",L,R);
    if (L == R-1 || L>=R) return true;
    int i = L, j = R-1;  //[i.j]
    while(i<=j){
        if (!(myprev[i] >= L && myprev[i] < R) && !(mynext[i] >= L && mynext[i] < R) && i<=j)
            return solve(L,i) && solve(i+1,R);
        i++;
        if (!(myprev[j] >= L && myprev[j] < R) && !(mynext[j] >= L && mynext[j] < R) && i<=j)
            return solve(L,j) && solve(j+1,R);
        j--;
    }
    return false;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);   // scanf的输入效率??? 
        for(int i = 0; i<n; i++)
            scanf("%d",&A[i]);
        init();
        if (solve(0,n)) printf("non-boring\n");
        else printf("boring\n");
    }
    return 0;
}