ACM 递归 non-boring sequences-蒲公英云

ACM 递归 non-boring sequences

Myth丶恋晨 2022-06-12 14:58 215阅读 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;
}