自动搬运

查看原文

来自洛谷，原作者为

	MEKHANE Order And Ruin

搬运于2025-08-24 22:15:54，当前版本为作者最后更新于2024-01-29 15:11:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

没有题解补一篇。

不难发现每一位是独立的，仅需求出对于数 $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);
}