Kuangbin 带你飞 数位DP题解

时间：2021-05-18 14:55:13

以前一直不知道该咋搞这个比较好。

感觉推起来那个数字好麻烦。后来有一种比较好的写法就是直接的DFS写法。相应的ismax表示当前位是否有限制。

数位DP也是有一种类似模版的东西，不过需要好好理解。与其他模版不同。

主要还是状态的定义

模版就不整理了。直接上题。

另外这里有一道题是数位DP+自动机的放到自动机里做

HDU 2089 不要62

基本的数位DP可以用来理解DFS写法

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define PI 3.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

const int MAXN = ;

int dp[MAXN][];

int digit[MAXN],length;

int calcu(int len,bool issix,bool ismax)

{

    if (len == ) return ;

    if (!ismax && dp[len][issix] != -) return dp[len][issix];

    int limit = ismax ? digit[len] : ;

    int tot = ;

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

    {

        if ((issix && i == ) || i ==  ) continue;

        tot += calcu(len - ,i ==  ,ismax && i == limit);

    }

    if (ismax) return tot;

    else return dp[len][issix] = tot;

}

int slove(int x)

{

    int len = ;

    int num = x;

    while (num)

    {

        digit[++len] = num % ;

        num /= ;

    }

    return calcu(len,false,true);

}

int main()

{

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

    int l,r;

    while (scanf("%d%d",&l,&r) != EOF)

    {

        if (l ==  && r == ) break;

        if (l > r) swap(l,r);

        printf("%d\n",slove(r) - slove(l - ));

    }

    return ;

}

HDU 3555 Bomb

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define PI 3.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

const int MAXN = ;

LL dp[MAXN][];

int digit[MAXN];

LL calcu(int length,bool isfour,bool ismax)

{

    if (length == ) return ;

    if (!ismax && dp[length][isfour] >= ) return dp[length][isfour];

    LL tot = ;

    int limit = ismax ? digit[length] : ;

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

    {

        if (isfour && i == ) continue;

        tot += calcu(length - ,i == ,ismax && i == limit);

    }

    if (!ismax) return dp[length][isfour] = tot;

    return tot;

}

LL slove(LL x)

{

    int len = ;

    LL num = x;

    while (num)

    {

        digit[++len] = num % ;

        num /= ;

    }

    return calcu(len,false,true);

}

int main()

{

    int T,kase = ;

    scanf("%d",&T);

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

    while (T--)

    {

        LL N;

        scanf("%I64d",&N);

        printf("%I64d\n",N - slove(N) + );

    }

    return ;

}

POJ 3252 Round Numbers

统计二进制形式中0的个数比1的个数不小的数字的数目

很简单的只是进制变成了2进制，这里还要和下一个题目做一下比较。状态的定义不能想简单了

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define PI 3.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

const int MAXN = ;

LL dp[MAXN][MAXN][MAXN];

int digit[MAXN];

LL calcu(int length,int preone,int prezero,bool zero,bool ismax)

{

    if (length == ) return prezero >= preone;

    if (!ismax && dp[length][preone][prezero] >= ) return dp[length][preone][prezero];

    LL tot = ;

    int limit = ismax ? digit[length] : ;

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

    {

        int addone = ,addzero = ;

        if (i == ) addone = ;

        if (i == ) addzero = ;

        tot += calcu(length - ,preone +addone,(zero && i == ) ?  : prezero + addzero, zero && i ==  ,ismax && i == limit);

    }

    if (!ismax) return dp[length][preone][prezero] = tot;

    return tot;

}

LL slove(LL x)

{

    int len = ;

    LL num = x;

    while (num)

    {

        digit[++len] = num % ;

        num >>= ;

    }

    return calcu(len,,,true,true);

}

int main()

{

    LL l,r;

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

    while (scanf("%I64d%I64d",&l,&r) != EOF)

    {

       // printf("%I64d\n",slove(r));

        //printf("%I64d\n",slove(l - 1));

        //printf("%I64d\n",slove(l));

        printf("%I64d\n",slove(r) - slove(l - ));

    }

    return ;

}

Spoj BAlnum BALNUM - Balanced Numbers

这个题题意是统计十进制形式中奇数出现偶数次，偶数出现奇数次的数字 个数

