注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

bjfu-1152 数1  

2013-01-17 11:02:49|  分类: ACM-bjfu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

数1

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:13            测试通过:6

描述

最近ACM爱好者协会交给了bjfuwfy 一个任务:给出一个正整数n,记f(a)为整数a中“1”出现的次数(比如“10”这个数,有一个“1”;“11”这个数,有两个“1”),求f(1)+f(2)+...+f(n)的结果。聪明的你能帮助bjfuwfy求解么?

输入

输入有多组测试数据,每一组测试数据占一行,为一个整数n,1<= n <=99,999,999,999

输出

每组测试数据输出占一行,输出一个数,表示f(1)+f(2)+...+f(n)的结果。

样例输入

1
2
3
13
23

样例输出

1
1
1
6
13

————————————————————————————————————————

简单的找规律,对于一个数n,从1到n出现1的总次数,可以分类讨论,个位上出现了几次,十位上出现了几次……最后相加即可,规律见代码注释

/*
* test.cpp
*
* Created on: 2013-01-17
* Author: fudq
* 找规律:
* 除了第一位之外,其余位满足以下条件(记p为当前位的数,res为最后的结果,tt为该位的位数(个位表示1,十位表示2)):
* 如果p==0,res+=10^(tt)*(该位前面部分数字);
* 如果p==1,res+=10^(tt)*(该位前面部分数字)+(该位后面部分数字+1);
* 否则,res+=10^(tt)*(该位前面部分数字+1)。
* 第一位的规律:
* 如果是1,res+=该位后面部分数字+1;否则res+=10^tt;
*/
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<iostream>
using namespace std;
typedef __int64 int64;

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int64 n,t,q,res,num;
int p;
while(scanf("%I64d",&n)!=EOF)
{
t=1;q=0;res=0;
while(n>=10)
{
p=n%10;
if(p==0)
num=t*(n/10);
else if(p==1)
num=t*(n/10)+(q+1);
else
num=t*(n/10+1);
res+=num;
q+=t*p;
n/=10;
t*=10;
}
if(n==1)
res+=q+1;
else
res+=t;
printf("%I64d\n",res);
}
return 0;
}


  评论这张
 
阅读(118)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018