数位dp浅析-练习题浅解

如果在看以下题解时未了解过数位dp相关,建议先看这一篇数位dp浅析:
数位dp浅析

如果你希望亲自完成这些题目请务必不要提前阅读题解,否则只会给你“这些题很简单”的错觉。
当然,对于大佬来说就是很简单就是了

HDU-2089:不要62

题意: 求一个范围内不含4和62的数有多少个。

解: 直接在数位dp模板的基础上加上不要4和不要62的条件判断。另外由于不要62这个条件要判断前一位,所以dfs还要传递前一位的值。

此外由于题目的数据量并不大,你甚至不需要记忆化操作。

代码:
#include<bits/stdc++.h>
using namespace std;
int dp2[10]
void solve(string &a,int i,int f0,int f1)
{
    if(i==a.length())return;
    int top=f1?a[i]-'0':9;
    for(int B=0; B<=top; B++)
    {
        if(B==2&&f0==6);
        else if(B==4);
        else
        {
            dp2[i]++;
            solve(a,i+1,B,f1&&B==top);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)break;

        string s=to_string(n-1);
        memset(dp2,0,sizeof(dp2));
        solve(s,0,0,1);
        int ans1=dp2[s.length()-1];

        s=to_string(m);
        memset(dp2,0,sizeof(dp2));
        solve(s,0,0,1);
        int ans2=dp2[s.length()-1];

        cout<<ans2-ans1<<endl;
    }

    return 0;
}

POJ-2282:The Counting Problem

题意: 求范围内的所有数的各个数位的数的个数。

解: 由于不是对数进行计数,而是对数的各个数位进行计数,所以dp要基于数位计数,而不是基于数计数。此外,对数位的计数要考虑前导0的影响,因为前导0不能被计数。

代码:
#include<iostream>
#include<string.h>
#include<string>
using namespace std;
typedef long long ll;
ll dp[10][10][10]; // pos,val means the number we aim to count, amt means the number of val we have counted.
ll ans1[10];
ll ans2[10];
string num;
int len;

// pos,val means the number we aim to count, amt means the number of val we have counted, lead means pre zero, limit means limit max
ll dfs(int pos,int val,int amt,bool lead,bool limit)
{
    if(pos==len)return amt;
    if(!lead&&!limit&&dp[pos][val][amt]!=-1)return dp[pos][val][amt];
    int top=limit?num[pos]-'0':9;
    ll t=0,ans=0;
    for(int i=0;i<=top;i++)
    {
        if(val!=i)t=amt;
        else
        {
            if(val==0)
            {
                if(lead)t=0;
                else t=amt+1;
            }
            else
            {
                t=amt+1;
            }
        }
        ans+=dfs(pos+1,val,t,lead&&i==0,limit&&i==top);
    }
    if(!limit&&!lead)dp[pos][val][amt]=ans;
    return ans;
}

void solve(ll n,ll ans[])
{
    //num=to_string(n);
    //因为poj不支持to_string,所以用下面的转化方法
    int nn=n;
    num="";
    while(nn!=0)
    {
        string ss(1,(char)(nn%10)+'0');
        num=ss+num;
        nn/=10;
    }
    len=num.length();
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<10;i++)
    {
        ans[i]=dfs(0,i,0,1,1);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a,b;
    while(cin>>a>>b)
    {
        if(a==0&&b==0)break;
        if(a<b)swap(a,b);
        solve(a,ans1);
        solve(b-1,ans2);
        for(int i=0;i<9;i++)cout<<ans1[i]-ans2[i]<<' ';
        cout<<ans1[9]-ans2[9]<<endl;
    }
    return 0;
}

CodeForces-914C:Travelling Salesman and Special Numbers

题意: 将一个数变为他的二进制中1的个数的和为一次操作。求1-n中有多少个数刚好经过k次操作变为1。

解: 只要初始化1的个数和k的对应关系,数位dp就计数上1的个数就能判断了。注意特判点。

代码:
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;

int tok[1005]={0};
ll dp[1005][1005];

string str;
int k;
int len;

void init()
{
    for(int i=1;i<=1000;i++)
    {
        tok[i]=tok[__builtin_popcount(i)]+1;
    }
}