为什么这道题状态不能向前边那个题，直接dp[i][j][k]第i位出现j个奇数k个偶数然后直接推，

看起来很简单，然而这个状态是错的。为什么？考虑dp[5][3][2]，他究竟表示什么。

可以在记忆花过程中直接返回这个值么？13522后边若干位和14688后边若干位都是这个dp状态！！

所以上述状态是错的。正确的是三进制状压。表示每个数字出现的次数的状态0，1，2

具体看代码

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define PI 3.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

const int MAXN = ;

const int MAXD = ;

LL dp[MAXN][MAXD];

int digit[MAXN];

//order : 9 8 7 6 5 4 3 2 1 0;

//num: 0 1 2 3 4 5 6 7 8 9

//sta : 0 no 1 odd 2 even

bool judge(int sta)

{

    int num[];

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

    {

        num[i] = sta % ;

        sta /= ;

    }

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

    {

        if (num[i] != )

        {

            if (i %  ==  && num[i] == ) return false;

            if (i %  ==  && num[i] == ) return false;

        }

    }

    return true;

}

int getsta(int x,int sta)

{

    int num[];

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

    {

        num[i] = sta % ;

        sta /= ;

    }

    if (num[x] == ) num[x] = ;

    else num[x] =  - num[x];

    int ret = ;

    for (int i =  ; i >=  ; i--)

        ret = ret *  + num[i];

    return ret;

}

LL calcu(int length,int presta,bool zero,bool ismax)

{

    if (length == ) return judge(presta);

    if (!ismax && dp[length][presta] >= ) return dp[length][presta];

    int limit = ismax ? digit[length] : ;

    LL ret = ;

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

    {

        ret += calcu(length - ,(zero && i == ) ?  : getsta(i,presta),zero && i == ,ismax && i == limit);

    }

    if (!ismax) return dp[length][presta] = ret;

    return ret;

}

LL slove(LL x)

{

    LL num = x;

    int len = ;

    while (num)

    {

        digit[++len] = num % ;

        num /= ;

    }

    return calcu(len,,true,true);

}

int main()

{

    int T;

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

    scanf("%d",&T);

    while (T--)

    {

        LL l,r;

        scanf("%lld%lld",&l,&r);

        //cout << slove(r) << endl;

        printf("%lld\n",slove(r) - slove(l - ));

    }

    return ;

}

Codeforces 55D Beautiful numbers

判断数字是否能整除他的十进制形式中所有非0数字的个数

注意到能整除所有位数实际上就是能整除这些位数的LCM，最大就是2520

那么状态定义dp[i][j][k] = val表示到达第i位对2520的摸为多少，当前的LCM为多少

另外代码里对LCM进行了哈希

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define PI 3.1415926535897932626

using namespace std;

LL gcd(LL a, LL b) {return a % b ==  ? b : gcd(b, a % b);}

LL lcm(LL a,LL b) {return a / gcd(a,b) * b;}

const int MAXN = ;

const int MAXD = ;

const LL MOD = ;

LL dp[][MAXD][MAXN];

int digit[MAXN];

int Hash[MAXD];

void init()

{

    int cas = ;

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

    {

        if (MOD % i == )

            Hash[i] = ++cas;

    }

}

LL calcu(int length,int premod,int prelcm,bool ismax)

{

    if (length == ) return premod % prelcm == ;

    if (!ismax && dp[length][premod][Hash[prelcm]] >= )

        return dp[length][premod][Hash[prelcm]];

    int limit = ismax ? digit[length] : ;

    LL tot = ;

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

    {

        int nextmod = (premod *  + i) % MOD;

        int nextlcm;

        if (i == ) nextlcm = prelcm;

        else nextlcm = lcm(prelcm,i);

        tot += calcu(length - ,nextmod,nextlcm,ismax && i == limit);

    }

    if (ismax) return tot;

    else return dp[length][premod][Hash[prelcm]] = tot;

}

LL slove(LL x)

{

    LL num = x,len = ;

    while (num)

    {

        digit[++len] = num % ;

        num /= ;

    }

    return calcu(len,,,true);

}

int main()

{

    init();

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

    int T;

    scanf("%d",&T);

    while (T--)

    {

        LL l,r;

        scanf("%I64d%I64d",&l,&r);

       // cout << slove(r) << endl;

        printf("%I64d\n",slove(r) - slove(l - ));

    }

    return ;

}

