数位dp整理-白红宇

数位dp整理

阅读量：4318 次

发布时间：2019-06-06

本文共 7324 字，大约阅读时间需要 24 分钟。

数位dp的思想就在于递归，记录当前的某一个唯一状态，依次递归下去，要注意唯一。

数位dp常设的状态有当前位置，上一数字，是否具有前导零，是否有限制。

1.Beautiful numbers

题目大意：一个数是幸运数当且仅当这个数能整除所有位数，求[a,b]有多少幸运数

10以内的数的最小公倍数是2520，状态为当前位置，模2520的值，出现了哪些数字（状压，1，0删去）

#include
      
       #include
       
        #include
        
         using namespace std;const int maxa = 20;const int mod = 2520;long long  dp[maxa][1<<8][mod];#define LL long long//当前位置，限制，有哪些数，模int num[maxa];LL dfs(int pos, int limit, int val, int numb){    if(pos == 0){        for(int i = 2; i < 10; i++){            if((1<<(i-2)) & val){                if(numb % i) return 0;            }        }return 1;    }    if(!limit && dp[pos][val][numb] != -1) return dp[pos][val][numb];    int nn = limit?num[pos]:9;    LL res = 0;    for(int i = 0; i <= nn; i++){        res += dfs(pos-1, limit & (i ==nn), i<2?val:val|(1<<(i-2)), (numb*10+i)%mod);    }    if(!limit) dp[pos][val][numb] = res;    return res;}LL ANS(LL n){    int leng = 0;    while(n){        num[++leng] = n %10;        n /= 10;    }    return dfs(leng, 1, 0, 0);}int main(){    int t;    LL a, b;    memset(dp, -1, sizeof(dp));    scanf("%d", &t);    while(t--){        cin>>a>>b;        if(a > b)swap(a, b);        cout<

View Code

题目大意，求最长上升序列为k的数在[a,b]出现了多少次，

lis的log时间的思想是换掉长度和当前数字一样并且大于当前的数字的数，用的是对列维护的

在这里我们可以这样比如当前最长是1346这个队列，当前数字是2，就能用2区替换3，因为到2的最长序列和3是一样的并且2还比三小，队列就变成了1246

状态是位数，序列（状压掉），K（是为了以后出现K省时间

#include
      
       #include
       
        #include
        
         using namespace std;#define LL long longconst int maxa = 20;LL dp[maxa][1<<10][11];int num[maxa];int Next[1<<10][10];int Hash[1<<10];int K;int go(int now, int k){    int kk = -1;    for(int i = k; i < 10; i ++){       if((1<
         
          >a>>b>>K;        cout <<"Case #"<
          
           <<": "<

View Code

题意：求[a,b]有多少数字里有62或含有4

状态，位数，到当前为满足或不满足

