pat 1049 Counting Ones
2024-08-21 07:06:32
要统计1到N之间‘1’的个数,如数11包含2个1.所以当N=12时,答案为5。
思想:
找规律,假设ans[N]表示1到N的‘1’的个数,则有a[100]=(a[10]-1)*9+10+a[10]-1+1;
先打表求出1ek的答案;
然后对N由高到低逐位拆分。
有种情况要特别注意:
当N=100001时,高位出现1时要累加到后面第一个非0位数上。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include <algorithm>
#include "malloc.h"
#include <cstring>
using namespace std;
#define LL long long
LL a[20]={0,1,2,21};//0, 1, 10,100,...
LL b[20]={1,10,100};
int main()
{
int i=3,j=2,n,cnt=0;
LL c=(1<<30),x,ans=0;
while(b[i-1]<=c){
a[i]=(a[i-1]-1)*9+b[i-2]+a[i-1]-1+1;
b[i]=b[i-1]*10;
i++;
// printf("%d %lld %lld %lld\n",i-1,a[i-1],b[i-1],c);
}
n=i;
scanf("%lld",&x);
if (x<10)
{
printf("1\n");
return 0;
}
j=0;
while(b[j]<=x)j++;
j--;
int flag=0;
while(x>0)
{// ans+=b[j]+(a[j+1]-1)+(n-1)*(a[j+1]-1);
n=x/b[j];
if(n==0);
else if(n==1)
ans+=(flag*x+a[j+1]),flag=0;
else
ans+=(flag*x+(n-1)*(a[j+1]-1)+b[j]+(a[j+1]-1)),flag=0;
if(n==1)flag=1;
x-=n*b[j--];
}
printf("%lld\n",ans);
return 0;
}
最新文章
- Java EE 经验
- 有用的php函数
- js闭包详解
- Zbrush遮罩边界该怎么实现羽化和锐化
- SqlSever基础 dateadd month 增加五个月
- svn教程
- MFC让控件随窗口大小而改变
- RegexOptions枚举
- IIS优化服务器性能导致QuartZ任务未运行
- IOS之富文本编辑
- C#计算表达式(仿计算器功能)
- 反编译Unity3D手机游戏
- 任务调度 ----->; quartz 不同时间间隔调度任务
- [Swift]LeetCode110. 平衡二叉树 | Balanced Binary Tree
- npm版本安装问题
- python 机器学习
- dd、split、csplit命令
- mvn多环境下的配置
- Linux巩固记录(7) Hbase安装
- python传输文件