bzoj3917: [Baltic2014]sequence

时间：2021-05-26 06:29:05

Description

 序列A由从N开始的连续K个数按顺序构成,现在将A中的每个数只保留某一个数码,记为序列B,给定K和B,求可能的最小的N

Input

第一行一个数K,第二行K个数B_i

Output

输出一个数N

当确定了N的个位时，可以确定这连续的K个数的个位，这是得到子问题求N/10的值，B数组（压位表示子问题中哪些位必须出现）对应更新为大约K/10的长度，于是可以递归处理，当K=1时贪心确定所需的最高位

当K=2时若选择个位为9则递归下去K仍为2，要特判剪枝一下

递归到K=1时，若答案有必须存在的前导0则要特判在前面补位

#include<cstdio>

typedef long long i64;

int _(){

    int x=,c=getchar();

    while(c<)c=getchar();

    while(c>)x=x*+c-,c=getchar();

    return x;

}

int n,v[],d[];

i64 dfs(int*d0,int n,bool _9,bool _0){

    bool dd=;

    for(int i=;i<n;++i)if(d0[i]){dd=;break;}

    if(!dd)return _0;

    if(n==){

        int x=*d0;

        if(x==)x=;

        i64 v=;

        for(int i=;i<;++i)if(x>>i&){

            v=i;

            x^=<<i;

            break;

        }

        for(int i=;i<;++i)if(x>>i&)v=v*+i;

        return v;

    }

    i64 v0=1ll<<;

    int*d1=d0+n;

    for(int a=;a<;++a){

        if(a==&&!_9)break;

        int n1=,x=a,s=;

        for(int b=;b<n;++b){

            s|=d0[b]&~(<<x);

            if(++x==){

                x=;

                d1[n1++]=s;

                s=;

            }

        }

        if(x)d1[n1++]=s;

        i64 v1=dfs(d1,n1,a!=||n>,!a&&(_0||(&*d0)))*+a;

        if(v1<v0)v0=v1;

    }

    return v0;

}

int main(){

    n=_();

    for(int i=;i<n;++i)d[i]=<<(v[i]=_());

    printf("%lld",dfs(d,n,,));

    return ;

}

相关文章