P5950 题解

· · 题解

没有题解补一篇。

不难发现每一位是独立的，仅需求出对于数 0 \le t \le 9 第一次不能写的答案取最小值即可。

这题并不满足单调性(更大的数包含 t 的个数不一定更大)，无法二分。但是有一些还行的性质。

如果我们跟据 10^ix+1 到 10^i(x+1) 的数值建一颗 trie 树，不难发现这棵树和 x 的关系并不大，考虑从这里入手，预处理出前缀最小值和总和。

总和是可以处理的，但是前缀最小值和 x 有关（每次均加上了 x 中包含 t 的数量），并不好处理。不过对于含 t 个数相同的 x 而言答案一样，可以压缩状态。

记 f_{i,j},s_{i,j} 为 10^ix+1 到 10^i(x+1)，其中 x 含 t 的个数为 j 的前缀最小值，总和。转移是显然的，最后从高到低按位确定即可。0 稍微有些特殊，记得处理。

需要高精。

#include<bits/stdc++.h>
#define vi vector<int>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
const int N=105;
bool bj(vi a,vi b){
    if(a.size()!=b.size()) return a.size()<b.size();
    int n=a.size();
    per(i,n-1,0) if(a[i]!=b[i]) return a[i]<b[i];
    return 0;
}
vi add(vi a,vi b){
    vi ans; int jw=0,n=a.size(),m=b.size();
    rep(i,0,max(n,m)-1){
        int A=(i<n?a[i]:0),B=(i<m?b[i]:0);
        ans.push_back((A+B+jw)%10),jw=(A+B+jw)/10;
    }if(jw) ans.push_back(jw); return ans;
}
vi del(vi a,vi b){
    vi ans; int jw=0,n=a.size(),m=b.size();
    rep(i,0,max(n,m)-1){
        int A=(i<n?a[i]:0),B=(i<m?b[i]:0); A-=B+jw,jw=0;
        if(A<0) A+=10,jw=1; ans.push_back(A);
    }while(!ans.empty()&&ans.back()==0) ans.pop_back();
    return ans;
}
struct gj{
    vi v; bool fu;
    gj(){v.clear(),fu=0;}
    void set(int x){
        fu=0,v.clear(); if(x<0) fu=1,x=abs(x);
        while(x) v.push_back(x%10),x/=10;
    }
    bool operator <(const gj o){
        if(fu!=o.fu) return o.fu<fu;
        return bj(v,o.v)^fu;
    }
}f[N][N],s[N][N],ans,pw[N],f1[N],s1[N];
int a[N];
gj operator +(gj a,gj b){
    gj ans;
    if(a.fu==b.fu) ans.fu=a.fu,ans.v=add(a.v,b.v);
    else{
        if(a.fu) swap(a,b);
        if(bj(a.v,b.v)) ans.fu=1,ans.v=del(b.v,a.v);
        else ans.fu=0,ans.v=del(a.v,b.v);
    }return ans;
}
gj min(gj a,gj b){return a<b?a:b;}
void operator +=(gj &a,const gj b){a=a+b;}
void write(gj a){
    if(a.fu) putchar('-'); reverse(a.v.begin(),a.v.end());
    rep(i,0,a.v.size()-1) putchar(a.v[i]+'0');
}
signed main(){
    rep(i,0,9) scanf("%d",&a[i]);
    rep(i,0,99){
        rep(j,0,i-1) pw[i].v.push_back(0);
        pw[i].v.push_back(1);
    }gj fu1; fu1.set(-1);
    rep(t,0,9){
        rep(i,0,99) f[0][i].set(min(a[t]-i,0)),s[0][i].set(a[t]-i);
        rep(i,1,99){
            f1[i]=f1[i-1],s1[i]=s1[i-1];
            rep(j,0,99-i){
                f[i][j].set(0),s[i][j].set(0);
                rep(c,0,9){
                    f[i][j]=min(f[i][j],s[i][j]+f[i-1][j+(t==c)]);
                    s[i][j]+=s[i-1][j+(t==c)];
                }
            }
            rep(c,1,9) f1[i]=min(f1[i],s1[i]+f[i-1][t==c]),s1[i]+=s[i-1][t==c];
        }int cur=0,ws=0; gj sum,res;
        if(!t){
            rep(i,1,99){
                rep(c,1,9){
                    if((sum+f[i-1][0]).fu){ws=i; break;}
                    sum+=s[i-1][0],res+=pw[i-1];
                }if(ws) break;
            }
        }else{
            per(i,99,1) if(!f1[i-1].fu){
                res+=pw[i-1],res+=fu1,sum=s1[i-1];
                rep(c,1,9){
                    if((sum+f[i-1][c==t]).fu){ws=i,cur+=(c==t); break;}
                    sum+=s[i-1][c==t],res+=pw[i-1];
                }break;
            }
        }
        per(i,ws-1,1) rep(c,0,9){
            if((sum+f[i-1][cur+(t==c)]).fu){cur+=(t==c); break;}
            sum+=s[i-1][cur+(t==c)],res+=pw[i-1];
        }if(!t) ans=res; else ans=min(ans,res);
    }write(ans);
}