算法基础之计数问题

2023-12-28 21:47:37

计数问题

  • 核心思想: 数位dp / 累加

累加

  • ? 分情况讨论 :

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

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

      2. 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;
          }
        
    • 在这里插入图片描述

数位dp

文章来源:https://blog.csdn.net/Pisasama/article/details/135278139
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。