#include
      
       #include
       
        #include
        
         using namespace std;const int maxa = 10;int dp[maxa][maxa][2];int num[maxa];int dfs(int pos, int limit, int ye, int last){    if(pos == 0){        return ye;    }    if(!limit && -1 != dp[pos][last][ye])        return dp[pos][last][ye];    int nn = limit ? num[pos]:9;    int res = 0;    for(int i = 0; i <= nn; i++){        res += dfs(pos-1, limit & (i==nn),i == 4 | ye | (last == 6&& i ==2), i);    }    if(!limit){        dp[pos][last][ye] = res;    }    return res;}int ans(int a){    int leng = 0;    while(a){        num[++leng] = a%10;        a /=10;    }    return dfs(leng, 1, 0, 0);}int main(){    memset(dp, -1, sizeof(dp));    int a, b;    while(scanf("%d%d", &a, &b), a+b){        cout<

View Code

和3思路一模一样

#include
      
       #include
       
        #include
        
         using namespace std;const long long maxa = 20;long long dp[maxa][maxa][2];long long num[maxa];long long dfs(long long pos, long long limit, long long ye, long long last){    if(pos == 0){        return ye;    }    if(!limit && -1 != dp[pos][last][ye])        return dp[pos][last][ye];    long long nn = limit ? num[pos]:9;    long long res = 0;    for(long long i = 0; i <= nn; i++){        res += dfs(pos-1, limit & (i==nn),ye | (last == 4&& i ==9), i);    }    if(!limit){        dp[pos][last][ye] = res;    }    return res;}long long ans(long long a){    long long leng = 0;    while(a){        num[++leng] = a%10;        a /=10;    }    return dfs(leng, 1, 0, 0);}int main(){    memset(dp, -1, sizeof(dp));    long long a, b, t;    cin>>t;    while(t--){        cin>>a;        cout<
         
          <

View Code

题目大意：求[a,b]有多少数字二进制0的个数>=1的个数

注意前导零

状态：位数，0比1多的个数，是否有前导零。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxa = 100;int dp[maxa][2*maxa][2];int num[maxa];int dfs(int pos, int limit, int re, int isZero){    //printf("%d %d %d %d\n", pos, limit, re, isZero);    if(pos == 0){
    //printf("%d\n", (re >= 50));        return (re >= 50);    }    if(!limit && dp[pos][re][isZero] != -1){        //printf("%d %d %d %d %d\n", pos, limit, re, isZero, dp[pos][re]);        return dp[pos][re][isZero];    }    int nn = limit ? num[pos]:1;    int res = 0;    for(int i = 0;i <= nn ; i++){       res += dfs(pos-1, limit &(i ==nn), (isZero && i==0)?re:(i==0?re+1:re-1), isZero && (i==0));    }    if(!limit)        dp[pos][re][isZero] = res;    return res;}int ans(int n){    int leng = 0;    while(n){        num[++leng] = n %2;        n /= 2;    }    return dfs(leng, 1, 50, 1);}int main(){    memset(dp, -1, sizeof(dp));    int a, b;    //printf("%d\n", ans(12));    while(scanf("%d%d", &a, &b)!=EOF){        //printf("%d %d\n", ans(b), ans(a-1));        printf("%d\n",ans(b) - ans(a-1));    }    return 0;}

View Code

题目大意：一个数十平衡数的条件是将这个数看成是一排砝码，天平的支点在某一个数字上，能使两边是平衡的

hint:4139 is a balanced number with pivot fixed at 3. The torqueses are 4*2 + 1*1 = 9 and 9*1 = 9

问在[a, b]区间有多少数是平衡数.

思路dp[][][]，四维分别是，位置 ,中间支点的位置，左边减去右边的值

需要注意的就是前导零问题，好久没刷数位dp的题被这个卡了半天

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxa = 20;const int maxn = 2000;long long dp[maxa][10][maxa][maxn];//位置，当前位置的数字,中间支点的位置，左边减去右边的值int N[maxa];long long dfs(int len, int nn, int point, int num, int limit, int zero){    if(len == -1){        return num == 0 && zero == 0;    }    if(num < 0)return 0;    if(!zero && !limit && dp[len][nn][point][num]!= -1){
    //printf("+");        return dp[len][nn][point][num];    }    int l = limit?N[len]:9;    long long sum = 0;    for(int i = 0; i <= l; i++){
    //printf("+");        sum += dfs(len-1, i, point, (len - point) * i+num, limit && (i == l), zero && (i==0));    }    if(!limit && !zero) dp[len][nn][point][num] = sum;    return sum;}long long ans(long long n){    if(n < 0)return 0;    int o = 0;    while(n){        N[o++] = n%10;        n /= 10;    }    long long sum = 0;    for(int i = 0;i < o; i++){        sum += dfs(o-1, 0, i, 0, 1, 1);    }    sum ++;    return sum;}int main(){    memset(dp, -1, sizeof(dp));    //cout<
          
           >a>>b;        //cout<
           
            <

View Code

题目大意：一个数是lala数时，这个数作为字符串里面含有13，并且这个数能被13整除

思路：

int dp[maxa][2][2][13];

//位置，上一个数是否是1，是否之前已经凑齐13，当前模13的值

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxa = 12;int dp[maxa][2][2][13];//位置，上一个数是否是1，是否之前已经凑齐13，当前模13的值int nn[maxa];int dfs(int pos, bool one, bool lala, int num, bool limit){    if(pos == -1){        return lala == 1 && num == 0;    }    if(!limit && dp[pos][one][lala][num] != -1)return dp[pos][one][lala][num];    int l = limit ? nn[pos]: 9;    int sum = 0;    for(int i = 0; i <= l; i++){        sum += dfs(pos-1, i == 1, lala || (one && i == 3), (int(num + i*pow(10, pos)))% 13, limit && i == l);    }    if(!limit){        dp[pos][one][lala][num] = sum;    }    return sum;}int ans(int n){    int o = 0;    while(n){        nn[o++] = n%10;        n /= 10;    }    return dfs(o-1, 0, 0, 0, 1);}int main(){    memset(dp, -1, sizeof(dp));    int n;    while(scanf("%d", &n)!=EOF){        printf("%d\n", ans(n));    }}