题解【P6740 [BalticOI 2014 Day1] Sequence】

· · 题解

在我的 cnblogs 中查看

题解

一堆细节的题。

首先答案一定不超过 123456789000000。

考虑枚举 N 的最低位填啥。由于 10x,10x+1,\dots,10x+9 这些数除去最低位以外的位置都相同，因此可以把它们并在一起，然后递归下去。对于每个“数”维护一个数集，表示需要有这个数集里的数位。

时间复杂度 T(n)=10T(\frac{n}{10})+\mathcal{O}(n)，解得 T(n)=\mathcal{\Theta}(n\log n)。

几点细节：

  2. 当递归到只有一个“数”的时候，应当特判，否则复杂度是错的。
  3. 注意特判 N 有前导零的情况。
  4. 注意处理进位，例如 \langle 9,0,1,0,3 \rangle 的答案是 99。

貌似和其他人写法不太一样，欢迎 Hack。

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T>
void Read(T &_x){
    _x=0;int _f=1;
    char ch=getchar();
    while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
    while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();
    _x*=_f;
}
template<typename T,typename... Args>
void Read(T &_x,Args& ...others){
    Read(_x);Read(others...);
}
typedef long long ll;
const int N=1e5+5;
const ll Inf=0x3f3f3f3f3f3f3f3f;
int n,a[N];
ll pow10[16];
int Convert(int x){
    int res=0;
    while(x) res|=1<<(x%10),x/=10;
    return res;
}
ll Dfs(int k,const vector<int>& need,ll cur,int zero){
    if(!zero&&none_of(need.begin(),need.end(),[](int x){return bool(x);})){
        return cur;
    }
    if(need.size()==1){
        if(k+__builtin_popcount(need[0])>17) return Inf;
        ll res=0,cnt=0;
        For(i,1,9){
            if(need[0]&(1<<i)){
                res=res*10+i;
                if(!cnt&&(need[0]&1)) res*=10;
                ++cnt;
            }
        }
        if(!cnt&&(need[0]&1)) res=10;
        else if(!cnt&&zero) res=1;
        return res*pow10[k]+cur;
    }
    if(k>17) return Inf;
    vector<int> nw;
    ll ans=Inf;
    For(i,0,9){
        nw.clear();
        ll x=cur+pow10[k]*i;
        int temp=0,flg=1;
        for(int j=0,dig=i;j<(int)need.size();++j,++dig){
            if(dig%10==0) flg&=(!temp),temp=0;
            temp|=(1023^Convert(dig))&need[j];
        }
        flg&=(!temp);
        temp=0;
        for(int j=0,dig=i;j<(int)need.size();++j,++dig){
            if(dig==10){
                nw.push_back(temp);
                dig=temp=0;
            }
            temp|=(1023^(1<<dig))&need[j];
        }
        nw.push_back(temp);
        ans=min(ans,Dfs(k+1,nw,x,i==0));
        if(flg) ans=min(ans,x);
    }
    return ans;
}
int main(){
    Read(n);
    For(i,1,n) Read(a[i]);
    pow10[0]=1;
    For(i,1,15) pow10[i]=10*pow10[i-1];
    vector<int> need;
    For(i,1,n) need.push_back(1<<a[i]);
    printf("%lld\n",Dfs(0,need,0,1));
    return 0;
}