-
数位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#include #include #include #include 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; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
因为用dfs写数位dp的话更加好写，而且不用判特例，所以下面是dfs版本：
#include#include #include #include 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; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
例题2：数字游戏
题意：
1：给定l，r
2：求l~r之间的上升数字
3：123，234，346这样的数字被称作上升数字
题解：数位dp
依旧是看作一棵树来处理，树的左边是当前的数枚举(0~a[i]-1)，这样的情况下面所有情况成立的情况都是满足的，然后枚举到了a[i]，把这个当作last，进行下面的枚举，如果此时的last太大了，下面的最大位也比他大，直接break，如果到了最后仍然没有break，那么加上最后一种情况。
下面是AC代码：#include#include #include #include 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; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
我们可以先理解一下f[N][N]，其中f[i]][j]表示只有i位，最高位是j。这样我们f[i][j]+=f[i-1][j~9]就是答案，这样从低位开始，可以得到答案。
然后我们再理解数位dp，这个题和上个题很类似，只是这个题的每位的数量不再是1，而是可以很多数，所以从小到大枚举数即可，最后假设都没有break出去的话就加上那种情况。
下面是dfs版本：#include#include #include #include 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; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
例题3：windy数
题意：找出[l,r]之间满足条件的数
题解：数位dp模板，但是这里要注意是应该考虑前导0
下面是dfs版的代码：#include#include #include #include 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; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
例题4：数字的游戏Ⅱ
题意：就是找到[l,r]之间的加起来各位数之和mod为0的数字个数。
题解：数位dp模板
下面是dfs版本的代码：#include#include #include #include 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; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
例题5：戳我
题意：求 [ l , r ] [l,r] [l,r]内的数的在[k,z]进制内的回文数的数量。
下面是AC代码：#include#include #include #include #include #include #include #include #include #include #include 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 ); } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
注：数位dp可以通过增加dp的维数来降低时间复杂度，我们以下面两个题为例：
1：数字游戏 II
可以这样写：#include#include #include #include 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; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
也可以这样写：
#include#include #include #include 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; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
两个写的主要区别就是可以通过将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≤ 1 0 5 10^{5} 105
) — the number of test cases.For each test case, there is one single line containing two integers l,r (1≤l≤r≤ 1 0 9 10^{9} 109
) — 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#include #include #include 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; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
这个代码就是将lead这一维加入到了数组里面，时间就变快了，不然的话这个题用数位dp的话很容易超时，但是这种方法也不是一定的，我们应具体问题，具体分析，如果不会分析，就多交两遍。
-
相关阅读:
晨控CK-GW06系列网关与汇川可编程控制器MOSBUSTCP通讯手册
微分中值定理证明和总结
刷穿力扣（1~30）
C语言入门Day_24 函数与指针
如何在不牺牲质量的情况下降低采购成本？
【蓝桥杯真题练习】STEMA科技素养练习题库 答案版009 持续更新中~
Fiddler抓包工具详解
C++ 17 filesystem
自学Python第十五天-爬虫解析工具 RE 、BS4 和 xpath
Anaconda成功安装之后没有在菜单列和桌面显示图标
- 原文地址：https://blog.csdn.net/qq_54783066/article/details/126136974
