题解 CF1355A 【Sequence with Digits】

· · 题解

显然，当 a_{i} 的数码中出现‘0’时，它就会停止变化，那么最终的答案就是 a_{i}。

而如果你是通过打暴力发现这个结论的，你同时也会发现 i 的值并不是很大。于是这题的解法就是不断暴力递推，直到 a_{i} 的数码中出现了0。

但是，要注意，这是有可能超时的。因为我们现在还不知道 i 的范围。 那接下来我们分析一下这个算法的时间复杂度。

只考虑 a_{i} 的百位数，那么，当 a_{i} 首次出现了百位向千位上的进位时，也就是当 a_{i}-a_{1}\ge 1000时，百位上一定会出现一次0。因为1\le MinDigit(x)\cdot MaxDigit(x) \le 81 。

故而，累加的和最多为1000，那么累加的次数也就是 i 最大为1000。最坏时间复杂度为 O(1000^{2})，肯定不会超时。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;

inline ll read(){
    ll x=0,fh=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*fh;
}

inline int f(ll x){//f(x)=MinDigit(x)*MaxDigit(x)
    int mn=100,mx=0;
    while(x){
        int k=x%10;
        x/=10;
        mn=min(mn,k);
        mx=max(mx,k);
    }
    return mn*mx;
}

void work(){
    ll a=read(),k=read();//注意long long
    for(ll i=1;i<k;++i){
        int w=f(a);
        if(w==0){
            break;
        }
        a+=f(a);
    }
    printf("%lld\n",a);
    //puts("");
}
int main(){
    int T=read();
    while(T--){
        work();
    }
    return 0;
}

点个赞再走吧qwq