首页 > 其他分享 >数位DP

数位DP

时间:2022-11-12 19:33:39浏览次数:65  
标签:return int pos limit DP include dp 数位

通常问法:区间[l,r]的数中,满足某一条件数的个数。
技巧1:[x,y] 中满足情况的个数位f[y]-f[x-1]
技巧2:从树的角度考虑问题
例题1:度的数量
题意:寻找[L,R]之间满足,是K个互不相等的整次幂之和
题解:
1:数位DP
2:f[R]-f[L-1]
3:现在我们的问题转化位了分别找到0~R的值,即0 ~ L-1的值,然后做差即可。
4:利用树的思想,我们先从最低位讨论,然后在本位的确定值的情况下找到下一个值
下面是AC代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=35;
int K,B;
int f[N][N];
void init()
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(!j) f[i][j]=1;
            else f[i][j]=f[i-1][j]+f[i-1][j-1];
        }
    }
}
int dp(int n)
{
    if(n==0) return 0;
    vector<int> nums;
    while(n) nums.push_back(n%B),n/=B;
    int res=0;
    int last=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        if(x>0)//只有大于0时讨论左右边界
        {
            //当前位置放0
            res+=f[i][K-last];
            if(x>1)//当前位置放1也满足情况
            {
                if(K-last-1>=0) res+=f[i][K-last-1];
                break;
            }
            else//讨论右分支
            {
                last++;
                if(last>K) break;//这里是满足的,这里可能会有些疑惑,下面的位数中是不是已经讨论完全了,实际上已经讨论完了的。因为,此时如果后面每多一个1,在前面必须少1个1,这样的情况实际上是在前面为0时已经讨论过了。
            }
        }
        if(i==0&&last==K) res++;//这种情况是特殊的一种情况,假设有5位,每一位都可以为1,到了11111的时候本应该继续往下讨论的,但是终止了,这种情况没有被加上,所以应该加上这种情况,可以自己将这种情况手推一下。
    }
    return res;
}
int main()
{
    init();
    int l,r;
    cin>>l>>r>>K>>B;
    cout<<dp(r)-dp(l-1)<<endl;
    return 0;
}

因为用dfs写数位dp的话更加好写,而且不用判特例,所以下面是dfs版本:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[100][50];//当前是第pos位,已经选了j个bit
int a[100];
int x,y,k,b;
int dfs(int pos,int num,int limit)//这里的num表示前面已经选了num个1
{
    if(num==k) return 1;
    if(num>k+1) return 0;
    if(pos==-1) return num==k;//表示到最后也没有实现
    if(!limit && dp[pos][num]!=-1) return dp[pos][num];
    int up=limit?a[pos]:b-1;
    int res=0;
    for(int i=0;i<=min(up,1);i++)
    {
        res+=dfs(pos-1,num+i,limit&&i==a[pos]);
    }
    if(!limit) dp[pos][num]=res;
    return res;
}
int solve(int num)
{
    int pos=0;
    memset(dp,-1,sizeof(dp));
    while(num)
    {
        a[pos++]=num%b;
        num/=b;
    }
    return dfs(pos-1,0,true);//第一位肯定是有限制的
}
int main()
{
    cin>>x>>y>>k>>b;
    printf("%d\n",solve(y)-solve(x-1));
    return 0;
}

例题2:数字游戏
题意:
1:给定l,r
2:求l~r之间的上升数字
3:123,234,346这样的数字被称作上升数字
题解:数位dp
依旧是看作一棵树来处理,树的左边是当前的数枚举(0~a[i]-1),这样的情况下面所有情况成立的情况都是满足的,然后枚举到了a[i],把这个当作last,进行下面的枚举,如果此时的last太大了,下面的最大位也比他大,直接break,如果到了最后仍然没有break,那么加上最后一种情况。
下面是AC代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=15;
int f[N][N];//f[i][j]表示一共有i位,最高位为j的方案数
void init()//线性dp求方案数
{
    for(int i=0;i<=9;i++) f[1][i]=1;
    for(int i=2;i<N;i++)
        for(int j=0;j<=9;j++)
           for(int k=j;k<=9;k++)
               f[i][j]+=f[i-1][k];
}
int dp(int n)
{
    if(!n) return 1;
    vector<int> nums;
    while(n) nums.push_back(n%10),n/=10;
    int res=0;
    int last=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        for(int j=last;j<x;j++)
            res+=f[i+1][j];//这里是i-1因为vector的下标从0开始
        if(x<last) break;
        last=x;
        if(!i) res++;
    }
    return res;
}
int main()
{
    init();
    int l,r;
    while(cin>>l>>r) cout<<dp(r)-dp(l-1)<<endl;
    return 0;
}

