[PAT解题报告] Counting Ones
不算太难的题,数1-n之间,数字1出现的次数。
我们把n拆开:
(before) d (after)
d是我们要考虑的位,before是前面若干个高位, after是后面若干个低位。
无论d等于多少,前面若干位总是可以从0 变化到(before - 1), 这能包含before * w个1, w实际上是after的位数决定的,例如after有两位,后面可以从00变为99,所以可以乘以100。

特殊情况:
d == 1, 那么当高位变到before的时候 后面可以从0变化到(after + 1),所以答案要加上(after + 1)
d > 1, 可以和之前统一的考虑,高位可以从0变化到before,而不用考虑after。
主要是细节,代码非常短。

代码:
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int n,answer  = 0;
    scanf("%d",&n);
    for (int w = 1, after = 0;n; w *= 10) {
        int before = n / 10;
        if (n % 10 == 1) {
            answer += after + 1;
        }
        after += n % 10 * w;
        answer += (before + ((n % 10 > 1)?1:0)) * w;    
        n = before;
    }
    printf("%d\n",answer);
    return 0;
}
原题链接: http://www.patest.cn/contests/pat-a-practise/1049

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
1 3 评论
分享

全站热榜

正在热议