数位dp （2）

今天继续写几个数位dp

F - Balanced Number

题目大意：给你一个区间，让你求这个区间之中满足条件的数字有多少。

这个条件：可以选数的一个位为轴，左右到轴的长度乘上那个数字本身相等的数有多少？

我的思路：首先我们要研究这个题目的数字要求，就是找到一个点然后去枚举每一个点是轴，然后我们就再dfs里面搜索

因为我们要求点到轴的力矩，但是我们又不知道力矩的位置，所以我们用一个数来记录到此位置的力矩

这个怎么记录呢？比如说数字abcdef

第一次就是a，第二次是a*2+b 第三次是a*3+b*2+c。。。。

所以我们需要有一个来记录这个力矩，还需要有一个数来记录 a a+b a+b+c....

这个时候就很好求了。

所以这个dp我是这么定义的 dp[i][j][k][h]表示到第 i 位轴为 j 力矩为 k 数字之和为 h

但是自己敲了之后发现有问题

首先就是这个数组开的太大了，其次就是这个状态定义的唯一不唯一很难确定。

我对于这个dp数组是真的无奈，不知道该怎么去定义，有时候定义多了，有时候定义少了。

状态是不是唯一真的很难去判断。

看了题解，题解是这么定义的，

dp[i][j][k] 表示第 i 为以第 j 位是否满足条件，满足k==0，不满足k!=0

这个状态一定义下来，就很好写这个dp了。

！！注意最后要减去全为0 的数，0 00 000 0000 000000 这些数是一样的，都是0，重复计算了很多次。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <algorithm>

#include <vector>

#include <iostream>

#define inf 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = ;

const int mod = ;

typedef long long ll;

ll dp[][][];

int a[maxn];

ll dfs(int pos,int sta,int num,bool limit)

{

    if (pos == -) return num == ;

    if (num < ) return ;

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

    int up = limit ? a[pos] : ;

    ll ans = ;

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

    {

        ans += dfs(pos - , sta, num + (pos - sta)*i, limit && (i == up));

    }

    if (!limit) dp[pos][sta][num] = ans;

    return ans;

}

ll solve(ll x)

{

    if (x < ) return ;

    int pos = ;

    while(x)

    {

        a[pos++] = x % ;

        x /= ;

    }

    ll ans = ;

    for(int i=;i<pos;i++) ans += dfs(pos - , i, ,);

    return ans - pos + ;

}

int main()

{

    int t;

    cin >> t;

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

    while(t--)

    {

        ll a, b;

        scanf("%lld%lld", &a, &b);

        ll ans = solve(b) - solve(a - );

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

    }

    return ;

}

数位dp

E - Round Numbers

这个题目我第一感觉还比较简单。

题目大意：还是求在一个区间内满足条件的数

这个条件就是：这个数的二进制表示0比1的数多或者等于。

这个题目是二进制，那么我们就先把他转化成二进制，然后怎么写呢？

因为我们要求的是0比1 的数量多，既然有一个比较，那我就想到了上面的这个题目，它是要求左边的力矩等于右边的力矩，

这个也有一个等式或者不等式的关系，所以我们试着像上面那样处理，就是dp[i][j][k]表示第i位，出现0的个数，是不是满足条件

这个应该是状态唯一的吧，或者说是可以表示一类数。不管怎么样，先试试。

这个是可以的，但是当你敲代码的时候就会发现并不需要三维，我们只需要两维就可以了，

dp[i][j]表示第i位，满足条件的数，

敲完代码，过了样例wa了，搜了一下题解发现我忘记处理前导零了，这个肯定是要处理前导零的啊。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <algorithm>

#include <vector>

#include <string>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

const int first = ;

typedef long long ll;

ll dp[][];

int a[];

ll dfs(int pos,int num,bool limit,bool lead)

{

    if (pos == -) return num >= first;

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

    int up = limit ? a[pos] : ;

    ll ans = ;

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

    {

        ans += dfs(pos - , lead&&(i==)?num:(i==?num+:num-), limit && (i == up),lead&&(i==));

    }

    if (!lead && !limit) dp[pos][num] = ans;

    return ans;

}

ll solve(ll x)

{

    int pos = ;

    while(x)

    {

        a[pos++] = x & ;

        x >>= ;

    }

    return dfs(pos - , first, ,);

}

int main()

{

    int l, r;

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

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

    {

        ll ans = solve(r)-solve(l-);

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

    }

    return ;

}

数位dp

G - B-number

这个题目也很简单，题目大意给你一个数，找到从1到这个数这个区间满足条件的数，这个条件就是可以被13整除，并且存在13这样的子串。

