题解 AT2341 【Increasing Numbers】

· · 题解

广告 && 吐槽

蒟蒻のblog

请各位同学不要忽略这题的想出来的思维难度，再怎么说普及-也太过分了，代码难度不是决定题目难度的唯一标准！

思路

首先，我们观察一下上升数的性质

可以发现，它一定可以表示为最多9个全是1的数字的和

那么我们设N可以被表示成k个上升数的和，同时我们设p_i=\underbrace{111\cdots 11}_{i}

我们令a_{i,j}表示构成N的第I个上升数的第j个全1数的位数

那么可以写出这样的式子

N=\sum_{i=1}^k\sum_{j=1}^9 p_{a[i][j]}

我们发现，p_{i,j}这样子摆在这里非常不好操作，那么我们继续观察p_i的性质，发现：

p_i=\frac{10^i - 1}{9}

所以上式可以写成：

N=\sum_{i=1}^k\sum_{j=1}^9 \frac{10^{a[i][j]}-1}{9}

我们把9乘过去，再把右边的9k个1加过去，得到：

9N+9k=\sum_{i=1}^k\sum_{j=1}^910^{a[i][j]}

我们发现：右边这个东西，如果在所有的10的幂加起来的过程中，能够不进位的话，那么它的数位和一定是9k

如果它发生了进位，因为1次进位一定是-10+1，总数位和-9，而9k是9的倍数，所以这个东西的数位和一定是一个小于9k的9的倍数

再看左边，我们发现，实际上我们需要满足的就是9N+9k的数位和小于9k且是9的倍数，而9N+9k一定是9的倍数

所以我们只需要求出最小的k，使得9N+9k的数位和小于等于9k即可

由数学归纳法不难证明，本题中k\leq len(N)，所以我们只需要枚举k=1\cdots 5e5，只要维护一个高精度+即可，复杂度是担此操作均摊O(1)，总复杂度O(n)

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[1000010];int a[1000010];
int main(){
    scanf("%s",s);int n=strlen(s),i,j,sum=0,k;
    for(i=1;i<=n;i++) a[i]=(s[n-i]-'0')*9;
    for(i=1;i<=n;i++){
        a[i+1]+=a[i]/10;a[i]%=10;
    }
    if(a[n+1]) n++;
    for(i=1;i<=n;i++) sum+=a[i];
    for(k=1;k<=n*10;k++){
        a[1]+=9;sum+=9;
        j=1;
        while(j<=n){
            if(a[j]<10) break;
            sum-=10;a[j]-=10;
            sum++;a[j+1]++;
            j++;
            if(j==n&&a[j+1]) n++;//别忘了有可能加一位
        }
        if(sum<=9*k){//注意这里一定不要写成等于了
            printf("%d\n",k);return 0;
        }
    }
}