1009 数字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示例
12
Output示例
5
关于计数的一个DP
#include<bits/stdc++.h>using namespace std;int dp[15];void init(){ dp[0]=0; dp[1]=1; for(int i=2;i<11;i++) dp[i]=10*dp[i-1]+pow(10,i-1);}int main(){ int n; init(); while(~scanf("%d",&n)) { int nr=0; int temp=1; long long ans=0; while(n) { int k=n%10; if(k==1) { ans+=dp[temp-1]; ans+=(nr+1); } else if(k!=0){ ans+=(k*dp[temp-1]+pow(10,temp-1)); } nr+=k*powl(10,temp-1); n/=10; temp++; } cout<<ans<<endl; }}新闻热点
疑难解答
