当前位置：首页 > news >正文

【补题】P10424 [蓝桥杯 2024 省 B] 好数（数位dp）

news 来源：原创 2025/9/19 10:10:28

题意：

一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位……）上的数字是奇数，偶数位（十位、千位、十万位……）上的数字是偶数，我们就称之为“好数”。

给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。

思路：

这里不对暴力进行讲解，网上有非常多的题解，做法也很简单，这个做法的缘由是我没看数据量，认错了，以为是数位dp，当时没做出来，现在补上，也算是学习数位dp了
参考题解：P10424 [蓝桥杯 2024 省 B] 好数数位dp_蓝桥杯好数问题-CSDN博客
原题主里面的cnt--是不必要的，讲错了

思路其实也不难，就是标准的数位dp，这里讲解是怎么来理解这道题的数位dp的

dp[i]表示的是，当前位置之前填写最高位的这个时刻，填剩下所有可能数的大小，往后就是默认填写最高位数字的，如果不是很明白推荐董晓老师的数位dp

1.dp[i]代表当前这一位在填写[1,3,5,7,9]或者[0,2,4,6,8]（注意要小于数本身）的可能算上所有的个数，因为高位固定，低位一定能两个区间都能取的，直接预处理pre数组，进行计算就好。个数就是能填的个数xpre[i],注意不包括本身

2.为什么不包括本身，因为本身是不可直接计算的，因为你计算的话可能超过本身的数。dp那里计算的是一定能得到的所有数，所以最后有一个if，判断最后dp结束的那个数本身。

3.但这并没有结束,因为其实奇数位是能填0的，前提是高位没有任何数，所以加上最后的个数，就是答案。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+10;
const int INF = 1e18;
const int MOD = 1e9+7;int pre[20],num[20];void solve(){int n;cin >> n;pre[1]=1;for(int i=2;i<20;i++){pre[i]=pre[i-1]*5;}int cntt=1;while(n){num[cntt++]=n%10;n/=10;}cntt--;int sum=0;for(int i=cntt;i>=0;i--){int cur=num[i];if(cur){int cnt=0;if(i&1){cnt+=cur/2;}else{cnt+=(cur+1)/2;}sum+=cnt*pre[i];}if( (i&1) != (num[i]&1) ){break;}if(i==1 && num[i]&1){sum++;}}for(int i=cntt;i>1;i--){if(i&1){sum+=pre[i];}}cout << sum << endl;}signed main() {IOS;int t = 1;
//	cin >> t;while (t--) {solve();}}

相关文章：