我们可以先理解一下f[N][N],其中f[i]][j]表示只有i位,最高位是j。这样我们f[i][j]+=f[i-1][j~9]就是答案,这样从低位开始,可以得到答案。
然后我们再理解数位dp,这个题和上个题很类似,只是这个题的每位的数量不再是1,而是可以很多数,所以从小到大枚举数即可,最后假设都没有break出去的话就加上那种情况。
下面是dfs版本:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[50][50];//dp[i][j]表示pos位,前面是j的数量
int a[50];
int l,r;
int dfs(int pos,int pre,bool limit)
{
    if(pos==-1) return 1;
    if(!limit && dp[pos][pre]!=-1) return dp[pos][pre];
    int up=limit?a[pos]:9;
    int res=0;
    for(int i=0;i<=up;i++)
    {
        if(i<pre) continue;
        res+=dfs(pos-1,i,limit&&i==a[pos]);
    }
    if(!limit) dp[pos][pre]=res;
    return res;
}
int solve(int x)
{
    int pos=0;
    memset(dp,-1,sizeof(dp));
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,-1,true);//第一位绝对是有限制的
}
int main()
{
    int l,r;
    while(cin>>l>>r)
    {
        printf("%d\n",solve(r)-solve(l-1));
    }
    return 0;
}

例题3:windy数
题意:找出[l,r]之间满足条件的数
题解:数位dp模板,但是这里要注意是应该考虑前导0
下面是dfs版的代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[50][50];//dp[i][j]表示pos位,前面是j的数量
int a[50];
int l,r;
int dfs(int pos,int pre,bool lead,bool limit)
{
    if(pos==-1) return 1;
    if(!limit && dp[pos][pre]!=-1&&!lead) return dp[pos][pre];
    int up=limit?a[pos]:9;
    int res=0;
    for(int i=0;i<=up;i++)
    {
        if(lead==true) res+=dfs(pos-1,i,i==0,limit&&i==a[pos]);
        else if(i-pre>=2||pre-i>=2) res+=dfs(pos-1,i,i==0,limit&&i==a[pos]);
    }
    if(!limit&&!lead) dp[pos][pre]=res;
    return res;
}
int solve(int x)
{
    int pos=0;
    memset(dp,-1,sizeof(dp));
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,true,true);//第一位绝对是有限制的
}
int main()
{
    int l,r;
    while(cin>>l>>r)
    {
        printf("%d\n",solve(r)-solve(l-1));
    }
    return 0;
}

例题4:数字的游戏Ⅱ
题意:就是找到[l,r]之间的加起来各位数之和mod为0的数字个数。
题解:数位dp模板
下面是dfs版本的代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int f[110][1100];//表示到了第i个位置,和为j的方案数
int a[100];
int l,r,n;
//不用管前导0
int dp(int pos,int sum,bool limit)
{
    if(pos==-1) return sum%n==0;
    if(!limit && f[pos][sum]!=-1) return f[pos][sum];
    int up=limit?a[pos]:9;
    int res=0;
    for(int i=0;i<=up;i++)
    {
        res+=dp(pos-1,sum+i,limit&&i==a[pos]);
    }
    if(!limit) f[pos][sum]=res;
    return res;
}
int solve(int x)
{
    int pos=0;
    memset(f,-1,sizeof(f));
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dp(pos-1,0,true);
}
signed main()
{
    while(cin>>l>>r>>n) cout<<solve(r)-solve(l-1)<<endl;
    return 0;
}

例题5:戳我
题意:求\([l,r]\)内的数的在[k,z]进制内的回文数的数量。
下面是AC代码:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn = 100;

int a[maxn],k,n;
int temp[maxn];

