[Digit Generator, ACM/ICPC Seoul 2005, UVA1583]
大阻力是开10万数组的魄力…
反直觉的复杂度分析
#include <stdio.h>
#include <string.h>
int a[100005];
int main()
{memset(a, 0, sizeof(a));for(int i=1; i<100005; ++i) {int tmp1 = i;int tmp2 = i;while(tmp1>0) { tmp2+=tmp1%10; tmp1/=10; }if(a[tmp2]==0 || i<a[tmp2]) a[tmp2] = i;}int T, n;scanf("%d", &T);while(T--) {scanf("%d", &n);printf("%d\n", a[n]);}return 0;
}