YBT 5.3 数位动态规划记忆化搜索的专题题解在代码中 Amount of Degrees[loj 10163] 数字游戏[loj 10164] Windy 数[loj 10165] 数字游戏[loj 10166] 不要 62[loj 10167] 恨 7 不成妻[loj 10168] 数字计数[loj 10169]

/*
此题可以转换成将10进制转成b进制后有k个1其他都为0的个数
所以用记忆化dfs
dp[pos][sum]表示将要处理第pos位，前面已有sum个一的数量 
*/ 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline long long read()
{
    long long f=1,ans=0;char c;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return ans*f;
}
int x,y,k,b,dg[31],ans,dp[101][101];
long long dfs(long long pos,long long sum,long long done,long long sry)
{
//    cout<<"位置:"<<pos<<" 一的个数："<<sum<<"  小于等于："<<done<<"  原来的数："<<sry<<endl;
    if(sum>k) return 0;
    if(pos==0) 
    {
        if(sum==k) return 1;
        return 0;
    }
    if(done==0&&dp[pos][sum]!=-1) return dp[pos][sum];
    long long end;
    if(done==0) end=1;
    else end=min(1,dg[pos]);
    long long maxn=0;
    for(long long i=0;i<=end;i++)
    {
        if(i==1) maxn+=dfs(pos-1,sum+1,done&&i==dg[pos],i);
        else maxn+=dfs(pos-1,sum,done&&i==dg[pos],i); 
    }
    if(done==0) dp[pos][sum]=maxn;
    return maxn;
}
long long solve(long long x)
{
    ans=0;memset(dg,0,sizeof(dg));
    while(x!=0)
    {
        dg[++ans]=x%b;
        x/=b;
    }
//    for(long long i=ans;i>=1;i--) cout<<dg[i]<<" ";
//    cout<<endl;
    return dfs(ans,0,1,2<<30-1);
 } 
int main()
{
    memset(dp,-1,sizeof(dp));
     x=read(),y=read(),k=read(),b=read();
     cout<<solve(y)-solve(x-1);
}

View Code

/*
记忆化dfs
dp[pos][sta]表示将要处理第pos位，上一位是sta的数量 
*/ 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
    int f=1,ans=0;char c;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
int dp[31][10],ans,dg[31];
int dfs(int pos,int sta,int done)//done为是否与原数小于或相等 
{
//    cout<<pos<<"  "<<sta<<"  "<<done<<endl;
    if(pos==0) return 1;
    if(done==0&&dp[pos][sta]!=-1) return dp[pos][sta];
    int end;
    if(done==0) end=9;
    else end=dg[pos];
//    cout<<end<<endl;
    int maxn=0;
    for(int i=sta;i<=end;i++)
        maxn+=dfs(pos-1,i,done&&i==dg[pos]);
    if(done==0) dp[pos][sta]=maxn;
    return maxn;
}
int solve(int x)
{
    ans=0;
    while(x!=0)
    {
        dg[++ans]=x%10;
        x/=10;
    }
//    cout<<ans<<endl;
//    for(int i=ans;i>=1;i--) cout<<dg[i]<<" ";cout<<endl;
    return dfs(ans,0,1);
}
int main()
{
    memset(dp,-1,sizeof(dp));
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        printf("%d
",solve(b)-solve(a-1));
//        return 0;
    }
    return 0;
}
/*
1 20
*/

View Code

