题解 P1179 【数字统计】

这也许是水题，但是我做复杂了…… 我的方法有O(lg r)的时空复杂度哦~ 思路是:ans=f(r)-f(l-1)，其中f(x)表示[1,x]的整数中所含数字2的个数。 f(x)的求法是:逐位求数字2的个数。从右到左第i位(0≤i≤$\lg x$)数字2的个数为$\frac{x}{10^{i+1}}\times 10^{i}+e_{i}$。(注意！要先除再乘！) 其中$e_{i}$的求法为: 1.若$x \mod 10^{i+1}\geq 3\time 10\times 10^{i}$，则$e_{i}=10^{i} $ 2.若$2\time 10\times 10^{i} \leq x \mod 10^{i+1}< 3\time 10\times 10^{i}$，则$e_{i}=x \mod 10^{i+1}-2\time 10\times 10^{i}+1 $。 ---------------------------------------------------- 这里对10的自然数次幂打了表，防止重复计算。 下面是代码: ```cpp #include <stdio.h> //#include <math.h> //此处说明，使用C提交时，竟不能使用数学函数！所以便不用log，而强制把计算的i的上界改为6 int twos(int n); //twos(n)即f(x) int tpow[]={1,10,100,1000,10000,100000,1000000,10000000}; //打表10的幂 int main(void){ int l,r; scanf("%d%d",&l,&r); printf("%d",twos(r)-twos(l-1)); return 0; } int twos(int n){ int count=0,i; //int bits=log(n)/log(10)+1; //数学函数无法使用，故用下一行代之 const int bits=7; for (i=0;i<bits;i++){ count+=n/tpow[i+1]*tpow[i]; if (n%tpow[i+1]>=3*tpow[i]) count+=tpow[i]; else if (n%tpow[i+1]>=2*tpow[i]) count+=(n%tpow[i+1]-2*tpow[i]+1); } return count; } ```