AcWing 338. 计数问题

题目传送门

1、为什么不能用暴力解?

数据范围太大了,\(0<a,b<100000000\)
两个数字\(a-b\)之间,最多就有\(1^8\)个数字,每个\(10^8\)数,需要遍历每一位,就是一个数字需要遍历8次最多。
那就一次的时间复杂度最高就是:$10^8 * 8 $,而且有多组测试数据,不出意外会TLE。

2、按小学数奥问题分析

如计算 78501 中 "5" 出现的次数。 [答案:41502]
我们可以枚举“5”出现的位置,
1、如当“5”位于倒数第1位时,写成 xxxx5,由于5大于1(当前数位1小于目标值5),前面只能取0~7849(共7850个);

2、如当“5”位于倒数第2位时,写成xxx5x,由于5大于0(当前数位0小于目标值5),前面只能取0~784(共785个),后面无限制为10; 总计:7850个

3、如当“5”位于倒数第3位时,写成xx5xx,由于5等于5(当前数位5等于目标值5),前面取0~77乘以后面无限制的100,共7800个;加上,前面取78,后面取“01”;因为还有"00",所以还需要加上一个1 ,总计:7802个。

4、如当“5”位于倒数第4位时,写成 x5xxx,由于5小于8(当前数位8大于目标值5),前面可取0~7(共8个),后面无限制的1000. 总计:8000个

5、如当“5”位于倒数第5位时,写成 5xxxx,由于5小于7(当前数位7大于目标值5),后面无限制的10000. 总计:10000个
总之,枚举x出现的位置,按x与n在该位上的大小关系,分为大于、小于、等于三类讨论。

加在一起: 7850+7850+7802+8000+10000=41502

ll count_x(ll n, ll x) {
    ll res = 0, tmp = 1;
    ll tmp_n = n;                                                           //n的副本,因为下面是以n为运算的基础,一路除下去的,如果我们想要得到原始的n,就找不到了,这里给它照了一个像
    while (n) {                                                             //从后向前一位一位的讨论
        //代码中注释掉的两行,用于跟踪调试程序的分步运行情况
        //int t = res;
        if (n % 10 < x) res += n / 10 * tmp;                                //小于  n/10代表当前位数前面的数字值,比如785,tmp是指需要乘以10的几次方
        else if (n % 10 == x) res += n / 10 * tmp + (tmp_n % tmp + 1);      //等于  等于最麻烦,需要再次分情况讨论
        else res += (n / 10 + 1) * tmp;                                     //大于  这个加1,是因为是0~77,共78个
        n /= 10;                                                            //进入前一位
        tmp *= 10;                                                          //计算需要乘几个10的变量
        //cout << res - t << endl;
    }
    return res;
}

3、对于0这个东东比较讨厌,需要单独讨论一下

(1)因为0不能当首位
就是上面讨论中提到的什么07,07849 啊,都不能从0开始,那样的话,前面就成了存在前导0了。

(2)在每一位判断时,不存在比0小的数字。
只需要分成两类,不可能存在当前位小于0的情况,只讨论等于和大于。

ll count_0(ll n) {
    ll res = 0, tmp = 1;
    ll tmp_n = n;
    while (n) {
        //代码中注释掉的两行,用于跟踪调试程序的分步运行情况
        //int t = res;
        if (n % 10 == 0) res += (n / 10 - 1) * tmp + (tmp_n % tmp + 1);    //等于,剔除了大于0的情况
        else  res += (n / 10) * tmp;                                       //大于,剔除了大于0的情况

        n /= 10;                                                           //进入前一位
        tmp *= 10;                                                         //计算需要乘几个10的变量
        //cout << res - t << endl;
    }
    return res;
}

4、写一个最笨的计算办法,与用数学方法计算出来的结果进行对比,验证一下思路的正确性

//数位分离之原始版本[笨蛋版本,慢,但绝对准确,用于算法对比判断正确性]
ll stupidCount(int n, int x) {
    ll res = 0;
    for (int i = 1; i <= n; ++i) {
        int tmp = i;
        while (tmp) {
            int t = tmp % 10;
            if (t == x) res++;
            tmp /= 10;
        }
    }
    return res;
}

验证办法:
int n = 78501;
printf("%d ", stupidCount(n, 5));
printf("%d ", stupidCount(n, 0));

5、要的是区间段,我们算的是从1到n,怎么办呢?

现在的题目要求我们求出\([a,b]\)之间 \([0-9]\)出现的次数,这不太好求,如果我们有一个函数,可以计算出\([1-n]\)之间\(x\)出现的次数,就可以使用类似于前缀和的思想,计算出来,比如:
\(f[a,b]=count(b,x)-count(a-1,x)\)

6、测试对拍的程序

 int n = 78501;
printf("%lld ", count_0(n));
for (int i = 1; i <= 9; i++) printf("%lld ", count_x(n, i));

printf("\n");

for (int i = 0; i <= 9; i++)  printf("%lld ", stupidCount(n, i));

//printf("%lld ", count_x(n,5));
//printf("%d ", stupidCount(n, 5));

7、完整C++ 代码

#include <iostream>

using namespace std;
typedef long long ll;

ll count_x(ll n, ll x) {
    ll res = 0, tmp = 1;
    ll tmp_n = n;                                                           //n的副本,因为下面是以n为运算的基础,一路除下去的,如果我们想要得到原始的n,就找不到了,这里给它照了一个像
    while (n) {                                                             //从后向前一位一位的讨论
        //代码中注释掉的两行,用于跟踪调试程序的分步运行情况
        //int t = res;
        if (n % 10 < x) res += n / 10 * tmp;                                //小于  n/10代表当前位数前面的数字值,比如785,tmp是指需要乘以10的几次方
        else if (n % 10 == x) res += n / 10 * tmp + (tmp_n % tmp + 1);      //等于  等于最麻烦,需要再次分情况讨论
        else res += (n / 10 + 1) * tmp;                                     //大于  这个加1,是因为是0~77,共78个
        n /= 10;                                                            //进入前一位
        tmp *= 10;                                                          //计算需要乘几个10的变量
        //cout << res - t << endl;
    }
    return res;
}

/**
对于0,稍作修改,
此时只需分成两类,因为不存在当前为小于0的情况,不过每次的最高为要排除全0的情况。
*/
ll count_0(ll n) {
    ll res = 0, tmp = 1;
    ll tmp_n = n;
    while (n) {
        //代码中注释掉的两行,用于跟踪调试程序的分步运行情况
        //int t = res;
        if (n % 10 == 0) res += (n / 10 - 1) * tmp + (tmp_n % tmp + 1);    //等于,剔除了大于0的情况
        else  res += (n / 10) * tmp;                                       //大于,剔除了大于0的情况

        n /= 10;                                                           //进入前一位
        tmp *= 10;                                                         //计算需要乘几个10的变量
        //cout << res - t << endl;
    }
    return res;
}


int main() {
    int a, b;
    while (cin >> a >> b, a) {
        if (a > b) swap(a, b);
        
        cout << count_0(b) - count_0(a - 1) << ' ';
        
        for (int i = 1; i <= 9; i++)
            cout << count_x(b, i) - count_x(a - 1, i) << ' ';
        cout << endl;
    }
    return 0;
}
上一篇:[Acwing] 字符串哈希 模板


下一篇:python笔记42-http请求命令行工具(httpie)