集训队大一下学期第一周作业（数位dp专题）

数位dp

为什么是数位dp专题呢233，因为只做了一道和这个相关的于是就叫数位dp
了，同时自己又去补了几道数位dp水题。
B - How Many Zeroes?

统计一个区间自然数据中有多少个0，数据范围为无符号32位正整数，裸的数位dp，这里需要注意的是我们需要在模板在多出一个状态去判断前导零对结果造成的影响，自然002这种数据我们是不能算作0的计数的
ps:cnt表示数据前面有cnt个0，pre为前导0状态表示

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll dp[99][99];
ll a[99];
ll n,m,t;
ll dfs(ll pos,ll cnt,int pre,bool limit)
{
    if(pos==0) return cnt;
    if(!limit&&dp[pos][cnt]!=-1&&pre)
            return dp[pos][cnt];
    int mxr=limit?a[pos]:9;
    ll ret=0;
    for(ll i=0;i<=mxr;i++)
    {
        ret+=dfs(pos-1,cnt+(pre&&i==0),pre||i,limit&&(i==mxr));
    }
    if(!limit&&pre) dp[pos][cnt]=ret;
    return ret;
}
ll solve(ll x)
{
    memset(dp,-1,sizeof(dp));
    ll pos=0;
    while(x)
    {
        a[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,0,1);
}
int main()
{
    int temp=1;
    cin>>t;
    while(t--)
    {
        cin>>m>>n;
        printf("Case %d: ",temp++);
        if(m==0)
            cout<<solve(n)-solve(m-1)+1<<endl;
        else
            cout<<solve(n)-solve(m-1)<<endl;
    }
    return 0;
}

C - Jason的特殊爱好 FZU - 2113

a,b(1<=a,b<=10^18)。
求数据区间含有多少个1，一个套路，只是这里不需要再对前导0进行限制啦,于是可以去掉判断前导0的状态pre

#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long ll;
using namespace std;
ll c,b;
ll a[25];
ll dp[25][25];
ll dfs(ll pos,ll cnt,bool limit)
{
    if(pos==0) return cnt;
    if(!limit&&dp[pos][cnt]!=-1)
        return dp[pos][cnt];
    int up=limit? a[pos]:9;
    ll ret=0;
    for(int i=0;i<=up;i++)
        ret+=dfs(pos-1,cnt+(i==1),limit&&(i==up));
    if(!limit)
        return dp[pos][cnt]=ret;
    return ret;
}
ll solve(ll x)
{
    memset(dp,-1,sizeof(dp));
    ll pos=0;
    while(x)
    {
        a[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,1);
}
int main()
{
    while(cin>>c>>b)
    {
        cout<<solve(b)-solve(c-1)<<endl;
    }
    return 0;
}

E - Bomb HDU - 3555

还是一样的套路，一样的感觉，给你一个数据n，求1到n这个区间内含多少个49.这里我们需要判断前缀数字于是需要一个pre状态，用sta判断是否为数字4开头，如果是就状态传递下去

#include <stdio.h>
#include <string.h>
typedef long long ll;
ll t,n;
ll a[66],dp[66][66][66];
ll dfs(ll pos,int sta,int pre,bool limit)
{
    if(pos==0) return sta;
    if(!limit&&dp[pos][pre][sta]!=-1)
        return dp[pos][pre][sta];
    int up=limit? a[pos]:9;
    ll ret=0;
    for(int i=0;i<=up;i++)
        ret+=dfs(pos-1,sta||(pre==4&&i==9),i,limit&&(i==up));
    if(!limit)
        return dp[pos][pre][sta]=ret;
    return ret;
}
ll solve(ll x)
{
    ll pos=0;
    while(x)
    {
        a[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,0,1);
}
int main()
{
    scanf("%d",&t);
    memset(dp,-1,sizeof(dp));
    while(t--)
    {
        scanf("%lld",&n);
        printf("%lld\n",solve(n));
    }
    return 0;
}

G - windy数 HYSBZ - 1026

题意：windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？
解析：
这里不仅要讨论前导零，我们也需要用pre状态讨论前缀数字，于是可以新建一个flag状态来另讨论前导0
需要注意的一点根据hint来看，002也算作windy数.也就是说前面全是0的情况要另作判断，其他情况自然就是flag为1即不含前导0的i-pre关系判断即可，具体看if语句的处理部分

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a,b;
ll num[66],dp[66][66][2];
ll dfs(ll pos,ll pre,int flag,bool limit)
{
    if(pos==0) return 1;
    if(!limit&&dp[pos][pre][flag]!=-1)
        return dp[pos][pre][flag];
    int up=limit? num[pos]:9;
    ll ret=0;
    for(int i=0;i<=up;i++)
    {
        if(!flag||abs(i-pre)>=2)
            ret+=dfs(pos-1,i,flag||i,limit&&(i==up));
    }
    if(!limit)
        return dp[pos][pre][flag]=ret;
    return ret;
}
ll solve(ll x)
{
    memset(dp,-1,sizeof(dp));
    ll pos=0;
    while(x)
    {
        num[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,0,1);
}
int main()
{
    cin>>a>>b;
    cout<<solve(b)-solve(a-1)<<endl;
    return 0;
}