[编程笔记]-Digital_DP数位DP

前言

要不是见到，我绝对不会把这种数奥题和信竞联系在一起。

甚至小学数奥hh

概念

统计数字每位上数字出现的次数。

解释不便，直接给题。

AcWing338-计数问题

#解决
我们就可以想到前缀和了。

count[i][j]表示从第1个数到第i个数出现的j的个数。

这就是大致思路。

假设当前数字是abcdefg，当前查找数字是x。

那么我们只需要求出在1~n个数中，x在不同数位分别出现的次数即可。

举个例子，现在我们在查找1在第4个数位出现的次数。

我们就需要找出所有形如xxx1yyy的数即可。

• 当000≤xxx<abc时，那么000≤yyy≤999。一共就有(abc*1000)种选法。
• 当xxx=abc时
  • d<1，abc1yyy>abc0efg，无答案
  • d=1，yyy=000~efg，(efg+1)种
  • d>1，yyy=000~999，1000种

然后就OK了。

#include<bits/stdc++.h>
using namespace std;

int a,b;

int getnum(vector<int> num,int l,int r){
    int res=0;
    for(int i=l;i>=r;i--){
        res*=10;
        res+=num[i];
    }
    return res;
}

int powten(int x){
    int res=1;
    while(x--){
        res*=10;
    }
    return res;
}

int count(int num,int x){
    int res=0;
    vector<int> nn;
    while(num){
        nn.push_back(num%10);
        num/=10;
    }
    int n=nn.size();
    for(int i=n-1-!x;i>=0;i--){//防止前导零
        res+=getnum(nn,n-1,i+1)*powten(i);//getnum:从个位存到最高位，要从高位循环回低位。
                                          //powten:i存的是倒序位数-1，就不用多减一个1了。
        if(!x)res-=powten(i);//还是会多算一个情况(000)，消掉。
        if(nn[i]==x)res+=getnum(nn,i-1,0)+1;
        if(nn[i]>x)res+=powten(i);
    }
    return res;
}

int main(){
    while(cin>>a>>b){
        if(a==0&&b==0)break;
        if(a>b)swap(a,b);
        for(int i=0;i<=9;i++){
            cout<<count(b,i)-count(a-1,i)<<" ";
        }
        cout<<endl;
    }
    return 0;
}

是挺难的。

完结撒花o(￣︶￣)o