这个题目怎么写呢？我们的要求就是被13整除，所以需要这个数来表示这个，存在13的子串，所以要有一个来记录前缀，然后要判断是不是13

所以这就有三个数了，所以就可以设dp[i][j][k] 表示第i个数和为j，是不是满足有13的子串的要求。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <algorithm>

#include <vector>

#include <string>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

const int first = ;

typedef long long ll;

ll dp[][][];

int a[];

ll dfs(int pos, int pre, int sum, int flag, int limit) {

    if (pos == -) return (flag==) && (sum == );

    if (!limit && dp[pos][sum][flag] != -) return dp[pos][sum][flag];

    int up = limit ? a[pos] : ;

    ll ans = ;

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

        int f = ;

        if (flag == ) f = flag;

        else if (flag ==  && i == ) f = ;

        else if (i == ) f = ;

        ans += dfs(pos - , i, (sum *  + i) % , f, limit && (i == up));

    }

    if (!limit) dp[pos][sum][flag] = ans;

    return ans;

}

ll solve(ll x) {

    int pos = ;

    while (x) {

        a[pos++] = x % ;

        x /= ;

    }

    return dfs(pos - , , , , );

}

int main() {

    int n;

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

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

        ll ans = solve(n);

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

    }

    return ;

}

数位dp

J - 吉哥系列故事――恨7不成妻

我开始以为这个题目特别简单，后来才发现自己在做梦。

这个题目我觉得还挺好，加深了我对于dp数组的理解，

之前我对于dp数组以为这个记录一类数，但是这个题目写完之后，我觉得这个数位dp的dp数组是记录一种状态，

这个状态往往和dfs里面的参数有关，也就是和题目本身有关，这个参数是来表示一类数的性质，这个性质就是题目的条件。

比如说这个题目，dp[i][j][k]这个 i 表示的就是第 i 位，前面的所有数字的和对7取模是 j ，到此为止它的数大小对7取模是k(把第 i 位当作个位来看）

然后dp本身就是表示的第i位以及之后我们要求的cnt ，sum ，two

所以对于58_ 51_ 如果说以及枚举到了第三位 pos==3 的时候继续枚举5 然后枚举5后面的位数，因为limit==0 所以后面从0~9来枚举

这个时候 58 51 都是dp[3][6][2] 但是这个并不影响结果，因为这个时候我们是枚举58 51 之和的值，后面都是从0~9 而且51 58这两个数对于这个题目来说

其实是一样的状态就是，这个状态和题目要求的一一对应。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <algorithm>

#include <vector>

#include <string>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

const int first = ;

typedef long long ll;

const ll mod = 1e9 + ;

struct node

{

    int cnt;

    ll sum;

    ll two;

    node(int cnt=,ll sum=,ll two=):cnt(cnt),sum(sum),two(two){}

}dp[][][];

ll f[];

int a[];

node dfs(int pos, int sum, int num, bool limit) {

    if (pos == -) return node(sum !=  && num != , , );

    if (!limit&&dp[pos][sum][num].two != ) return dp[pos][sum][num];

    int up = limit ? a[pos] : ;

    node ans(,,);

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

    {

        if (i == ) continue;

        node ex = dfs(pos - , (sum *  + i) % , (num + i) % , limit && (i == up));

        ans.cnt += ex.cnt;

        ans.cnt %= mod;

        ans.sum = ans.sum + ((i * f[pos])%mod * ex.cnt)%mod + ex.sum;

        ans.sum %= mod;

        ans.two = ans.two + ((((i * f[pos]%mod) * (i*f[pos]%mod))%mod * ex.cnt%mod))%mod +  * ((i*f[pos])%mod * ex.sum)%mod + ex.two;

        ans.two %= mod;

    }

    if (!limit) dp[pos][sum][num] = ans;

    return ans;

}

ll solve(ll x) {

    int pos = ;

    while (x) {

        a[pos++] = x % ;

        x /= ;

    }

    ll ans = dfs(pos - , , , ).two;

    ans %= mod;

    return ans;

}

int main() {

    int t;

    scanf("%d", &t);

    f[] = ;

    for (int i = ; i <= ; i++) f[i] = f[i - ] * ;

    while (t--) {

        ll l, r;

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

        ll ans = (solve(r) - solve(l - ) + mod) % mod;

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

    }

    return ;

}

数位dp

巴特西

数位dp （2）

F - Balanced Number

E - Round Numbers

G - B-number

J - 吉哥系列故事――恨7不成妻

最新文章

热门文章