CSU-ACM2017暑期训练3-递推与递归 J - Non-boring sequences UVA - 1608

题目大意：给你一串数字序列，问你这串数字是否满足所有的连续子序列都至少存在一个元素是与子序列中所有元素都不相同的。

思路：先对序列中的所有数字进行预处理，分别存下距离他左右最近的与他相同的数字的位置。这样做是为了后面递归时可以直接判断某个元素在哪一段区间是独立的。然后递归还要左右分治递归，不然会超时.......我也不知道为啥

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
using namespace std;

int ll[222222],rr[222222],a[222222];

bool judge(int l,int r)
{
    if(l>=r)
        return 1;
    for(int i=l,j=r;i<=j;i++,j--)
    {
        if (ll[i]<l&&rr[i]>r)
            return judge(l,i-1)&&judge(i+1,r);
        if (ll[j]<l&&rr[j]>r)
            return judge(l,j-1)&&judge(j+1,r);
    }
    return 0;
}

int main()
{
    int n,t;
    scanf("%d",&t);
    while (t--)
    {
        map<int,int> mp;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for (int i=1;i<=n;i++)
        {
            if (mp.count(a[i]))
                ll[i]=mp[a[i]];
            else
                ll[i]=-1;
            mp[a[i]]=i;
        }
        mp.clear();
        for (int i=n;i>=1;i--)
        {
            if (mp.count(a[i]))
                rr[i]=mp[a[i]];
            else
                rr[i]=n+1;
            mp[a[i]]=i;
        }
        if (judge(1,n))
            printf("non-boring\n");
        else
            printf("boring\n");
    }
}