题解：P14337 [JOI2020 预选赛 R2] 求和 / Digit Sum

· · 题解

题目链接

题目大意

JOI 君有一个介于 1 到 N 之间的整数，他通过若干次操作 （ 每次操作将当前整数的各位数字之和加到该整数上 ） 后，得到了整数 N 。现在给你 N ，请计算 JOI 君一开始可能会有几个整数。

思路分析

对于这道题目，如果我们正向枚举再一个个判断，效率特别低。因此我们可以使用 dfs 来反向枚举。
从 N 开始，向前找可以通过一次操作就得到当前数的整数 （ 即前驱数 ） ，并放到 set 里面，直到找不到前驱数，此时 set 的长度就是答案。
另外， N 最大不超过 10000000 ，所以前驱数的位数一定是小于 7 的，则前驱数的个位数字之和最大不超过 54 ，我们可以根据这个来缩小枚举范围，从而优化时间复杂度。

AC Code

不要抄袭

#include<bits/stdc++.h>
using namespace std;

int N;
set<int> st;

int get(int x)
{
    int sum=0;
    while(x > 0)
    {
        sum+=x%10;
        x/=10;
    }
    return sum;
}

void dfs(int y)
{
    //最大数字和不超过54
    int start=max(1,y-54);
    for(int x=start;x<y;x++)
    {
        if(x+get(x) == y && !st.count(x))//x是y的前驱数 
        {
            st.insert(x);
            dfs(x);
        }
    }
}

int main()
{
    cin >> N;
    st.insert(N);

    dfs(N);

    cout << st.size();

    return 0;
}