1049 Counting Ones (数学）

1049 Counting Ones (数学）

思路：考虑对数的每一位贡献进行计算。

假设对于当前位：$now$，其对应的$1$开头后面全为0的数为：$a$。

如$12345$，假设$now=4$，$a=10$。$now=2,a=1000$

令$now$左边组成的数为：$l$，右边组成的数为：$r$。

分情况讨论：

$1.now=0$

这种情况：该位为$1$的贡献只能在$left\in [0,l?1]$产生，一共$l$种情况。

而右边的贡献为$right\in [0,a?1]$，共$a$种情况。

根据乘法原理有：$contribution=l\times a$种情况。

2.$now=1$。

这种情况与上面相比，还需考虑当左边为$l$时，右边可以为$[0,r]$。

所以还要加上$r+1$。

$contribution=l\times a+r+1$

3.$now>1$。

这种情况$left\in [0,l]$，$right\in [0,a?1]$。

$contribution=(l+1)\times a$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
#define ios ios::sync_with_stdio(false),cin.tie(0)
int n,ans,l,r,a=1,now;
int main(){
    scanf("%d",&n);while(n/a){
    l=n/(a*10),r=n%a,now=n/a%10;if(!now) ans+=l*a;else if(now==1) ans+=l*a+r+1;else ans+=(l+1)*a;a*=10;}printf("%d\n",ans);return 0;
}