数位dp专题整理

acm

数位dp专题整理

关键在于找到不同位的关系。
注意0。

典型例题：C不要６２

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

int dp[10][3];

void init(){
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for(int i = 1; i < 7; i++){
        dp[i][0] = dp[i-1][0]*9 - dp[i-1][1];//除去4和首位为2
        dp[i][1] = dp[i-1][0];
        dp[i][2] = dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];
    }
}

int slove(int n){
    int a[20],ans ;
    int tem = n;
    int len = 0;
    while(n){
        a[++len]=n%10;
        n/=10;
    }
    a[len+1] = ans = 0;
    bool flag = 0;
    //ans计算非Beautiful Num
    for(int i = len; i >= 1; i--){
        ans += dp[i-1][2]*a[i];
        if(flag) ans += dp[i-1][0]*a[i];
        if(!flag && a[i]>4) ans+=dp[i-1][0];
        if(!flag && a[i+1]==6 && a[i]>2)ans+=dp[i][1];
        if(!flag && a[i]>6)ans+=dp[i-1][1];
        if(a[i]==4 || a[i+1]==6&&a[i]==2)
        flag = 1;
    }
    return tem - ans;
}

int main(){
    init();
    int st,ed;
    while(1){
        scanf("%d%d",&st,&ed);
        if(st==0)break;
        printf("%d\n",slove(ed+1)-slove(st));
    }
    return 0;
}

相似题型：D:bomb:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll __int64

using namespace std;

ll dp[30][3]={0};

void init(){
    dp[0][0]=1;
    for(int i = 1; i < 22; i++){
        dp[i][0] = dp[i-1][0]*10 - dp[i-1][1];
        dp[i][1] = dp[i-1][0];
        dp[i][2] = dp[i-1][2]*10 + dp[i-1][1];
    }
}

ll slove(ll ed){
    int digit[30]={0};
    ll temp = ed;
    int len = 0;
    while(temp){
        digit[++len] = temp%10;
        temp/=10;
    }
    ll ans = 0;
    bool flag = 0;
    for(int i = len ; i > 0; i--){
        ans += dp[i-1][2]*digit[i];
        if(flag)ans+=dp[i-1][0]*digit[i];
        if(!flag && digit[i]>4)ans += dp[i-1][1];
        if(digit[i+1]==4 && digit[i] == 9)
            flag = 1;
    }
    return ans;
}

int main(){
    init();
    int n;scanf("%d",&n);
    ll ed;
    while(n--){
        scanf("%I64d",&ed);
        printf("%I64d\n",slove(ed+1));
    }
}

A.Beautiful numbers

除此之外还可以用dfs，而且dfs更为常见。

利用１－９的公倍数，化小了10^i，然后才开下了数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
#define CL(a,v) memset(a,v,sizeof a)
using namespace std;

const int Mod = 2520;
ll dp[21][Mod][50];
int digit[21];
int indx[Mod+5];

void init(){
    int num = 0;
    for(int i = 1; i <= Mod; i++){
        if(Mod%i == 0)indx[i] = num++;
    }
    CL(dp,-1);
}

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

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

ll dfs(int pos, int presum, int prelcm, bool edge){
    if(pos==-1) return presum%prelcm == 0;
    if(!edge && dp[pos][presum][indx[prelcm]] != -1){
        return dp[pos][presum][indx[prelcm]];
    }
    int ed = edge ? digit[pos] : 9;
    ll ans = 0;
    for(int i = 0; i <= ed; i++){
        int nowlcm = prelcm;
        int nowsum = (presum*10 + i)%Mod;
        if(i) nowlcm = lcm(prelcm, i);
        ans += dfs(pos-1, nowsum, nowlcm, edge && i == ed);
    }
    if(!edge) dp[pos][presum][indx[prelcm]] = ans;
    return ans;
}

