PAT（甲级）1049 Counting Ones (30point(s))

灰太狼 2024-05-08 05:56 7阅读 0赞

##### 题目 #####

[题目链接][Link 1]

##### 思路 #####

题目大意：给出一个数n，找出大小在\[0,n\]中，且含有数字1的数字个数；  
从后往前遍历每一位数字，当前遍历的位置 i 将整个数字分为三部分，i 的左边称为left，右边称为right，位置 i 上的数称为now；  
如果 now = 0，那么左边最大是left - 1，注意从零开始，所以左边有 left 种可能，右边有 a 种可能；  
如果 now = 1，那么左边可以等于left，但是当左边等于left时，右边只有right + 1种可能；  
如果 now >= 2，那么左边可以等于left，有left + 1 种可能；右边有 a 种可能；

##### 代码 #####

#include <iostream>
    #include <string>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        
         int n, a = 1, left, now, right;
         int ans = 0;
         scanf("%d", &n);
         while(n / a != 0){
        
              left = n / (a * 10);
              now = n / a % 10;
              right = n % a;
              if(now == 0) ans += left * a;//如果当前位是0，那么左边的数只能小于left，不能等于left
              else if(now == 1) ans += left * a + right + 1;//如果当前位是1，那么左边数可以等于left，但右边数要小于等于right
              else ans += (left + 1) * a;
              a *= 10;
         }
         printf("%d\n", ans);
         system("pause");
         return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805430595731456

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT（甲级）1111 Online Map (30point(s)) 最短路算法

题目题目链接思路题目大意：给一张图，注意有的边是有向的，有的是无向的；分别找出从起点到终点最短路径和最快路径；如果两个路径相同，只输出一次；首先来看题的要求，需要输出路径...

布满荆棘的人生/ 2024年05月08日 06:03/ 0 赞/ 7 阅读

相关 PAT（甲级）1021 Deepest Root (25point(s))

题目题目链接思路题目大意：给一张图，这个图有点特殊，没有环且边数等于节点数-1，即是一棵树；每个节点都可能是根节点，要求是输出那些作为根节点时树的深度最大的节点；首先要判...

桃扇骨/ 2024年05月08日 06:01/ 0 赞/ 10 阅读

相关 PAT（甲级）1078 Hashing (25point(s))

题目题目链接思路先判断原题hash位置有没有被占用，如果被占用，就进行二次平方探查；代码#include <iostream>#include <str...

阳光穿透心脏的1/2处/ 2024年05月08日 05:59/ 0 赞/ 7 阅读

相关 PAT（甲级）1049 Counting Ones (30point(s))

题目题目链接思路题目大意：给出一个数n，找出大小在[0,n]中，且含有数字1的数字个数；从后往前遍历每一位数字，当前遍历的位置 i 将整个数字分为三部分，i 的左边称为l...

灰太狼/ 2024年05月08日 05:56/ 0 赞/ 8 阅读

相关 PAT（甲级）1008 Elevator (20point(s))

题目题目链接思路每次和上次的楼层比较一下，判断是上楼还是下楼；代码#include <iostream>using namespace std;int mai...

爱被打了一巴掌/ 2024年05月08日 05:55/ 0 赞/ 10 阅读

相关 PAT 甲级 1004 Counting Leaves (30 分) 遍历树求解

1.题目翻译输入：每个输入文件包含一个测试用例。每种情况都从包含0 <N <100（树中的节点数）和M（<N）（非叶节点数）的行开始。然后是M行，每行的格式为：

ゝ一世哀愁。/ 2023年08月17日 16:27/ 0 赞/ 65 阅读

相关 Python实现Pat 1049. Counting Ones (30)

[题目][Link 1] The task is simple: given any positive integer N, you are supposed to co

清疚/ 2022年06月04日 08:45/ 0 赞/ 120 阅读

相关 1049. Counting Ones (30)

The task is simple: given any positive integer N, you are supposed to count the total nu

朴灿烈づ我的快乐病毒、/ 2022年05月31日 12:42/ 0 赞/ 175 阅读

相关 PAT甲级 - 1004 Counting Leaves （30 分）

题目链接：[（PAT甲级）1004 Counting Leaves （30 分）][PAT_1004 Counting Leaves _30] A family hierar

迷南。/ 2022年03月19日 16:29/ 0 赞/ 130 阅读

相关 PAT1049. Counting Ones (30)(数学)

题意：给出一个n，求从0到n一共出现几个1 思路：这题还是有点复杂的，看了一下别人的代码，基本思路是一位一位考虑，也就是计算这一位为1的数有几个，用now表示当前位的

朴灿烈づ我的快乐病毒、/ 2021年12月20日 23:11/ 0 赞/ 160 阅读