/*
注意前导0，将它转换成11即可，想一想为什么
dp[pos][sta]，记忆化dfs
当前位数，上次的数字 
*/ 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
inline long long read()
{
    long long f=1,ans=0;char c;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
long long dp[32][32];
long long dg[32];
long long dfs(long long pos,long long sta,long long done)//若flag为0，没有出现真正位 
 {
//     cout<<"位数："<<pos<<" 所得位数："<<sta<<"  与原数的大小："<<done<<" 有没有真正的位"<<flag<<endl;
    if(pos==0)  return 1;
    if(done==0&&dp[pos][sta]!=-1)  return dp[pos][sta];
    long long end;
    if(done==1) end=dg[pos];
    else end=9;
    long long maxn=0;    
    // dfs(ans,0,1,0)
    //long long dfs(long long pos,long long sta,long long done,bool flag)//若flag为0，没有出现真正位 
    for(long long i=0;i<=end;i++)
    {
        if(abs(i-sta)<2) continue;
        if(sta==11&&i==0) maxn+=dfs(pos-1,11,done&&i==end);
        else maxn+=dfs(pos-1,i,done&&i==dg[pos]);
    }
    if(done==0) dp[pos][sta]=maxn;
    return maxn;
}
long long solve(long long x)
{
    memset(dg,0,sizeof(dg));
    long long ans=0;
    while(x!=0)
    {
        dg[++ans]=x%10;
        x/=10;
    }
//    for(long long i=ans;i>=1;i--) cout<<dg[i]<<" ";cout<<endl;
    return dfs(ans,11,1);
}
int main()
{
    memset(dp,-1,sizeof(dp));
    long long a=read(),b=read();
    cout<<solve(b)-solve(a-1);
     int x; 
//     while(scanf("%d",&x)!=EOF) cout<<solve(x)<<endl;
//    long long x=read();cout<<solve(x);
    return 0;
}

View Code

/*
sum为mod n的和
记忆化dfs,dp[pos][sum]，不解释 
*/ 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
inline long long read()
{
    long long f=1,ans=0;char c;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
long long a,b,dg[101],dp[101][101],mod;
long long dfs(long long pos,long long sta,long long done,long long sum)
{
//    cout<<"位数："<<pos<<" 此数："<<sta<<" 是否小于等于："<<done<<"  和："<<sum<<endl;
    if(pos==0)
    {
        if(sum%mod==0) return 1;
        else return 0;
    }
    if(done==0&&dp[pos][sum]!=-1) return dp[pos][sum];
    long long end;
    if(done==0) end=9;
    else if(done==1) end=dg[pos];
    long long maxn=0;
    for(long long i=0;i<=end;i++)
    {
        maxn+=dfs(pos-1,i,done&&i==dg[pos],(sum+i)%mod);
    }
    if(done==0) dp[pos][sum]=maxn;
    return maxn;
}
long long solve(long long x)
{
    memset(dg,0,sizeof(dg));
    long long ans=0;
    while(x!=0)
    {
        dg[++ans]=x%10;
        x/=10;
    }
    return dfs(ans,0,1,0);
}
int main()
{

    while(cin>>a>>b>>mod)
    {    
        memset(dp,-1,sizeof(dp));
        cout<<solve(b)-solve(a-1)<<endl;
    }
//    a=read(),b=read(),mod=read();
    
}
/*
19 9
*/

View Code

/*
只要不让62，4进for循环即可
dp[pos][sta] 
*/ 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
    int f=1,ans=0;char c;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
int dg[31],dp[301][301];
int dfs(int pos,int sta,int done,bool flag)
{
//    cout<<pos<<" "<<sta<<" "<<done<<" "<<flag<<endl;
    if(pos==0) return 1;
    if(done==0&&dp[pos][sta]!=-1) return dp[pos][sta];
    int end;
    if(done==0) end=9;
    if(done==1) end=dg[pos];
    int maxn=0;
    for(int i=0;i<=end;i++)
    {
        if(i==4) continue;
        if(i==2&&flag==true) continue;
        if(i==6) maxn+=dfs(pos-1,i,done&&i==dg[pos],true);
        else maxn+=dfs(pos-1,i,done&&i==dg[pos],false);
    }
    if(done==0) dp[pos][sta]=maxn;
    return maxn;
}
int solve(int x)
{
    memset(dg,0,sizeof(dg));
    int ans=0;
    while(x!=0)
    {
        dg[++ans]=x%10;
        x/=10;
    }
//    for(int i=ans;i>=1;i--) cout<<dg[i]<<" ";
//    cout<<endl;
    return dfs(ans,0,1,false);
}
int main()
{
    memset(dp,-1,sizeof(dp));
//    int x=read();
//    cout<<solve(x)<<endl;return 0;
    while(1)
    {
        int a=read(),b=read();
        if(a==0&&b==0) return 0;
        cout<<solve(b)-solve(a-1)<<endl;
    }
}

View Code

/*
主要是求平方和，其他的都可以记忆化搜索实现
dp[pos][pre1][pre2]表示当前以pos位作为下一位，pre1记录数字和，pre2记录数字
（i+next）^2=i*i+2*i*next+next*next
而放眼望去，合并同类项后可的
 （i+next）^2=i*i+2*i*（接下来的数字和）+（平方和）
 所以搜索把每一个都记录下来即可 
*/ 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
const long long mod=1000000007;
using namespace std;
inline long long read()
{
    long long f=1,ans=0;char c;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return ans*f;
}
struct node{
    long long cnt;//个数
    long long sum;//和
    long long sqsum;//平方和 
}dp[51][51][51];
long long p[51];
long long dg[51];
node dfs(long long pos,long long pre1,long long pre2,long long done)//pre1表示数字和，pre2表示数字 
{
    if(pos==-1) 
    {
        node tmp;
        tmp.cnt=tmp.sqsum=tmp.sum=0;
        if(pre1!=0&&pre2!=0) tmp.cnt=1;
        return tmp;
    }
    if(done==0 && dp[pos][pre1][pre2].cnt!=-1) return dp[pos][pre1][pre2];
    long long end;
    if(done==0) end=9;
    if(done==1) end=dg[pos];
    node ans;
    ans.cnt=ans.sqsum=ans.sum=0;
    for(long long i=0;i<=end;i++)
    {
        if(i==7) continue;
        node tmp=dfs(pos-1,(pre1+i)%7,(pre2*10+i)%7,done&&i==dg[pos]);
        ans.cnt+=tmp.cnt;
        ans.cnt%=mod;
        ans.sum+=(tmp.sum+((p[pos]*i%mod)%mod)*tmp.cnt%mod)%mod;
        ans.sum%=mod;
        ans.sqsum+=(tmp.sqsum+((2*p[pos]%mod*i)%mod)*tmp.sum)%mod;
        ans.sqsum%=mod;
        
        ans.sqsum+=((p[pos]%mod*p[pos]%mod)*(tmp.cnt)%mod*(i%mod*i%mod)%mod);
        ans.sqsum%=mod;
    }
    if(done==0) dp[pos][pre1][pre2]=ans;
    return ans;
    
 } 
long long solve(long long x)
{
    long long anss=0;
    while(x!=0)
    {
        dg[anss++]=x%10;
        x/=10;
    }
    return dfs(anss-1,0,0,1).sqsum;
}
int main()
{
    p[0]=1;
    for(int i=1;i<31;i++)
        p[i]=(p[i-1]*10)%mod;
    for(int i=0;i<20;i++)
        for(int j=0;j<20;j++)
            for(int k=0;k<20;k++)
                dp[i][j][k].cnt=-1;
    long long t=read(),l,r;
  while(t--)
    {
        l=read();r=read();
        printf("%d
",(solve(r)-solve(l-1)+mod)%mod);
    }
}
/*
1
2065 7880
*/

View Code

/*
其实感觉跟例题1没有什么区别
只要再看看前导0即可 
*/ 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline long long read()
{
    long long f=1,ans=0;char c;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return ans*f;
}
long long a,b,cur,dg[31],dp[31][31];
long long dfs(long long pos,long long done ,long long zero,long long sum)
{
    if(pos==0) return sum;
    if(done==0&&zero==0&&dp[pos][sum]!=-1) return dp[pos][sum];
    long long end;
    if(done==1) end=dg[pos];
    else end=9;
    long long maxn=0;
    for(long long i=0;i<=end;i++)
        maxn+=dfs(pos-1,done&&i==dg[pos],zero&&i==0,sum+(cur==0&&i==0&&zero==0||cur&&i==cur));
    if(done==0&&zero==0) dp[pos][sum]=maxn;
    return maxn; 
}
long long solve(long long x)
{
    memset(dp,-1,sizeof(dp));
    long long ans=0;
    while(x!=0)
    {
        dg[++ans]=x%10;
        x/=10;
    }
    return dfs(ans,1,1,0);
}
int main()
{
    a=read(),b=read();
    for(cur=0;cur<=9;cur++)
        cout<<solve(b)-solve(a-1)<<" ";
}

View Code

YBT 5.3 数位动态规划 记忆化搜索的专题 题解在代码中 Amount of Degrees[loj 10163] 数字游戏[loj 10164] Windy 数[loj 10165] 数字游戏[loj 10166] 不要 62[loj 10167] 恨 7 不成妻[loj 10168] 数字计数[loj 10169]

题解在代码中

Amount of Degrees[loj 10163]

数字游戏[loj 10164]

Windy 数[loj 10165]

数字游戏[loj 10166]

不要 62[loj 10167]

恨 7 不成妻[loj 10168]

数字计数[loj 10169]

相关推荐

YBT 5.3 数位动态规划记忆化搜索的专题题解在代码中 Amount of Degrees[loj 10163] 数字游戏[loj 10164] Windy 数[loj 10165] 数字游戏[loj 10166] 不要 62[loj 10167] 恨 7 不成妻[loj 10168] 数字计数[loj 10169]