nod_1009 数字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的个数

思路：

假设十进制数N的位数是K。我们分别统计【1，N】中第1位、第2位，....，第K位是1的数的个数。然后相加。【【巧妙！】】

分类讨论。

代码：

int n;

int main(){

    cin >> n;

    int w=(int)log10(n)+1;

    ll ans=0;

    rep(i,0,w-1){

        int left, cur, right, tmp;

        cur=w-i;

        tmp=(int)pow(10,cur-1);

        right=n%tmp;

        left=n/tmp/10;

        int curNum=n/tmp%10;

        if(curNum<1){

            ans+=((ll)left*tmp);

        }

        else if(curNum==1){

            ans+=((ll)left*tmp+1+right);

        }

        else{

            ans+=((ll)(left+1)*tmp);

        }

    }

    print("%lld\n",ans);

    ret 0;

}

巴特西

nod_1009 数字1的数量（分析题）

最新文章

热门文章