本文主要是介绍数位dp n内1的个数递推找规律，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1061:数字统计
- 查看
- 提交
- 统计
- 提问
- 总时间限制:
- 1000ms 内存限制:
- 10000kB
- 描述
- 给出一个整数n(1<=n<=20000000),要求输出从1到n间所有数字中“1”的出现次数．例如：数字11，1到11间数字“1”的出现次数为4。（1，10，11，11出现4次，因为11有两个1，所以出现4次） 输入
- 一个整数n，(1<=n<=20000000) 输出
- 输出一行，输出“1”的出现次数。 样例输入
-
11
样例输出 -
4
-
http://wyu.openjudge.cn/practice/1061
-
//修剪版！！！！！！！！！#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<map> #include<stack> #define rt return #define bk break #define ct continue #define sf scanf #define pf printf #define ms memset #define si(n) sf("%d",&n) #define pi(n) pf("%d\n",n) #define REP0(i,n) for(int i=0;i<(n);i++) #define REP1(i,n) for(int i=1;i<=(n);i++) #define REP(i,s,n) for(int i=s;i<=(n);i++) #define db double #define op operator #define pb push_back #define LL long long #define INF 0x3fffffff #define eps 1e-8 #define PI acos(-1) #define maxn 1010 using namespace std; int f[100]; void init(){f[0]=0;for(int i=1;i<=9;i++)f[i]=1;f[10]=2;f[11]=4;for(int i=12;i<=19;i++)f[i]=f[i-1]+1;for(int i=20;i<=99;i++){if(i%10==1)f[i]=f[i-1]+1;else f[i]=f[i-1];} } int dp(int n){if(n<=99)rt f[n];int tmp=1;while(tmp<=n)tmp*=10;tmp/=10;int res;if(n/tmp==1){res=dp(tmp-1)+dp(n%tmp)+10*(n/10-tmp/10)+(n%10)+1;}else {res=(n/tmp)*dp(tmp-1)+dp(n%tmp)+tmp;}rt res; } int main(){#ifdef ACBangfreopen("in.txt","r",stdin);freopen("dp.txt","w",stdout);#endifinit();int n;while(~sf("%d",&n)){int ans;if(n<=99)ans=f[n];else ans=dp(n);// pf("%d %d\n",n,ans);pf("%d\n",ans);}rt 0; }
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<map> #include<stack> #define rt return #define bk break #define ct continue #define sf scanf #define pf printf #define ms memset #define si(n) sf("%d",&n) #define pi(n) pf("%d\n",n) #define REP0(i,n) for(int i=0;i<(n);i++) #define REP1(i,n) for(int i=1;i<=(n);i++) #define REP(i,s,n) for(int i=s;i<=(n);i++) #define db double #define op operator #define pb push_back #define LL long long #define INF 0x3fffffff #define eps 1e-8 #define PI acos(-1) #define maxn 1010 using namespace std; int dp(int n){if(n==0)rt 0;if(n<=9)rt 1;int tmp=1;while(tmp<=n)tmp*=10;tmp/=10;int res;if(n/tmp==1){res=dp(tmp-1)+dp(n%tmp)+10*(n/10-tmp/10)+(n%10)+1;}else {res=(n/tmp)*dp(tmp-1)+dp(n%tmp)+tmp;}rt res; } int main(){#ifdef ACBangfreopen("in.txt","r",stdin);freopen("dp.txt","w",stdout);#endifint n;while(~sf("%d",&n)){int ans;ans=dp(n);pf("%d\n",ans);}rt 0; }
这篇关于数位dp n内1的个数递推找规律的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
