数位dp整理

时间：2022-06-04 18:04:24

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

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

1.CodeForces 55DBeautiful numbers

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

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

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int maxa = ;

const int mod = ;

long long  dp[maxa][<<][mod];

#define LL long long

//当前位置，限制，有哪些数，模

int num[maxa];

LL dfs(int pos, int limit, int val, int numb){

    if(pos == ){

        for(int i = ; i < ; i++){

            if((<<(i-)) & val){

                if(numb % i) return ;

            }

        }return ;

    }

    if(!limit && dp[pos][val][numb] != -) return dp[pos][val][numb];

    int nn = limit?num[pos]:;

    LL res = ;

    for(int i = ; i <= nn; i++){

        res += dfs(pos-, limit & (i ==nn), i<?val:val|(<<(i-)), (numb*+i)%mod);

    }

    if(!limit) dp[pos][val][numb] = res;

    return res;

}

LL ANS(LL n){

    int leng = ;

    while(n){

        num[++leng] = n %;

        n /= ;

    }

    return dfs(leng, , , );

}

int main(){

    int t;

    LL a, b;

    memset(dp, -, sizeof(dp));

    scanf("%d", &t);

    while(t--){

        cin>>a>>b;

        if(a > b)swap(a, b);

        cout<<ANS(b) - ANS(a-)<<endl;

    }

}

2.HDU 4352

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

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

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

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

#include<iostream>

#include<string.h>

#include<stdio.h>

using namespace std;

#define LL long long

const int maxa = ;

LL dp[maxa][<<][];

int num[maxa];

int Next[<<][];

int Hash[<<];

int K;

int go(int now, int k){

    int kk = -;

    for(int i = k; i < ; i ++){

       if((<<i) & now){

          kk = i;

         break;

       }

    }

    if(kk == -){

        return now|(<<k);

    }

    now ^= (<<kk);

    now |= (<<k);

    return now;

}

void init(){

    memset(dp, -, sizeof(dp));

    for(int i = ; i < (<<); i++){

        for(int k = ; k < ; k++){

            if(i&(<<k))

                Hash[i] ++;

        }

    }

    for(int i = ; i < (<<); i++){

        for(int k = ; k < ; k++){

            Next[i][k] = go(i, k);

        }

    }

}

LL dfs(int pos, int mask, int isZero, int limit){//printf("%d %d %d %d\n", pos, mask, isZero, limit);

    if(pos ==){//printf("%d %d\n", Hash[mask], K == mask);

        return Hash[mask] == K;

    }

    if(!limit && -!=dp[pos][mask][K])

        return dp[pos][mask][K];

    int nn = limit?num[pos]:;

    LL res = ;

    for(int i = ; i <= nn; i++){

        res += dfs(pos-,( isZero && (i ==))? mask:Next[mask][i],isZero&(i==), limit &(i ==nn));

    }

    if(!limit){

        dp[pos][mask][K] = res;

    }

    return res;

}

LL ANS(LL n){

    int leng = ;

    while(n){

        num[++leng] = n%;

        n/= ;

    }

    return dfs(leng, , , );

}

int main(){

    init();

    int t;

    int Case = ;

    LL a, b;

    scanf("%d", &t);

    while(t--){

        cin>>a>>b>>K;

        cout <<"Case #"<<Case++<<": "<<ANS(b) - ANS(a-)<<endl;

    }

    return ;

}

3.HDU 2089

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

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

#include<iostream>

#include<string.h>

#include<stdio.h>

using namespace std;

const int maxa = ;

int dp[maxa][maxa][];

int num[maxa];

int dfs(int pos, int limit, int ye, int last){

    if(pos == ){

        return ye;

    }

    if(!limit && - != dp[pos][last][ye])

        return dp[pos][last][ye];

    int nn = limit ? num[pos]:;

    int res = ;

    for(int i = ; i <= nn; i++){

        res += dfs(pos-, limit & (i==nn),i ==  | ye | (last == && i ==), i);

    }

    if(!limit){

        dp[pos][last][ye] = res;

    }

    return res;

}

int ans(int a){

    int leng = ;

    while(a){

        num[++leng] = a%;

        a /=;

    }

    return dfs(leng, , , );

}

int main(){

    memset(dp, -, sizeof(dp));

    int a, b;

    while(scanf("%d%d", &a, &b), a+b){

        cout<<b-a+-(ans(b) - ans(a-))<<endl;

    }

    return ;

}

4.HDU 3555

和3思路一模一样

#include<iostream>

#include<string.h>

#include<stdio.h>

using namespace std;

const long long maxa = ;

long long dp[maxa][maxa][];