ll cal(ll x){
    CL(digit, 0);
    int pos = 0;
    while(x){
        digit[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1, 0, 1 ,1);
}

int main(){
    init();
    ll a,b;
    int t;scanf("%d",&t);
    while(t--){
        scanf("%I64d%I64d",&a,&b);
        printf("%I64d\n",cal(b) - cal(a-1));
    }
    return 0;
}

模板性很强，只需要掌握关键的地方，如edge的意义，以及return 后面那句话，以及最重要的ans+=那句话，还有有时候会根据０而设置zero，特别是带状态压缩的时候。

相似题型：GG - B-number

只需要判断是否有１３且能被１３整除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;

ll dp[30][13][3];
int digit[20];

ll dfs(int pos, int pre, int md, int flag, bool e){
    if(pos==-1) return flag&&md==0;
    if(!e && flag &&  dp[pos][md][2]!=-1)return dp[pos][md][2];
    if(!e && !flag && dp[pos][md][1]!=-1 && pre==1)return dp[pos][md][1];
    if(!e && !flag && dp[pos][md][0]!=-1 && pre!=1)return dp[pos][md][0];
    ll ans = 0;
    int ed = e?digit[pos]:9;
    for(int i = 0; i <= ed; i++){
        ans += dfs(pos-1, i, (md*10+i)%13, flag||(pre==1&&i==3), e&&(i==ed));
    }
    if(!e)dp[pos][md][flag?2:pre==1?1:0] = ans;
    return ans;
}

ll calc(ll n){
    int len=0;
    memset(dp, -1, sizeof dp);
    while(n){
        digit[len++]=n%10;
        n/=10;
    }
    return dfs(len-1, 0, 0, 0, 1);
}

int main(){
    ll n;while(~scanf("%lld",&n)){
        printf("%lld\n",calc(n));
    }
    return 0;
}

F:F - Balanced Number

此题就像一个杠杆，要求左右力臂平衡，而支点只需要从左到右遍历一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;

ll a,b;
ll dp[20][20][2000];
int digit[20];

ll dfs(int pos, int o, int val, int e){
    if(pos==-1)return val==0;
    if(val < 0)return 0;
    if(!e && dp[pos][o][val]!=-1)return dp[pos][o][val];
    int ed = e?digit[pos]:9;
    ll ans = 0;
    for(int i = 0; i <= ed; i++){
        ans += dfs(pos-1, o, val+(pos-o)*i, e&&i==ed);
    }
    if(!e)dp[pos][o][val] = ans;
    return ans;
}


ll calc(ll n){
    int len = 0;
    while(n){
        digit[len++] = n%10;
        n/=10;
    }
    ll ans = 0;
    for(int i = 0; i < len; i++){
        ans += dfs(len-1, i, 0, 1);
    }
    return ans-len;//需要减去0,00,000,0000.这种重复情况
}


int main(){
    memset(dp,-1,sizeof dp);
    int t;scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&a,&b);
        printf("%lld\n",calc(b)-calc(a-1));
    }
    return 0;
}

H - F(x)

这里是要求在０－B内找打所有满足f(x)<f(a)的个数，但是我们可以返现f(x)<18*2^8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
int digit[20];
ll dp[20][5000];//前缀和不大于presum满足条件的个数
ll a,b;

ll dfs(int pos, int remain, bool e){
    if(pos==-1)return remain>=0;
    if(remain<0)return 0;
    if(!e && dp[pos][remain]!=-1) return dp[pos][remain];
    int ed = e?digit[pos]:9;
    ll ans=0;
    for(int i = 0; i <= ed; i++){
        ans += dfs(pos-1, remain - i*(1<<pos), e&&(i==ed));
    }
    if(!e)dp[pos][remain] = ans;
    return ans;
}

int f(ll n){
    int ans =0,t=-1;
    while(n){
        ans+=(n%10)*(1<<++t);
        n/=10;
    }
    return ans;
}

ll calc(ll n){
    int len = 0;
    while(n){
        digit[len++] = n%10;
        n/=10;
    }
    return dfs(len-1, f(a),1);
}

int main(){
    int T,t=0;scanf("%d",&T);
    memset(dp, -1, sizeof dp);
    while(t++<T){
        scanf("%lld%lld",&a,&b);
        printf("Case #%d: %lld\n",t,calc(b));
    }
}

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

求区间平方和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
也就是说在DP时候，要重建每个数，算出平方，然后求和。
使用结构体
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
ll mod = 1000000007;
struct status{
    ll cnt, sum, sqsum;
    status(){cnt = -1;sum=sqsum=0;}
    status(ll a, ll b, ll c){
        cnt = a;
        sum = b;
        sqsum = c;
    }
}dp[20][10][10];

ll a,b;
ll digit[20],p[25];

status dfs(int pos, int sum, int md, bool e){
    if(pos==-1)return (sum!=0&&md!=0)?status(1,0,0):status(0,0,0);
    if(!e && dp[pos][sum][md].cnt!=-1) return dp[pos][sum][md];
    status ans = status(0,0,0);
    int ed = e?digit[pos]:9;
    for(int i = 0; i <= ed; i++){
        if(i==7)continue;
        status next = dfs(pos-1, (sum+i)%7, (md*10+i)%7, e&&i==ed);
        ans.cnt += next.cnt;
        ans.cnt %= mod;
        ans.sum += (next.sum+((p[pos]*i)%mod)*next.cnt%mod )%mod;
        ans.sum %= mod;
        ans.sqsum += (next.sqsum + ((2*p[pos]*i)%mod)*next.sum)%mod;
        ans.sqsum %= mod;
        ans.sqsum += (next.cnt*p[pos])%mod*p[pos]%mod*i*i%mod;
        ans.sqsum %= mod;
    }
    if(!e)dp[pos][sum][md] = ans;
    return ans;
}

ll calc(ll n){
    int len = 0;
    while(n){
        digit[len++] = n%10;
        n/=10;
    }
    return dfs(len-1, 0, 0, 1).sqsum;
}

int main(){
    int t;scanf("%d",&t);
    p[0] = 1;
    for(int i = 1; i <= 20; i++)p[i] = (p[i-1]*10)%mod;
    while(t--){
        scanf("%lld%lld",&a,&b);
        printf("%lld\n",((calc(b)-calc(a-1))%mod+mod)%mod);
    }
}

状态压缩的两道题：

B: B - XHXJ’s LIS

