PAT A1049 Counting Ones (30分)

前言

传送门

正文

参考题解

#include<iostream>
using namespace std;
/* 题意： 给定一个正整数n，求从1~n中每个十进制数中'1'的个数总和 思路：由于直接从1~n循环遍历计数会有两个测试点超时，因此考虑 是否有规律，能否扩展到一般情况去 。对于每一位数，分其为0,1和2~9 进行讨论 eg:170218 */
typedef long long LL;
int main(){
	int n,left,right,now;
	LL res=0;
	cin>>n;
	for(int i=1;i<=n;i=i*10){
		right=n%i;
		left=n/(i*10);
		now=n/i%10;
		if(now==0)res+=left*i;
		else if(now==1)res+=left*i+right+1;
		else res+=(left+1)*i;
	}
	cout<<res<<endl;
	return 0;
} 

参考链接：
1.https://www.shuzhiduo.com/A/obzbgyq1JE/
2.https://www.liuchuo.net/archives/2305