Problem Address:http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1593
其实算是一道水题吧。
刚好看到有人提交，便做了一下。发现之前自己是做过的，但那个时候超时，之后不知道该怎么继续做。没想到这次很快就做出来了。
听过一个人的话，说的是，做了100道水题，水题没了，然后艰难地过了50道，之后又出现了100道水题，然后水题又没了，然后再艰难地过50道……如此反复。也许你并不知道你的进步，但是你确实是在进步。
讲下自己的做法。
之前是直接对每个数进行判断是否满足条件，这种方法是很费时的，即使优化出来，时间也会花很多。
这次我是直接进行筛选。把各个位是9的数以及9的倍数都先筛好；而不是对每个数进行判断。然后再计算在每个数之前有多少个数满足条件。后面这个有点小变动，就是根据输入的数，如果比之前的数小则可以直接查找出来，否则在之前计算的基础下继续计算下去。结果出来是节省了大量的时间和空间。
以下贴代码：
#include <iostream>using namespace std;int main(){ int num[20001],i,j,k,ct=1,jt=9,n; memset(num, 0, sizeof(num)); for (i=18; i<=20000; i=i+9) num[i] = 1;//9倍数 for (i=9; i<=20000; i=i+10) num[i] = 1;//个位是9 //十位是9 for (i=90; i<=99; i++) num[i] = 1; for (j=0; j<=9; j++) { for (k=100; k<=19900; k=k+100) { num[k+j+90] = 1; } } //百位是9 for (i=900; i<=999; i++) num[i] = 1; for (j=0; j<=99; j++) { for (k=1000; k<=19000; k=k+1000) { num[k+j+900] = 1; } } //千位是9 for (i=9000; i<=9999; i++) num[i] = 1; for (i=19000; i<=19999; i++) num[i] = 1; while(scanf("%d", &n)!=EOF) { if (n>jt) { for (i=jt+1; i<=n; i++) { if (num[i]==1) ct++; num[i] = ct; } jt=n; } printf("%d/n", num[n]); } return 0;}