ll dp[40][maxn][maxn][2];
ll dfs(int pos,bool status,int len,bool limit,int k)
{
    if( pos < 0 ) {
        if( status ) return k;
        else return 1;
    }
    if(!limit && dp[k][pos][len][status]!=-1) return dp[k][pos][len][status];

    int up=limit?a[pos]:k-1;
    ll ans=0;

    for(int i=0;i<=up;i++)
    {
        temp[pos]=i;//记录数
        if( i == 0 && len == pos)//前导0 
        {
            ans += dfs(pos-1, status, len-1, limit && (i==up),k);
        }
        else if( status && pos < (len+1)/2 ) 
        {
            ans += dfs(pos-1, i == temp[len-pos], len, limit&&(i==up),k );
        }
        else 
        {
            ans += dfs(pos-1, status, len, limit&&(i==up),k );
        }
    }
    if(!limit) dp[k][pos][len][status]=ans;
    return ans;
}
ll solve(ll x,int k)
{
    if( x == 0 ) return k;
    int pos=0;
    while(x)
    {
        a[pos++]=x%k;
        x/=k;
    }
    return dfs(pos-1,true,pos-1,true,k);
}
int main()
{
    ll le,ri,l,r;
    int t;
    scanf("%d",&t);
    int cases=1;
    memset(dp,-1,sizeof(dp));
    while(t--)
    {
        ll res=0;
        scanf("%lld%lld%lld%lld",&le,&ri,&l,&r);
        for( int i = l; i <= r; i++ ) {
            res += solve(ri, i) - solve(le-1, i);
        }
        printf( "Case #%d: %lld\n", cases++, res );
    }
}

注:数位dp可以通过增加dp的维数来降低时间复杂度,我们以下面两个题为例:
1:数字游戏 II
可以这样写:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int f[110][1100];//表示到了第i个位置,和为j的方案数
int a[100];
int l,r,n;
//不用管前导0
int dp(int pos,int sum,bool limit)
{
    if(pos==-1) return sum%n==0;
    if(!limit && f[pos][sum]!=-1) return f[pos][sum];
    int up=limit?a[pos]:9;
    int res=0;
    for(int i=0;i<=up;i++)
    {
        res+=dp(pos-1,sum+i,limit&&i==a[pos]);
    }
    if(!limit) f[pos][sum]=res;
    return res;
}
int solve(int x)
{
    int pos=0;
    memset(f,-1,sizeof(f));
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dp(pos-1,0,true);
}
signed main()
{
    while(cin>>l>>r>>n) cout<<solve(r)-solve(l-1)<<endl;
    return 0;
}

也可以这样写:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int f[110][1100][3];//表示到了第i个位置,和为j的方案数
int a[100];
int l,r,n;
//不用管前导0
int dp(int pos,int sum,bool limit)
{
    if(pos==-1) return sum%n==0;
    if( f[pos][sum][limit]!=-1) return f[pos][sum][limit];
    int up=limit?a[pos]:9;
    int res=0;
    for(int i=0;i<=up;i++)
    {
        res+=dp(pos-1,sum+i,limit&&i==a[pos]);
    }
    return f[pos][sum][limit]=res;
}
int solve(int x)
{
    int pos=0;
    memset(f,-1,sizeof(f));
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dp(pos-1,0,true);
}
signed main()
{
    while(cin>>l>>r>>n) cout<<solve(r)-solve(l-1)<<endl;
    return 0;
}

两个写的主要区别就是可以通过将lead,limit这类影响记忆化的操作记入数组,增加维数,降低复杂度。

D
Find the Number
(300分)
Let's call a number x good if x is an interger and ctz(x)=popcount(x).

ctz(x) is the number of trailing zeros in the binary representation of x.

popcount(x) is the number of 1's in the binary representation of x.

For example:

ctz(12)=ctz(1100)=2 and popcount(12)=popcount(1100)=2, so 12 is a good number.

Now you are given an interval [l,r], you need to find a good number in it. If there are multiple solutions, print any of them; if there is no solution, print −1 instead.

输入格式:
The first line contains a single integer T (1≤T≤\(10^{5}\)
) --- the number of test cases.

For each test case, there is one single line containing two integers l,r (1≤l≤r≤\(10^{9}\)
) --- the interval.

输出格式
For each test case, print one line containing the answer.

If there are multiple solutions, print any of them; if there is no solution, print −1 instead.

输入样例:
5
38 47
57 86
23 24
72 83
32 33
输出样例:
-1
68
-1
-1
-1
这个题的话下面是AC代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;
#define endl '\n'
const int N = 40;
int n, m, f[N][N][N][2];
int nums[N], len;
int last;
set<int> S;

