pat 甲级 1049 Counting Ones

思路是枚举每一位上为1的数的个数，需要对每一位进行分情况讨论。

假设N可以表示成abcdefg，其中每一位代表一个0-9的数字，假如当前枚举到了从大到小的第4为，即d所在的数位，我们对d进行分情况讨论：

1.d =0，即该位等于0，那若想要d位出现1，则受更高位影响。

/*如果百位上的数字为0，则可以知道，百位上可能出现1的次数由更高位决定，比如12013，则可以知道百位出现1的情况可能是11113等情况。*/

则前3位可以选择0 ~ abc - 1 后3位可以选择 0 ~ 999
2.d = 1则分两种情况
 即该位等于0，第一种情况。前3位可以选择0 ~ abc - 1 后3位可以选择0~999
该位等于1，前3位可以选择abc 后3位可以选择0 ~ efg
3.d > 1

前3位可以选择0 ~ abc 后3位可以选择0-999。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
ll calc(int n){
    vector<int> nums;
    while(n){
        nums.push_back(n%10);
        n/=10;
    }
    ll res=0;
    for(int i=nums.size()-1;i>=0;i--){
        int left=0,right=0,pow=1;
        for(int j=nums.size()-1;j>i;j--) left=left*10+nums[j];
        for(int j=i-1;j>=0;j--){
            right=right*10+nums[j]; 
            pow=pow*10;
        }
        int d=nums[i];
        if(d<1) res+=left*pow;
        else if(d==1) res+=left*pow+right+1;
        else res+=(left+1)*pow;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    cout<<calc(n)<<endl;
    return 0;
}

原文地址：https://blog.csdn.net/weixin_50671259/article/details/136242508

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！