AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 338. 已经重新推导,但是仍存在输出错误,有待查清楚改正。    原题链接    中等

作者: 作者的头像   奶酪宝宝 ,  2025-06-06 14:56:42 · 山东 ,  所有人可见 ,  阅读 1


0


#include <iostream>
#include <vector>
using namespace std;
//正确基本样例输出
/*
1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247
*/

//WA1:输出
/*
1 1 -1 -1 -1 -1 -1 -1 -1 -1 
0 1 1 1 2 1 1 2 1 2 
0 1 2 1 2 2 1 1 1 1 
0 2 1 1 2 1 1 2 2 1 
1 2 1 2 2 1 1 1 1 1 
1 1 1 2 1 2 1 1 1 1 
1 2 1 1 1 1 1 1 1 2 
0 1 1 1 2 2 1 1 2 1 
0 1 1 1 3 1 1 1 1 2 
1 2 1 1 1 1 2 1 1 2 
*/
//问题在于#1处

//WA2:修改后输出,有负数,且有一部分正确,大多数是错误的。说明算法逻辑有误。
//需要重新细细推导算法。
/*
1 3 1 1 1 1 1 1 1 1 
85 279 279 279 284 190 190 190 189 187 
40 37 37 90 134 80 37 37 37 37 
115 1216 765 765 764 755 755 704 655 656 
-15 -203 -111 -111 -204 -112 -111 -111 -111 -107 
-104 -104 -99 -99 -99 -195 -200 -200 -200 -200 
-412 -1753 -1126 -1126 -1125 -1125 -1125 -1039 -1025 -1034 
-196 -772 -447 -364 -347 -353 -358 -357 -402 -458 
-398 -2255 -1278 -1278 -1283 -1380 -1379 -1375 -1369 -1350 
294 2216 1256 1256 1256 1256 1247 1246 1246 1207 
*/

//WA3:输出错误内容。
/*
10 2 2 2 2 2 2 2 2 2 
140 0 0 0 0 0 0 0 0 0 
20 0 0 0 0 0 0 0 0 0 
60 0 0 0 0 0 0 0 0 0 
-6 0 0 0 0 0 0 0 0 0 
-1054 0 0 0 0 0 0 0 0 0 
-1260 0 0 0 0 0 0 0 0 0 
-1150 0 0 0 0 0 0 0 0 0 
-1250 0 0 0 0 0 0 0 0 0 
198 0 0 0 0 0 0 0 0 0 
*/

//发现是leftBoundary与rightBoundary调用反了
/*  之后输出
11 2 2 2 2 2 2 2 2 2 
185 135 135 135 140 55 55 55 54 54 
40 20 20 73 109 52 20 20 20 20 
115 605 55 55 55 55 55 55 55 55 
-15 -101 -9 -9 -10 -10 -9 -9 -9 -9 
-1104 46 -50 -50 -50 -146 -140 -140 -140 -140 
-1412 -776 -243 -243 -242 -242 -242 -242 -242 -242 
-1196 -263 -46 -46 -46 -47 -47 -46 -91 -136 
-1398 -1024 -148 -148 -153 -239 -238 -238 -238 -238 
294 1056 96 96 96 96 96 96 96 96
*/

const int maxN = 1e8 + 10;
int rangeLeft, rangeRight;
//注意mask的* 10 /10 适配数位的问题
//有问题
int leftBoundaryCounting(int numberRange, int bitNumber, int mask ){
    int sum = 0;
    if (bitNumber == 0){
        sum += 0;
    }
    else{
        int rangeBit = numberRange / (mask / 10);
        if (rangeBit > bitNumber){
            sum += mask / 10;
        }
        else if (rangeBit == bitNumber){
            sum += numberRange % (mask / 10) + 1;
        }
        else{
            sum += mask / 100;
        }
    }
    return sum;
}
//有问题
int rightBoundaryCounting(int numberRange, int bitNumber, int mask ){
    int sum = 0;
    //cout << mask << endl;
    //输出为100,发现left与right调用顺序相反
    if (bitNumber == 0){
        sum += numberRange / mask;//此时mask == 10
    }
    else{
        if (numberRange % mask >= bitNumber){
            sum += numberRange / mask + 1;
        }
        else{
            sum += numberRange / mask;
        }
    }
    return sum;
}
//实现
int normalCounting(int numberRange, int bitNumber, int mask ){
    int sum = 0;
    if (bitNumber == 0){
        sum += (numberRange / mask) * (mask / 10);
        int rangeBit = (numberRange % mask) / (mask / 10);
        if (rangeBit == bitNumber){
            sum += (numberRange % (mask / 10)) + 1;
        }
        else if (rangeBit > bitNumber){
            sum += mask / 10;
        }
        else{
            sum += mask / 100;
        }
    }
    return sum;
}
//无bug
int singleCounting(int numberRange, int bitNumber ){
    int sum = 0;
    if (bitNumber == 0){
        sum += 0;
    }
    else{
        if (numberRange > bitNumber){
            sum += 1;
        }
        else if (numberRange == bitNumber){
            sum += 1;
        }
        else{
            sum += 0;
        }
    }
    return sum;
}
//实现
int countBit(int numberRange, int bitNumber ){
    int mask = 10;
    int sum = 0;
    if (numberRange != 0){//保证退化情况不会被统计
        if (numberRange / mask == 0){//数字范围是单个数字的时候
            sum += singleCounting(numberRange, bitNumber );
        }
        else{
            sum += rightBoundaryCounting(numberRange, bitNumber, mask );
            while (numberRange / mask != 0){
                mask *= 10;
                sum += normalCounting(numberRange, bitNumber, mask );
            }
            sum += leftBoundaryCounting(numberRange, bitNumber, mask );
        }
    }
    return sum;
}

void outputBitCounting(){
    for (int bitNumber = 0; bitNumber < 10; bitNumber ++ ){
        //#1//printf("%d ", countBit(rangeRight, bitNumber ) - countBit(rangeRight - 1, bitNumber ) );
        printf("%d ", countBit(rangeRight, bitNumber ) - countBit(rangeLeft - 1, bitNumber ) );
    }
    printf("\n");
}

void queries(){
    while(cin >> rangeLeft >> rangeRight, rangeLeft || rangeRight){
        outputBitCounting();
    }
}

int main(){
    queries();
    return 0;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息