数位dp题解

· · 个人记录

【P2657 [SCOI2009]windy数】

答案=比B小的-比A小的+特判A

采用记忆化搜索，按位转移合法情况

特殊记录前导0情况（如果还在填前导0那么后一位没有转移限制）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring> 
using namespace std;

string l,r,m;
int len,memo[15][10][2][2];

int dfs(int cur,int x,bool f,bool g){
    if(memo[cur][x][f][g]!=-1) return memo[cur][x][f][g]; 
    if(cur==len) return memo[cur][x][f][g]=1;

    int h=9,res=0;
    if(f==1) h=(m[cur]-'0');
    for(int i=0;i<=h;i++){
        if(g==1){
            if(i==0) res+=dfs(cur+1,0,f&(i==h),1);
            else res+=dfs(cur+1,i,f&(i==h),0);
        }
        else if(abs(i-x)>=2) res+=dfs(cur+1,i,f&(i==h),0);
    }

    return memo[cur][x][f][g]=res;
}

int work(string s){
    m=s;
    len=m.length();
    memset(memo,-1,sizeof(memo));
    return dfs(0,0,1,1);
}

bool check(string& s){
    for(int i=1;i<s.length();i++){
        if(abs(s[i]-s[i-1])<2) return 0;
    }
    return 1;
}

int main(){
    cin>>l>>r;
    int ans=work(r)-work(l)+check(l);
    cout<<ans<<endl;
    return 0;
}

【AcWing 310. 启示录】

可以求出有多少个小于等于x的满足

所以转化为二分查找第一个不符合有k个小于等于x的数满足的x，x即为答案

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring> 
using namespace std;

int k;
int len,memo[15][2][2][2][2],s[15];

int dfs(int cur,bool p2,bool p1,bool m,bool g){
    if(cur==len) return m==1;
    if(memo[cur][p2][p1][m][g]!=-1) return memo[cur][p2][p1][m][g]; 

    int h=9;
    long long res=0;
    if(g) h=s[cur];
    for(int i=0;i<=h;i++){
        res+=dfs(cur+1,p1,(i==6),m||(p1&&p2&&(i==6)),g&&(i==h));
    }
    return memo[cur][p2][p1][m][g]=res;
}

bool work(long long x){
    len=0;
    while(x){
        s[len++]=x%10;
        x/=10;
    }
    reverse(s,s+len);
    memset(memo,-1,sizeof(memo));
    return (dfs(0,0,0,0,1)<=k);
}   

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>k;
        --k;
        long long l=0,r=1e10,mid;
        while(l<r){
            mid=(l+r)/2;
            if(work(mid)) l=mid+1;
            else r=mid;
        }
        cout<<r<<endl;
    }
    return 0;
}

【AcWing 311. 月之谜】

各位数字之和的范围很小，所以分类把每个数字和单独做

余数可以一边填一边维护，所以用余数来判断是否整除即可

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring> 
using namespace std;

string l,r,s;
int sum,len,memo[15][105][105][2];

int power(int num){
    int res=1;
    for(int i=1;i<=num;i++) res*=10;
    return res;
}

int dfs(int cur,int sum1,int r,bool f){
    if(cur==len) return (sum1==sum&&r==0);
    if(memo[cur][sum1][r][f]!=-1) return memo[cur][sum1][r][f]; 

    int h=9;
    long long res=0;
    if(f) h=s[cur]-'0';
    for(int i=0;i<=h;i++){
        res+=dfs(cur+1,sum1+i,(r+power(len-cur-1)*i)%sum,f&&(i==h));
    }
    return memo[cur][sum1][r][f]=res;
}

int work(string t){
    s=t;
    len=t.length();
    memset(memo,-1,sizeof(memo));
    return dfs(0,0,0,1);
}   

bool check(string t){
    int num=0,x=0,k=1;
    for(int i=t.length()-1;i>=0;i--){
        x+=(t[i]-'0')*k;
        num+=(t[i]-'0');
        k*=10;
    }
    if(x%num==0&&num==sum) return 1;
    else return 0;
}

int main(){
    cin>>l>>r;
    int ans=0;
    for(sum=1;sum<=100;sum++){
        ans+=work(r)-work(l)+check(l);
    }
    cout<<ans<<endl;
    return 0;
}

【AcWing 338. 计数问题】

与第一道类似，特殊记录前导0

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring> 
using namespace std;

string l,r,s;
int k,len,memo[25][25][2][2];

long long dfs(int cur,int sum,bool f,bool g){
    if(cur==len) return sum;
    if(memo[cur][sum][f][g]!=-1) return memo[cur][sum][f][g]; 

    int h=9;
    long long res=0;
    if(f) h=s[cur]-'0';
    for(int i=0;i<=h;i++){
        if(g==1&&i==0) res+=dfs(cur+1,0,f&&(i==h),1);
        else res+=dfs(cur+1,sum+(i==k),f&&(i==h),0);
    }
    return memo[cur][sum][f][g]=res;
}

long long work(string t){
    s=t;
    len=t.length();
    memset(memo,-1,sizeof(memo));
    return dfs(0,0,1,1);
}   

int check(string t){
    int num=0;
    for(int i=t.length()-1;i>=0;i--){
        if((t[i]-'0')==k) num++;
    }
    return num;
}

int main(){
    while(1){
        cin>>l>>r;
        if(l=="0"&&r=="0") break;
        if(l.length()>r.length()||(l.length()==r.length()&&l>r)) swap(l,r);
        for(k=0;k<=9;k++){
            cout<<work(r)-work(l)+check(l)<<" ";
        }
        cout<<endl;
    }
    return 0;
}