ll dfs(int pos,int num,bool limit)
{
    if(pos==len)
    {
        return tok[num]==k;
    }
    if(!limit&&dp[pos][num]!=-1)
    {
        return dp[pos][num];
    }
    ll ans=0;
    int up=limit?(str[pos]-'0'):1;
    for(int i=0;i<=up;i++)
    {
        ans=(ans+dfs(pos+1,num+(i==1),limit&&(i==(str[pos]-'0'))))%MOD;
    }
    if(!limit)
    {
        dp[pos][num]=ans;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();

    cin>>str;
    cin>>k;
    if(k==0)
    {
        cout<<1;
        return 0;
    }
    len=str.length();
    memset(dp,-1,sizeof(dp));
    ll ans=dfs(0,0,1)%MOD;
    if(k==1)ans=(ans-1+MOD)%MOD;
    cout<<ans;

    return 0;
}

UVA-11361:Investigating Div-Sum Property

题意: 求范围内有多少个数,数和该数的数位和都能被k整除。

解: 根据题意得出需要注意的条件——数的和、数位的和。此外注意到数位和的最大的值会是多少,从而把k的上限缩小。再用取模操作来缩小dp所需的空间,然后dp就有空间存数的和和数位的和了。

代码:
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;

ll dp[20][100][100]; //pos,presum,predigitsum
int len;
ll a,b,k;

ll dfs(string &str,int pos,int ps,int pds,bool limit)
{
    if(pos==len)
    {
        if(ps==0&&pds%k==0) return 1;
        if(ps%k==0&&pds%k==0)return 1;
        else return 0;
    }
    if(!limit&&dp[pos][ps][pds]!=-1)return dp[pos][ps][pds];
    int top=limit?str[pos]-'0':9;
    ll ans=0;
    for(int i=0;i<=top;i++)
    {
        ans+=dfs(str,pos+1,(ps*10+i)%k,pds+i,limit&&i==top);

    }
    if(!limit)dp[pos][ps][pds]=ans;
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {

        cin>>a>>b>>k;
        if(k>95)
        {
            cout<<0<<endl;
            continue;
        }
        string sa,sb;
        sa=to_string(a-1);
        sb=to_string(b);

        memset(dp,-1,sizeof(dp));
        len=sa.length();
        ll ans1=dfs(sa,0,0,0,1);

        memset(dp,-1,sizeof(dp));
        len=sb.length();
        ll ans2=dfs(sb,0,0,0,1);

        cout<<ans2-ans1<<endl;
    }
    return 0;
}

CodeForces-55D:Beautiful numbers

题意: 求范围内有多少数能被该数的各个非零数位整除。

解:
根据题意知道要加两个条件——数的和、数位的最小公倍数。求得1到9这9个数的最小公倍数是2520,再加上这题也能用上一题的取模优化,有关数的和和数位的最小公倍数这两个维度的量级可以下降到[2520][2520]。但这空间还是太大了,所以还是要缩减特征量。

之后发现公倍数的真正个数远小于2520,那可以离散化,从而使存储公倍数的维度值下降到100以内。

最后就是数位dp的一般操作了。

代码:
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;

int len;
ll dp[20][2600][200]; //pos,presum,prelcm  the prelcm use map to min the memory
map<int,int> lcmtoi;
int itolcm[200];
int cnt=0;

//lcm of 1,2,3,4,5,6,7,8,9 is 2520.
ll mylcm(ll a,ll b)
{
    if(a==0||b==0)
    {
        return max(a,b);
    }

    ll s=a*b;
    ll t;
    while(b!=0)
    {
        t=a%b;
        a=b;
        b=t;
    }
    return s/a;
}

ll dfs(string &str,int pos,int presum,int prelcm,bool limit)
{
    if(pos==len)
    {
        if(presum==0)return 1;
        
        if(itolcm[prelcm]==presum)return 1;
        if(mylcm(presum,itolcm[prelcm])==presum)return 1;
        else return 0;
    }
    if(!limit&&dp[len-pos][presum][prelcm]!=-1)
    {
        return dp[len-pos][presum][prelcm];
    }
    int top=limit?(str[pos]-'0'):9;
    ll ans=0;
    for(int i=0;i<=top;i++)
    {
        ll tl=mylcm(itolcm[prelcm],i);
        if(lcmtoi.find(tl)==lcmtoi.end())
        {
            lcmtoi[tl]=cnt;
            itolcm[cnt]=tl;
            cnt++;
        }
        ans+=dfs(str,pos+1,(presum*10+i)%2520,lcmtoi[tl],limit&&i==top);
    }
    if(!limit)
    {
        dp[len-pos][presum][prelcm]=ans;
    }
    return ans;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    lcmtoi[0]=cnt;
    itolcm[cnt]=0;
    cnt++;
    memset(dp,-1,sizeof(dp));//如果在每个dfs前都memset,就会超时。而如果将dp中第一维的意思从pos(从高位到低位数的第几位)变为len-pos(反过来数的第几位),
    //就可把memset放出来,dp也不会每次重新学习记录,也就不会超时。
    while(t--)
    {
        ll a,b;
        cin>>a>>b;
        if(a<b)swap(a,b);
        b--;
        string sa,sb;
        sa=to_string(a);
        sb=to_string(b);


        len=sa.length();
        ll ans1=dfs(sa,0,0,0,1);


        len=sb.length();
        ll ans2=dfs(sb,0,0,0,1);

        //cout<<ans1<<'a'<<endl;
        //cout<<ans2<<'b'<<endl;
        cout<<ans1-ans2<<endl;
    }

    return 0;
}
粤 ICP 备 2020080455 号