【PAT甲级】1049 如何运用数位DP思想高效计数？

本文共计294个文字，预计阅读时间需要2分钟。

题目：计算从1到N（N=2^30）之间共有多少个数字。

代码：pythondef count_digits(N): count=0 for i in range(1, N + 1): count +=len(str(i)) return count

N=2**30print(count_digits(N))

题意：

输入一个正整数N（N<=2^30），输出从1到N共有多少个数字包括1。

代码：

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
int ans=0;
int l=0,r=0,low_bit=1,yushu=0;//当前位左边的数字，当前位右边的数字，当前位，当前位上的数字
while(n/low_bit){
l=n/(10*low_bit);
yushu=n/low_bit%10;
r=n%low_bit;
if(!yushu)
ans+=l*low_bit;//当前位为1时，左边数字可以从0~l-1，故有l*low_bit
else if(yushu==1)
ans+=l*low_bit+r+1;//当前位为1时，有为0时加上右边数字为0~r，故有l*low_bit+r+1
else
ans+=(l+1)*low_bit;//当前位大于1时，左边数字从0~l，当前位只要为1就符合题意，故有(l+1)*low_bit
low_bit*=10;//当前位左移
}
cout<<ans;
return 0;
}