long long num[maxa];

long long dfs(long long pos, long long limit, long long ye, long long last){

    if(pos == ){

        return ye;

    }

    if(!limit && - != dp[pos][last][ye])

        return dp[pos][last][ye];

    long long nn = limit ? num[pos]:;

    long long res = ;

    for(long long i = ; i <= nn; i++){

        res += dfs(pos-, limit & (i==nn),ye | (last == && i ==), i);

    }

    if(!limit){

        dp[pos][last][ye] = res;

    }

    return res;

}

long long ans(long long a){

    long long leng = ;

    while(a){

        num[++leng] = a%;

        a /=;

    }

    return dfs(leng, , , );

}

int main(){

    memset(dp, -, sizeof(dp));

    long long a, b, t;

    cin>>t;

    while(t--){

        cin>>a;

        cout<<ans(a)<<endl;

    }

    return ;

}

5.POJ 3252

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

注意前导零

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

#include<string.h>

#include<stdio.h>

#include<iostream>

using namespace std;

const int maxa = ;

int dp[maxa][*maxa][];

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 == ){//printf("%d\n", (re >= 50));

        return (re >= );

    }

    if(!limit && dp[pos][re][isZero] != -){

        //printf("%d %d %d %d %d\n", pos, limit, re, isZero, dp[pos][re]);

        return dp[pos][re][isZero];

    }

    int nn = limit ? num[pos]:;

    int res = ;

    for(int i = ;i <= nn ; i++){

       res += dfs(pos-, limit &(i ==nn), (isZero && i==)?re:(i==?re+:re-), isZero && (i==));

    }

    if(!limit)

        dp[pos][re][isZero] = res;

    return res;

}

int ans(int n){

    int leng = ;

    while(n){

        num[++leng] = n %;

        n /= ;

    }

    return dfs(leng, , , );

}

int main(){

    memset(dp, -, 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-));

    }

    return ;

}

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

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<iostream>

#include<string.h>

#include<cmath>

#include<stdio.h>

using namespace std;

const int maxa = ;

const int maxn = ;

long long dp[maxa][][maxa][maxn];

//位置，当前位置的数字,中间支点的位置，左边减去右边的值

int N[maxa];

long long dfs(int len, int nn, int point, int num, int limit, int zero){

    if(len == -){

        return num ==  && zero == ;

    }

    if(num < )return ;

    if(!zero && !limit && dp[len][nn][point][num]!= -){//printf("+");

        return dp[len][nn][point][num];

    }

    int l = limit?N[len]:;

    long long sum = ;

    for(int i = ; i <= l; i++){//printf("+");

        sum += dfs(len-, i, point, (len - point) * i+num, limit && (i == l), zero && (i==));

    }

    if(!limit && !zero) dp[len][nn][point][num] = sum;

    return sum;

}

long long ans(long long n){

    if(n < )return ;

    int o = ;

    while(n){

        N[o++] = n%;

        n /= ;

    }

    long long sum = ;

    for(int i = ;i < o; i++){

        sum += dfs(o-, , i, , , );

    }

    sum ++;

    return sum;

}

int main(){

    memset(dp, -, sizeof(dp));

    //cout<<ans((long long)(9))<<endl;return 0;

    int t;

    scanf("%d", &t);

    while(t--){

        long long a, b;

        cin>>a>>b;

        //cout<<ans(b)<<endl;

        cout<<ans(b) - ans(a-)<<endl;

    }

}

7.HDU 3652

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

思路：
int dp[maxa][2][2][13];
//位置，上一个数是否是1，是否之前已经凑齐13，当前模13的值

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<cmath>

using namespace std;

const int maxa = ;

int dp[maxa][][][];

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

int nn[maxa];

int dfs(int pos, bool one, bool lala, int num, bool limit){

    if(pos == -){

        return lala ==  && num == ;

    }

    if(!limit && dp[pos][one][lala][num] != -)return dp[pos][one][lala][num];

    int l = limit ? nn[pos]: ;

    int sum = ;

    for(int i = ; i <= l; i++){

        sum += dfs(pos-, i == , lala || (one && i == ), (int(num + i*pow(, pos)))% , limit && i == l);

    }

    if(!limit){

        dp[pos][one][lala][num] = sum;

    }

    return sum;

}

int ans(int n){

    int o = ;

    while(n){

        nn[o++] = n%;

        n /= ;

    }

    return dfs(o-, , , , );

}

int main(){

    memset(dp, -, sizeof(dp));

    int n;

    while(scanf("%d", &n)!=EOF){

        printf("%d\n", ans(n));

    }

}

相关文章