题目描述


请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。

比如给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。


输入描述:

输入共1行，为两个正整数L和R，之间用一个空格隔开。

输出描述:

输出共1行，表示数字2出现的次数。

示例1

输入
2 22
输出
6

示例2

输入
2 100
输出
20

备注:

解答

这道题很显然是削弱版的51nod P1042。那么显然我们需要使用数位DP解题。

思路大致是这样的：

对于每一个数字，考虑三种影响关系：

1. 它对低位的影响

2. 它对高位的影响

3. 高位对低位的影响


然后在递归中实现这三种关系的计算即可。

代码： 
 #include <stdio.h>
   #include <cstring>
   #include <algorithm>
   using namespace std;
   #define CLR(a,b) memset(a,b,sizeof(a))
  #define INF 0x3f3f3f3f
  #define LL long long
   void dp(LL n , LL m , LL *c)
   {
     LL x = n % 10;
    LL y = n / 10;
      for (int i = 0 ; i <= x ; i++)
         c[i] += m;        //当前位对低位的影响，每个都是0~9的范围 
     for (int i = 0 ; i <= 9 ; i++)
         c[i] += m * y;        //当前位对的高位影响（高位不为0，在上一个循环中算过） 
      c[0] -= m;        //排除前导0的情况
     LL t = y;
     while (t)        //高位对低位的影响，即都为最大限制数 
      {
         c[t % 10] += (x+1) * m;        //算上0
          t /= 10; 
      }
     if (y)
          dp(y-1 , m*10 , c);        //y值在上个while中算过，算下一个未限制数 
  }
  int main()
  {
      LL r,l;
     LL a[10] = {0};
      LL b[10] = {0};
      scanf ("%lld %lld",&l,&r);
      dp(r , 1 , a);
      dp(l-1 , 1 , b);
     printf("%lld\n",a[2]-b[2]);
      return 0;
  }


来源：Ilverene