算法基础之计数问题

计数问题

• 核心思想： 数位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