在《编程之美》中看到过这道题,在《编》中求第 i 位数字贡献的次数时还需要考虑 i之前和之后的数字,计算也蛮麻烦的。
后来搜了一些网友的IDEA,发现了更好的解法,先自己总结如下:
首先我们通过两个例子来理解这个规律,我们把计算这个出现次数的函数记为 f(n)。
1. n=12345时, 首位为1。如果我们模拟这个1-n的序列,我们发现从 0 ~ 9999 时,首位并未出现,所以此时1出现的次数为 f(9999);然后从10000~12345时,首位1出现了 0~2345即(2345+1)次,而在从10000~12345递增的过程中,后四位数字也有1出现,而且与首位的1是无关的,即这个过程中后四位出现的次数是与从0~2345中出现的次数是等价的,即f (2345) ;
所以对n=12345来讲,f (12345) = f(9999) + 2345+1 + f( 2345) ;
2.n=56789,即首位不为1的时候。与第一种情况类似,我们此时可以将0~n的递增氛围四个区段: 0~9999 ; 10000~ 19999 ; 20000 ~ 49999 ; 50000 ~ 56789 ;
第一个区段中1出现的次数与首位是无关的,所以是 f ( 9999 ) ;
第二个区段首位一直保持为1,总共出现了10000次,后四位贡献了 f( 9999) 次,分析与 第一种情况相同的;
第三个区段中首位一直不为1,所以等价于后四位的递增,但注意这个完整的递增出现了3次(20000~29999;30000~39999;40000~49999),所以是 (5-2)* f(9999)次;
第四个区段中首位也一直不为1,所以等价于后四位的递增,即0~6789,所以是 f(6789 )次;
所以 f (n ) = f (56789 ) = (5-2+2) * f( 9999 ) + 10000 + f(6789 ) 次;
分析到这里应该很好写代码了,改天写一个贴上来。
说不如做,现在就写吧。
#include<iostream> #include<vector> using namespace std; long long find1(int n) { if(n<10) { return n>=1?1:0; } int factor=1; while(factor<=n) { factor*=10; } factor/=10; int first=n/factor; long long res=0; if ( first==1 ) { int other = n%factor; res= other+1+ find1(factor-1)+find1(other); } else { int other = n%factor; res= first*find1(factor-1) + find1(other)+factor; } return res; } int main() { int n; scanf("%d",&n); long long res=find1(n); printf("%ld\n",res); }
测试数据用的:http://pat.zju.edu.cn/contests/pat-practise/1049,代码已通过测试。