算法基础之计数问题

计数问题

核心思想：数位dp / 累加

累加

分情况讨论：

xxx = 000 ~ abc –1 yyy = 000 ~ 999 共 abc * 1000 种

特别地，当枚举数字0时 (找第4位为0的数) 前三位不能从000开始了 否则没这个数不合法(有前导零)
xxx == abc

2.1. d < 1 , 不存在这样的数

2.2. d == 1 , yyy = 000 ~ efg 共 efg + 1

2.3. d > 1, yyy = 000 ~ 999 共1000种

  #include<iostream>
  
  using namespace std;
  typedef long long LL;
  
  int power10(int x)  //求10的x次方
  {
      int res = 1;
      while(x--) res *= 10;
      return res;
  }
  
  LL count(int n,int x)  // 求 1 ~ n 的x出现次数
  {
      LL res = 0;
      int l,r,cnt=0, m=n;
      
      while(m)  //求n的位数
      {
          cnt++;
          m /= 10;
      }
      
      for(int i=1;i<=cnt;i++)  //遍历每个位数
      {
          r = power10(i-1);  //求右半边的10的某次方
          l = n / (r * 10);  //求左半边的数
          
          if(x) res += l * r;  //x != 0
          else res += (l-1) * r;  // x == 0
          
          int d = (n / r) % 10;  // 求当前搜的的数
          
          if(d == x) res += (n % r) + 1;  //如果相等 是efg+1次
          else if (d > x) res += r;  //如果大于 是1000(10的某次方)
      }
      
      return res;
  }
  
  int main()
  {
      int a,b;
      
      while(cin>>a>>b , a||b)
      {
          if(a>b) swap(a,b);  //保证大小顺序
          
          for(int i=0;i<10;i++)  //遍历0 ~ 9 每个数
          {
              cout<<count(b, i) - count(a-1 , i)<<" ";  //类似前缀和
          }
          cout<<endl;
      }
      
      return 0;
  }