题意：

如果一个十进制非负整数的所有数位从高位到低位是不减的，我们称它为“上升数”，例如1558,11,3,0都是上升数，而10,20170312则不是；

给定整数N，求最小的k使得N能被表示为k个上升数之和。

$1\leq N\leq 10^{500000}$

题解：

一个结论：每个上升数必定能被分解为九个全一数的和；

所谓“全一数”就是指1,1111,11111111这种每一位数都为1的数（包括0），证明显然。

设N可以被分解成K个全一数之和，显然答案$k=\lceil\frac{K}{9}\rceil$；

由于全一数不好处理，我们可以把一个长度为$l$的全一数变成$\frac{(10^{l+1}-1)}{9}$，那么有：

$N=\sum\limits_{i=1}^{K}\frac{(10^x)}{9}$（此处$x$代表不确定的位数）

$9N=\sum\limits_{i=1}^{K}(10^x-1)$

$9N+K=\sum\limits_{i=1}^{K}10^x$

这个式子是什么意思呢？如果不考虑进位，右边每一项都会使数位和+1，那么总体就说明$9N+K$的数位和等于$K$的数位和，此时$K$一定是9的倍数；

如果考虑进位，那么每进一位数位和就会减少9，因此$K$仍然要是9的倍数。

由于答案最多不会超过N的位数，枚举k，写个高精度乱做就行了。。。注意加法的时候没有进位就要break，这样是均摊$O(1)$的，否则是$O(n^2)$的。

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 2147483647

 #define eps 1e-9

 using namespace std;

 typedef long long ll;

 int n,tot,a[];

 char s[];

 void mul(int a[],int &n,int k){

     int p=;

     tot=;

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

         p=a[i]*k+p;

         a[i]=p%;

         tot+=a[i];

         p/=;

     }

     if(p)a[++n]=p;

     tot+=p;

 }

 void add(int a[],int &n,int k){

     int p=;

     tot-=a[];

     a[]+=k;

     p=a[]/;

     a[]%=;

     tot+=a[];

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

         tot-=a[i];

         a[i]+=p;

         p=a[i]/;

         a[i]%=;

         tot+=a[i];

         if(!p)break;

     }

     if(p)a[++n]=p;

     tot+=p;

 }

 int main(){

     scanf("%s",s);

     n=strlen(s);

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

         a[i]=s[n-i]-'';

     }

     mul(a,n,);

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

         add(a,n,);

         if(tot%==&&i*>=tot)return printf("%d",i),;

     }

     return ;

 }

巴特西

[agc011e]increasing numbers

题意：

题解：

代码：

最新文章

热门文章