Digit Generator UVA - 1583

Digit Generator UVA - 1583

题目传送门：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4458

题目大意：生成元，一个数x的值为另一个数y的值加上y的各位数之和；
216 = 198 + 1 + 9 + 8；
2005 = 1979 + 1 + 9 + 7 + 9；
……..

分析：难道我们要枚举小于x的所有数字，挨个比较看哪个是它的生成元吗？
这样未免太过复杂，费时费力；

另一种方法就是打表，没错先让后台编译器去预处理一批数据，然后我们直接查表就好了；

怎么打表？
我们就先按照题意打一个大小为10086的表；

int ans[10086];
for(int i = 0; i < 10086; i++)//打满
{
    int x = i, y = i;
    while(x > 0){y += x%10; x /= 10}//当前数字x拆开加和，注意是在y的基础上加，因为我们直接就要达到“ans[y] = y的生成元”的目的；
    if(ans[y] == 0 || i < ans[y])//赋值，并且根据题意要小的（我们i从小到大加上去，所以也没必要判断要小的这一项，不过加上去完整些）
        ans[y] = i;
}

这个时候，ans[]就是符合我们要求的表单了；

还有很多数据量很大，但是又需要一次次查询比较的题目，也都可以先预处理出一个表格来解决，会节省很多时间，效率显著上升；

下面奉上AC Code：

#include<bits/stdc++.h>

using namespace std;
int ans[100086];

void makelist()//打表
{
    for(int i = 0; i < 100086; i++)
    {
        int x = i,y = i;
        while(x > 0)
        {
            y += x%10;
            x /= 10;
        }
        if(ans[y] == 0 || ans[y] > i)
            ans[y] = i;
    }
}

int main()
{

    int m,n;
    memset(ans,0,sizeof(ans));
    makelist();
    cin>>n;
    while(n--)
    {
        cin>>m;
        cout<<ans[m]<<endl;
    }
    return 0;
}