题目大意

JOI 君有一个介于

1

到

N

之间的整数，他通过若干次操作（每次操作将当前整数的各位数字之和加到该整数上）后，得到了整数

N

。现在给你

N

，请计算 JOI 君一开始可能会有几个整数。

思路分析

对于这道题目，如果我们正向枚举再一个个判断，效率特别低。因此我们可以使用 dfs 来反向枚举。
从

N

开始，向前找可以通过一次操作就得到当前数的整数（即前驱数），并放到 set 里面，直到找不到前驱数，此时 set 的长度就是答案。
另外，

N

最大不超过

10000000

，所以前驱数的位数一定是小于

7

的，则前驱数的个位数字之和最大不超过

54

，我们可以根据这个来缩小枚举范围，从而优化时间复杂度。

AC Code

不要抄袭

CPP

#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;
}

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

文章操作