51 Nod 数字1的数量

基准时间限制：1 秒空间限制：131072 KB 分值: 5 难度：1级算法题

给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。

例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。

Input

输入N(1 <= N <= 10^9)

Output

输出包含1的个数

Input示例

Output示例

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

int ans=0;

int a[10];

ll mypow(int a,int b)

{

ll res=1;

for(int i=0;i<b;i++)res*=a;

return res;

}

ll f(int pos1,int pos2)

{

int len=pos2-pos1+1;

ll res=0;int cnt=1;

for(int i=pos1;i<=pos2;i++)res+=a[i]*mypow(10,len-(cnt++));

return res;

}

int main()

{

//freopen("in.txt","r",stdin);

ll N;

cin>>N;

ll len=0;

ll t=N;

while(t>0)

{

t/=10;len++;

}

if(len==1){cout<<1<<endl;return 0;}

else

{

t=N;int pos=len-1;

while(t>0)

{

a[pos--]=t%10;

t/=10;

}

if(a[0]==1)ans=(f(1,len-1)+1);

else ans=mypow(10,len-1);

for(int i=1;i<len;i++)

{

if(a[i]==0)

{

ans+=(f(0,i-1))*mypow(10,len-i-1);

}

if(a[i]==1)

{

ans+=(f(0,i-1)*mypow(10,len-i-1));

ans+=(f(i+1,len-1)+1);

}

if(a[i]>1)

{

ans+=(f(0,i-1)+1)*mypow(10,len-i-1);

}

}

cout<<ans<<endl;

}

return 0;

}

巴特西

51 Nod 数字1的数量

最新文章

热门文章