PAT甲级1049.

目录

A1049

题目

样例

输入:

12

输出:

5

思路和坑点

　　寻找数字的规律，统计从1-n的数字中所有1的个数，不妨这样思考：对于每一位而言，该位为1的数字有多少个，然后把每一位取到的个数相加，即最终的答案。
　　对于数的每一位而言：（以1014为例）
　　如果该位等于0（比如百位），则其左侧必有数字，记为left（1），说明该位可以取到1，比如0124，但其左侧的数字left只能取到[0，left-1]共left种情况，考虑其右侧的数字可以取遍[0，该位权值-1]。因此，该位取1的数字有left*该位权值个。
　　如果该位等于1(比如十位)，则其左边的数字记为left（10），右边数字记为right（4），左边数字可以先取[0，left-1]，类似于等于0时的情况，但是由于该位等于1，当左边数字取到left时，右侧的数字只能取[0，right]。因此，该位取1的数字有left*该位权值+right+1个。
　　如果该位大于1，当该位左侧数字可以取[0，left],同时右侧数字可以取[0，该位权值-1]。因此，该位取1的数字有（left+1）*该位的权值个。
　　补充
　　为了能清楚的理解该原理，可以按照从低到高依次竖排打印出每一位取1的数字情况以便参考。AC代码后面补充了打印1014的个位，十位，百位，千位取1时候的数字情况的测试代码，可以运行一下，以作观察和理解。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    cin>>n;
    int ans=0;
    int a=1;                    //a表示当前位的权值，初始化为1 
    while(n/a){                    //依次循环取每一位 
        int left=n/(a*10);        //取左边的数字 
        int right=n%a;            //取右边的数字 
        int now=n/a%10;            //去当前位 
        if(now==0)                //当前位等于0时 
            ans+=left*a;
        else if(now==1)            //当前位等于1时 
            ans+=left*a+right+1;
        else                     //当前位大于1时 
            ans+=(left+1)*a;
        a*=10;                    //权值扩大，为下一位判定做准备 
    }
    cout<<ans;
    return 0;    
}

用于理解的测试代码

#include<iostream>
#include<vector>
using namespace std;

int main(void){
    int i=1;
    vector<int> v1,v2,v3,v4;
    for(int i=1;i<=1014;i++){
        if(i%10==1) v1.push_back(i);
        if(i/10%10==1) v2.push_back(i);
        if(i/100%10==1) v3.push_back(i);
        if(i/1000==1) v4.push_back(i);
    }
    int id1,id2,id3,id4;
    id1=id2=id3=id4=0;
    while(1){
        if(id1<v1.size()) printf("%04d ",v1[id1++]);
        else     printf("     ");
        if(id2<v2.size()) printf("%04d ",v2[id2++]);
        else     printf("     ");
        if(id3<v3.size()) printf("%04d ",v3[id3++]);
        else     printf("     ");
        if(id4<v4.size()) printf("%04d ",v4[id4++]);
        else     printf("     ");
        putchar('\n');
        if(id1==v1.size()&&id2==v2.size()&&id3==v3.size()&&id4==v4.size())    
            break;
    }
}