P6740 题解

Problem Link

题目大意

给定 $n$ 个数码 $d_1\sim d_n$，求最小的正整数 $x$ 使得对于所有 $1\le i\le n$，数码 $d_i$ 在数字串 $x+i-1$ 中出现过。

数据范围：$n\le 10^5$。

代码呈现

考虑推广原问题，设数码集 $S_i\subseteq\{0,1,2,3,4,5,6,7,8,9\}$ 表示 $x+i-1$ 中必须出现的数码集合。

观察 $x\sim x+n-1$，注意到删掉末位后这些数会 $10$ 个一组地变成相同的数，容易发现可以把这些数压缩到一起，然后把没满足的条件放进新的 $S_i$ 里，我们就成功构造了一个规模更小的子问题，枚举末位递归求解即可。

时间复杂度 $T(n)=10\times T(\dfrac n{10})+\mathcal O(n)=\mathcal O(n\log n)$，还有一些细节要注意：

• 特判 $n=1$ 的情况，以及 $n=2$ 且填的数码形如 $99\dots 9,100\dots 0$ 的情况。
• 注意判断当前 $x$ 是否有前导 $0$，以及这些前导 $0$ 是否一定要保留。

时间复杂度 $\mathcal O(n\log n)$。

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int B=1023;
inline int b(int x) { return 1<<x; }
inline int d(int x,int v) { return (x>>v)&1; }
inline int dfs(const vector<int> &lim,int lst,bool rem0) {
    //required digits, last digit, need remain zero?
    if(lim.size()==1) {
        int S=lim[0],res=0;
        if(S==0) return (!lst&&rem0)?1:0;
            //need 1 to be the highest digit in order to protect the 0
        if(S==1) return 10; //only need zero
        bool req0=d(S,0); //need 0?
        for(int i=1;i<=9;++i) if(d(S,i)) {
            res=res*10+i;
            if(req0) res=res*10,req0=false; //push 0 after the first non-0 digit
        }
        return res;
    }
    int res=1e16;
    for(int s=0;s<=9;++s) { //last digit
        if(lim.size()==2&&s==9&&lst==9&&!d(lim[0],9)&&!d(lim[1],0)) continue;
            //no use 9...9,10...0
        vector <int> newlim;
        for(int i=0,t=s,S=0;i<(int)lim.size();++i,t=(t+1)%10) {
            S|=lim[i]&(1023^b(t));
            if(i==(int)lim.size()-1||t==9) newlim.push_back(S),S=0;
        }
        res=min(res,dfs(newlim,s,d(lim[0],0))*10+s);
    }
    return res;
}
signed main() {
    int n;
    scanf("%lld",&n);
    vector <int> lim(n);
    for(int &i:lim) scanf("%lld",&i),i=b(i);
    printf("%lld\n",dfs(lim,0,1));
    return 0;
}