int dfs(int pos, int cnt1, int cnt0, int limit, int lead)
{
    int &v = f[pos][cnt1][cnt0][lead];
    if(!limit && ~v) return v;
    if(!pos) return (cnt1 && cnt1 == cnt0);
    int up = limit ? nums[pos] : 1, res = 0;
    res += dfs(pos - 1, cnt1, cnt0 + 1, limit & (up == 0), lead);
    if(up == 1) res += dfs(pos - 1, cnt1 + 1, 0, limit & (up == 1), 0);
    return limit ? res : v = res;
}

int dp(int x)
{
    if(!x) return 0;
    len = 0;
    while(x) nums[++ len] = x & 1, x >>= 1;
    return dfs(len, 0, 0, 1, 1);
}

bool check(int mid)
{
    return dp(mid) >= last + 1;
}

void solve()
{
    int a, b;
    cin >> a >> b;
    if(S.size())
    {
        int t = *S.lower_bound(a);
        if(t >= a && t <= b) 
        {
            cout << t << endl;
            return ;
        }
    }
    
    last = dp(a - 1);
    int l = a, r = b;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    if(check(r)) 
    {
        cout << r << endl;
        S.insert(r);
    }
    else puts("-1");
}

signed main()
{
    memset(f, -1, sizeof f);
    int T = 1;
    cin >> T;
    while(T -- ) solve();
    return 0;
}

这个代码就是将lead这一维加入到了数组里面,时间就变快了,不然的话这个题用数位dp的话很容易超时,但是这种方法也不是一定的,我们应具体问题,具体分析,如果不会分析,就多交两遍。

标签:return,int,pos,limit,DP,include,dp,数位
From: https://www.cnblogs.com/kingwz/p/16884476.html

相关文章

  • 在WordPress中,如果你想自动转换URL,跳转至超链接页面,你可以利用内置的函数make_clickab
    <?php/*在WordPress中,如果你想自动转换URL,跳转至超链接页面,你可以利用内置的函数make_clickable()执行此操作。如果你想基于WordPress之外操作该程序,那么你可以参考wp-in......
  • 区间dp
    区间dp:顾名思义,就是从小的区间推向大的区间。区间dp的一般模板:for(intlen=1;len<=n;len++){for(intj=1;j+len<=n+1;j++){intr=j+len-1;......
  • P3226 [HNOI2012]集合选数(状压 DP)
    P3226[HNOI2012]集合选数要求选出集合\(S\)满足如果\(x\)选择了,\(2x\)和\(3x\)都不能选择。求\(\{1,2,\dots,n\}\)的符合要求的子集数量。\(n\le10^5\)。......
  • 基于QPSK+LDPC的微波信道误码率matlab仿真
    目录一、理论基础二、核心程序三、测试结果FPGA教程目录MATLAB教程目录一、理论基础  1.1QPSKQPSK数字解调包括:模数转换、抽取或插值、匹配滤波、时钟和载......
  • UDP --02--UDP广播数据
    设计模型局域网UDP广播数据端UdpBroadCast.cpp #include<tchar.h>//_T宏#include<stdio.h>//printfsprintf#include<iostream>//coutfstreamusingnamespacestd;......
  • 如何检测UDP 端口是否连接成功?
    (转,仅作为个人学习备用,原文地址: https://blog.51cto.com/kusorz/1749878)根据测试环境的不同,用户可以参阅如下方式测试UDP端口的连通性。假设待测试服务器的IP地址为1.1.......
  • Apple开发_Socket_UDP协议广播机制的实现
    1、前言1.1什么是UDP协议广播机制?举一个例,例如在一群人群中,一个人要找张三,于是你向人群里大喊一声(广播):“谁是张三”如果它是张三,它就会回应你,在网络中也是一样的......
  • ABC 267 D - Index × A(Not Continuous ver.) (DP)
    https://atcoder.jp/contests/abc267/tasks/abc267_d题目大意:给定长度为n的数组a,让我们从中选择m个数字,按顺序组成B(a1----am)之后,sum=1*a1+……+m*am;问我们sum最大......
  • 在关闭RDP远程连接后,保持windows程序的运行
    问题在最近将笔记本放在了宿舍24小时开机由于挂网课,在教室里可以用微软RDClientapp连接宿舍里的电脑查看刷课进度。但是在几次连接后发现,在ipad端关闭'RDP'远程连接后,笔......
  • 单调队列优化DP
    [POI2015]WIL题目描述给定一个长度为\(n\)的序列,你有一次机会选中一段连续的长度不超过\(d\)的区间,将里面所有数字全部修改为\(0\)。请找到最长的一段连续区间,使得......