关键是构造下一个state的地方利用了nlogn的LIS算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;

ll st,ed;
ll K;
int bit[25];
ll dp[25][1<<11][11];

int getnews(int x, int s){
    for(int i = x; i < 10; i++){
        if(s&(1<<i))return s^(1<<i)|(1<<x);
    }
    return s|(1<<x);
}

int getnum(int s){
    int ret = 0;
    while(s){
        if(s&1)ret++;
        s>>=1;
    }
    return ret;
}

ll dfs(int pos, int s, bool e,bool z){
    if(pos==-1)return getnum(s) == K;
    if(!e && dp[pos][s][K] != -1)return dp[pos][s][K];
    long long ans = 0;
    int ted = e?bit[pos]:9;
    for(int i = 0; i <= ted; i++){
        ans += dfs(pos-1, (z&&i==0)?0:getnews(i,s), e&&i==ted, z&&(i==0));
    }
    if(!e)dp[pos][s][K] = ans;
    return ans;
}

ll calc(ll n){
    int len = 0;
    while(n){
        bit[len++]=n%10;
        n/=10;
    }
    return dfs(len-1,0,1,1);
}


int main(){
    int t=0,T;scanf("%d",&T);
    memset(dp,-1,sizeof dp);
    while(t++<T){
        scanf("%lld%lld%lld",&st,&ed,&K);
        printf("Case #%d: %lld\n",t,calc(ed)-calc(st-1));
    }
    return 0;
}

另外的一道题是三进制的，可以手动模拟一下：

K - Balanced Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
ll digit[20];
ll dp[20][60000];
ll a,b;

int getnew(int x, int s){
    int temp = s;
    for(int i = 0; i < x; i++){
        temp/=3;
    }
    if(temp%3<2)return s+(int)pow(3,x);
    else return s - (int)pow(3,x);
}

bool judge(int s){
    //printf("%d\n",s);
    int cont = 0;
    while(s){
        //printf("%d%d\n",s%3,cont);
        if(s%3==1+(++cont)%2)return false;
        s/=3;
    }
    //printf("asdas");
    return true;
}

ll dfs(int pos, int s, bool e, bool z){
    if(pos == -1)return judge(s);
    if(!e && dp[pos][s]!=-1)return dp[pos][s];
    ll ans = 0;
    int ed = e?digit[pos]:9;
    for(int i = 0; i <= ed; i++){
        ans += dfs(pos-1,(z&&i==0)?0:getnew(i,s), e&&i==ed, z&&i==0);
    }
    if(!e) dp[pos][s]=ans;
    return ans;
}

ll calc(ll n){
    int len = 0;
    while(n){
        digit[len++] = n%10;
        n/=10;
    }
    return dfs(len-1, 0, 1, 1);
}

int main(){
    int t;scanf("%d",&t);
    memset(dp,-1,sizeof dp);
    while(t--){
        scanf("%lld%lld",&a,&b);
        printf("%lld\n",calc(b)-calc(a-1));
    }
    return 0;
}

E???是组合数学把。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;

ll bin[35];
ll c[33][33]={0};
void init(){
    for(int i = 0; i <= 32; i++){
        for(int j = 0; j <= i; j++){
            if(!j || i==j )c[i][j] = 1;
            else c[i][j] = c[i-1][j-1] + c[i-1][j];
        }
    }
}

void T_to_bin(ll n){
    bin[0] = 0;
    while(n){
        bin[++bin[0]] = n%2;
        n>>=1;
    }
}

ll calc(ll v){
    ll sum = 0;
    T_to_bin(v);

    for(int i = 1; i < bin[0]-1; i++){
        for(int j = i/2+1; j <= i; j++){
            sum+=c[i][j];
        }
    }

    int zero = 0;//从高位向低位搜索过程中的0
    for(int i = bin[0]-1; i>=1; i--){
        if(bin[i])for(int j = (bin[0]+1)/2-(zero+1); j <= i; j++)
            sum += c[i-1][j];
        else zero++;
    }
    return sum;

}

int main(){
    init();
    ll st,ed;
    scanf("%lld%lld",&st,&ed);
    printf("%lld\n",calc(ed+1)-calc(st));
    return 0;
}

还有一提是Ｉ：自动机＋数位dp,做自动机的时候再补上。

本文标题:数位dp专题整理

文章作者:呼哧

发布时间:2017-07-12, 12:40:42

最后更新:2018-08-04, 02:48:34

原始链接:http://hu-chi.github.io/2017/07/12/acm/数位dp/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 数位dp专题整理
    1. 1.1. 典型例题：C不要６２
      1. 1.1.1. 相似题型：D:bomb:
    2. 1.2. A.Beautiful numbers
      1. 1.2.1. 相似题型：GG - B-number
    3. 1.3. F:F - Balanced Number
    4. 1.4. H - F(x)
    5. 1.5. J - 吉哥系列故事――恨7不成妻
    6. 1.6. 状态压缩的两道题：
      1. 1.6.1. B: B - XHXJ’s LIS
      2. 1.6.2. K - Balanced Numbers
    7. 1.7. E???是组合数学把。。。
|