HDU 3709 Balanced Number

一开始觉得好难。后来发现只需要枚举支点。复杂度并不会高多少。20而已

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define PI 3.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

//此题枚举支点即可不用想麻烦了。

const int MAXN = ;

LL dp[MAXN][MAXN][MAXN * ];

int digit[MAXN];

LL calcu(int length,int premid,int preval,bool ismax)

{

    if (length == ) return preval == ;

    if (preval < ) return ;

    if (!ismax && dp[length][premid][preval] >= ) return dp[length][premid][preval];

    LL tot = ;

    int limit = ismax ? digit[length] : ;

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

    {

        int add = (length - premid) * i;

        int nextval = preval + add;

        tot += calcu(length - ,premid,nextval,ismax && i == limit);

    }

    if (!ismax) return dp[length][premid][preval] = tot;

    return tot;

}

LL slove(LL x)

{

    int len = ;

    LL num = x;

    while (num)

    {

        digit[++len] = num % ;

        num /= ;

    }

    LL ret = ;

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

        ret += calcu(len,i,,true);

    return ret - len + ;

}

int main()

{

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

    LL l,r;

    int T;

    scanf("%d",&T);

    while (T--)

    {

        scanf("%I64d%I64d",&l,&r);

        printf("%I64d\n",slove(r) - slove(l - ));

    }

    return ;

}

HDU 3652 B-number

包含13且整除13的数字个数

为什么不能直接dp[i][0/1]表示到达第i位是否出现13？同前面错误状态的比较

代码

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define PI 3.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

const int MAXN = ;

LL dp[MAXN][][];

int digit[MAXN];

LL calcu(int length,int presta,int premod,bool ismax)

{

    if (length == ) return (presta ==  && premod == );

    if (!ismax && dp[length][presta][premod] >= ) return dp[length][presta][premod];

    LL tot = ;

    int limit = ismax ? digit[length] : ;

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

    {

        int nextmod = (premod *  + i) % ;

        int nextsta = presta;

        if (presta ==  && i == ) nextsta = ;

        if (presta ==  && i != ) nextsta = ;

        if (presta ==  && i == ) nextsta = ;

        tot += calcu(length - ,nextsta,nextmod,ismax && i == limit);

    }

    if (!ismax) return dp[length][presta][premod] = tot;

    return tot;

}

LL slove(LL x)

{

    LL num = x;

    int len = ;

    while (num)

    {

        digit[++len] = num % ;

        num /= ;

    }

    return calcu(len,,,true);

}

int main()

{

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

    LL N;

    while (scanf("%I64d",&N) != EOF)

    {

        printf("%I64d\n",slove(N));

    }

    return ;

}

HDU 4352 XHXJ's LIS

统计数字表示中LIS==K的数字的个数

这题状压+数位DP

觉得好厉害。为什么状压。考虑nlognLIS是怎么做的。这里的数字只能是0-9

所以状压。举个例子 1 2 4 6 是g数组,LIS = 4，现在来了个5.G数组变成 1 2 4 5 LIS仍然等于4

考虑好NLOGN LIS 怎么来的。注意前导0和0！

然后数位DP

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define PI 3.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

const int MAXN = ;

LL dp[MAXN][( << ) + ][];

LL L,R,K;

int digit[MAXN];

int getsta(int x,int s)

{

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

    {

        if (s & ( << i))

        {

            return (s ^ ( << i)) | ( << x);

        }

    }

    return s | ( << x);

}

int getnum(int x)

{

    int ret = ;

    while (x)

    {

        if (x & ) ret++;

        x >>= ;

    }

    return ret;

}

LL calcu(int length,int presta,bool prezero,bool ismax)

{

    if (length == ) return getnum(presta) == K;

    if (!ismax && dp[length][presta][K] >= ) return dp[length][presta][K];

    LL tot = ;

    int limit = ismax ? digit[length] : ;

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

    {

        tot += calcu(length - ,(i ==  && prezero) ?  : getsta(i,presta),i ==  && prezero,ismax && i == limit);

    }

    if (ismax) return tot;

    else return dp[length][presta][K] = tot;

}

LL slove(LL x)

