Problem description
一本书的页数为N，页码从1开始编起，请你求出全部页码中，用了多少个0，1，2，…，9。其中一个页码不含多余的0，如n=1234时第5页不是0005，只是5。
Input format
一个正整数N（N<=10^9），表示总的页码。
Output format
共十行，第K行表示数字K－1的个数。
Algorithm design
模拟TLE/记忆化搜索AC
Problem analysis
模拟TLE
先敲一下暴力，方便对拍
从1枚举到n，每次将该数各位切分后加入答案、
O(nlog10n)
隐约觉得在切分的时候可以有些许优化把log10n提高一下
但不用想了复杂度里有n本身肯定过不了
记忆化搜索AC
由计数问题得到的经验：对于较大整数状态转移不是去头就是去尾
一开始想着去头，发现0不能做数头的问题约束了这个算法
所以采取去尾状态转移法，去掉尾之后如果num成了0直接退出
那么怎么状态转移呢？
不难发现，对于一个数如234而言
可以拆分为尾是0~9的数，又分为两大类：
1.对于尾是0~4 那么十位数就可以从1枚到23
2.对于尾是5~9 那么十位数就可以从1枚到22
之后以此类推，直到1位数无法拆分
既然如此就可以看出动态转移的基本模型了
但是，在确定尾并不是被真正“去”掉了，而只是在确定之后不参与枚举
那么答案数列里还要考虑枚举个数个尾
至于枚举个数可以很容易的写出来，num%10（-1）
想到这里还是简单递归，顶多比模拟多10分
再看有许多低位数字被反复的使用，自然联想出记忆化思想
因为要记忆化，图方便就对于0~9依次搜索
这样记忆化只用开一维数组，且可以直接复制
至于记忆化的范围，我觉得其实把常用的2，3位数记忆化就行了
但在编程中要有“得寸进寸”的思想，在确保不会爆空间的情况下尽可能记得多
所以我对于记忆化开了10^7..
这样就很容易过了
Source code
记忆化搜索
1 #include <bits/stdc++.h> 2 #define lim 10000000 3 4 using namespace std; 5 6 int n,ans[10],opt[10000001]; 7 //opt[i]表示数字1~i可拆分出的某个数字个数 8 9 void input() 10 { 11 freopen("test.in","r",stdin); 12 freopen("test.out","w",stdout); 13 cin>>n; 14 return ; 15 } 16 17 int search(int tar,int num) 18 { 19 if(num<1) 20 return 0; 21 //如果要拆分的数小于1，则拆分无意义 22 if(num<=lim&&opt[num]) 23 return opt[num]; 24 //如果可以记忆并被记忆过，则直接返回 25 int re=0; 26 if(tar&&tar<=num%10) 27 re=num/10+1; 28 //如果不为零，并且寻找的数不大于个位数，就可以考虑前面是0~num/10 29 else 30 re=num/10; 31 //如果为零，就不用考虑前面为0，如果大于个位数，就不用考虑num/10 32 re+=(num%10+1)*search(tar,num/10)+(9-num%10)*search(tar,num/10-1); 33 /* 34 对于不大于个位数的数字都可以延伸1~num/10 35 大于个位数的数字不考虑num/10 36 */ 37 if(num<=lim)opt[num]=re; 38 //可以记忆再记忆，不然就会数组越界 39 return re; 40 } 41 42 void output() 43 { 44 for(int i=0;i<=9;i++) 45 cout<<ans[i]<<endl; 46 //输出答案 47 fclose(stdin); 48 fclose(stdout); 49 return ; 50 } 51 52 int main() 53 { 54 input(); 55 for(int i=0;i<=9;i++) 56 { 57 memset(opt,0,sizeof(opt)); 58 ans[i]+=search(i,n); 59 //针对0~9依次搜索 60 } 61 output(); 62 return 0; 63 }
over~