ACM 递归 non-boring sequences

Myth丶恋晨 2022-06-12 14:58 101阅读 0赞

### 看了一上午，可以说是很难理解了... ###

书上说为了节省时间，所以要从两边往中间招，，此时T(n)=max\{T(k)+T(n-k)+min(k,n-k)\}。

而最坏的情况是唯一元素在中间的情况，他满足经典递推式T(n)=2T(n/2)+O(n)，即T(n)=O(nlogn)。

### uva 1608 non-boring sequences ###

![20170725132837715][]

题目大意：如果一个序列的任意连续子序列中至少有一个只出现一次的元素，则称这个序列是non-boring的。

思路：

1.用map预处理出每个位置的左边和右边最近的相等元素，从而可以在O(1)的时间内判断任意区间内某元素是否唯一。

2.设置n1,n2,两个数组分别记录a\[i\]上一次/下一次出现的位置。

3.如果我们已知一个区间中存在某一个数字只出现一次，假设区间为\[l,r\]，这个只出现一次的数字的位置为x，那么我们只要去验证\[l,x-1\]和\[x+1,r\]是否分别满足即可。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <map>
    #define maxn 200200
    using namespace std;
    int n1[maxn],n2[maxn],a[maxn],n,m,t;
    map<int,int> ss;
    bool check(int l,int r)
    {
        if (l>=r) return true;
        for (int i=0; i<=(r-l+1)/2; i++)
        { 
            if (n1[l+i]>r && n2[l+i]<l) 
    		return check(l,l+i-1)&check(l+i+1,r);
            if (n1[r-i]>r && n2[r-i]<l) 
    		return check(l,r-i-1)&check(r-i+1,r);
        }
        return false;
    }
    
    int main()
    {
        scanf("%d",&t);
        while (t--)
        {
            scanf("%d",&n);
            for (int i=1;i<=n; i++)
    		{
    			scanf("%d",&a[i]);
    			n1[i]=n+1,n2[i]=0;
    		} 
            ss.clear();
            for (int i=1; i<=n; i++)
            {
                n2[i]=ss[a[i]];//记录上一次出现a[i]的位置 
    			n1[n2[i]]=i;//记录下一次出现a[i]的位置 
                ss[a[i]]=i;
            }
            if (check(1,n)) 
    		printf("non-boring\n");
      		else 
      		printf("boring\n");
        }
        return 0;
    }

[20170725132837715]: /images/20220612/6162e5b4b1da4193a10abfd6f306031e.png