{

    int len = ;

    LL num = x;

    while (num)

    {

        digit[++len] = num % ;

        num /= ;

    }

    return calcu(len,,true,true);

}

int main()

{

    int T,kase = ;

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

    scanf("%d",&T);

    while (T--)

    {

        scanf("%I64d%I64d%I64d",&L,&R,&K);

        printf("Case #%d: %I64d\n",kase++,slove(R) - slove(L - ));

    }

    return ;

}

HDU 4734 f(x)

数位DP的一维状态表示差值即可

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL int

#define PI 3.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

const int MAXN = ;

const int MAXD = ;

LL dp[][MAXD];

int digit[MAXN];

LL val,A,B;

LL calcu(int length,int preval,bool ismax)

{

    if (length == ) return preval >= ;

    if (preval < ) return ;

    if (!ismax && dp[length][preval] >= ) return dp[length][preval];

    LL tot = ;

    int limit = ismax ? digit[length] : ;

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

    {

        tot += calcu(length - ,preval - ( << (length - )) * i,ismax && i == limit);

    }

    if (!ismax) return dp[length][preval] = tot;

    return tot;

}

int f(int x)

{

    int ret = ,cas = ;

    while (x)

    {

        ret += (x % ) * ( << cas);

        cas++;

        x /= ;

    }

    return ret;

}

LL slove()

{

    int len = ;

    LL num = B;

    while (num)

    {

        digit[++len] = num % ;

        num /= ;

    }

    return calcu(len,f(A),true);

}

int main()

{

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

    int T,kase = ;

    scanf("%d",&T);

    while (T--)

    {

        scanf("%d%d",&A,&B);

        printf("Case #%d: %d\n",kase++,slove());

    }

    return ;

}

HDU 4507

主要是要求的不是数字个数。而是平方和。

那么可能久有点问题了

怎么做考虑(a + b1) ^ 2 + (a + b2) ^ 2 + .... 等于

a^2 * n + b1^ 2 + b2 ^ 2 + ..bn ^ 2 + 2 * a * (b1 + b2 +... bn)

上式实际上就是比如枚举到第3为a就1000，递归的找到b然后推即可

于是dp有三个值。数字个数。一次方和，二次方和

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define PI 3.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

const int MAXN = ;

const int MOD = 1e9 + ;

LL fac[];

typedef pair<int,pair<LL,LL> >PII;

PII dp[MAXN][][][];

int digit[MAXN];

bool vis[MAXN][][][];

PII calcu(int length,int presum,int remain,bool contain,bool ismax)

{

    if (length == )

    {

        if (!contain && presum && remain)

            return make_pair(,make_pair(0LL,0LL));

        else return make_pair(,make_pair(0LL,0LL));

    }

    if (!ismax && vis[length][presum][remain][contain])

        return dp[length][presum][remain][contain];

    PII ret = make_pair(,make_pair(0LL,0LL));

    int limit = ismax ? digit[length] : ;

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

    {

        PII nxt = calcu(length - ,(presum + i) % ,(remain *  + i) %

                        ,contain || (i == ),ismax && i == limit);

        LL preval = (LL)i * fac[length - ] % MOD;

        ret.first = (ret.first + nxt.first) % MOD;

        ret.second.first = (ret.second.first + nxt.second.first + preval * nxt.first) % MOD;

        ret.second.second = (ret.second.second + nxt.second.second +  * preval * nxt.second.first % MOD

                                    + preval * preval % MOD * nxt.first) % MOD;

    }

    if(!ismax)

    {

        vis[length][presum][remain][contain] = true;

        dp[length][presum][remain][contain] = ret;

        return ret;

    }

    return ret;

}

LL slove(LL x)

{

    int len = ;

    LL num = x;

    while(num)

    {

        digit[++len] = num % ;

        num /= ;

    }

    return calcu(len,,,,true).second.second;

}

int main()

{

    fac[] = ;

    for (int i =  ; i <  ; i++) fac[i] = fac[i - ] *  % MOD;

    int T;

    memset(vis,false,sizeof(vis));

    scanf("%d",&T);

    while (T--)

    {

        LL l,r;

        scanf("%I64d%I64d",&l,&r);

        printf("%I64d\n",(slove(r) - slove(l - ) + MOD) % MOD);

    }

    return ;

}

BCD CODE 放到自动机专题里在做

相关文章