Cptraser/ 十月 29, 2018/ 2018.10/ 0 comments

[Cerc2018]Non-boring Sequences

这是一道神奇的启发式分治题…

题目大意:
一个序列被称为是不无聊的,仅当它的每个连续子序列存在一个独一无二的数字,即每个子序列里至少存在一个数字只出现一次。给定一个整数序列,请你判断它是不是不无聊的。
Solution:
对于当前分治的子区间来说,如果有一个点ipre<Lnxt>R,则此区间不无聊。
那么两端点一起扫描,保证分治复杂度。

O(nlog_2n)

#pragma GCC optimize(3)
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <map>
using namespace std;

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}


int T,N,A[200005],nxt[200005],pre[200005];
int dfs(int L,int R){
    if(L>=R)return 1;
    for(int l=L,r=R;l<=r;l++,r--){
        if(pre[l]<=L&&R<=nxt[l])return dfs(L,l-1)&dfs(l+1,R);
        if(pre[r]<=L&&R<=nxt[r])return dfs(L,r-1)&dfs(r+1,R);
    }
    return 0;
}
map<int,int>t;
int main()
{
    for(read(T);T;T--){
        read(N);
        for(int i=1;i<=N;i++)nxt[i]=pre[i]=0;
        for(int i=1;i<=N;i++){
            read(A[i]);int &x=t[A[i]];
            if(!x)pre[i]=1;
            else nxt[x]=i-1,pre[i]=x+1;
            x=i;
        }
        for(int i=1;i<=N;i++)if(!nxt[i])nxt[i]=N;
        puts(dfs(1,N)?"TAK":"NIE");
        t.clear();
    }
}

当然这道题还可以像区间Mex一样考虑左端点的影响。

Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*