grant's Blog

记录生活中的点点滴滴

算法基础课笔记（二七）

发表于 更新于 分类于 ，   阅读次数： Valine：
本文字数： 4.3k 阅读时长 ≈ 4 分钟

4.6：高精度加法压位

高精度压位参考笔记1： https://www.it610.com/article/1288095829105618944.htm。

高精度压位参考笔记2：https://www.acwing.com/blog/content/2116/。

高精度压位参考资料： https://oi-wiki.org/math/bignum/。（很棒！）

回顾一下高精度加法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// C = A + B，A和B都是正整数
vector<int> add(vector<int> &A,vector<int> &B){
    vector<int> C;
    int t = 0;
    for (int i = 0;i < A.size() || i < B.size();i++){
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;// 进位到下一位
    }
    if (t) C.push_back(1);// 判断最高位是否需要进位
    return C;
}

int main(){
    string a,b;
    vector<int> A,B;

    cin >> a >> b;
    for (int i = a.size()-1;i >= 0;i--) A.push_back(a[i] - '0');
    for (int i = b.size()-1;i >= 0;i--) B.push_back(b[i] - '0');

    auto C = add(A,B);
    for (int i = C.size()-1;i >= 0;i--) printf("%d",C[i]);

    return 0;
}

什么是压位？

int型可以存9位数字，而高精度加法代码在数组的每个元素中只存了0-9中的一位数，可以说浪费了很多空间，而且计算机计算4+5和3333+4444用的时间是相同的，所以我们有时候用压位来节省空间和时间。

压8位：上面的代码中，数组里每一个数存0~9，压8位就是每个数存0~99999999。这样数组长度会缩小到八分之一。压9位类似。

例如计算8192*42时，如果按照高精度乘高精度的计算方式，我们实际上算的是(8000+100+90+2)*(40+2)。

还是以上面这个例子为例，如果我们每两位拆分一个数（也就是压2位），我们可以拆分成(8100+92)*42。

从 进位制 的角度理解这一过程，我们通过在较大的进位制（上面每两位拆分一个数，可以认为是在 100进制下进行运算）下进行运算，从而达到减少参与运算的数字的位数，提升运算效率的目的。

高精度加法压位代码：手动模拟样例会更容易理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
压位算法相较于普通的高精度算法主要区别在于进制数(压几位就模十的几次方), 和储存(见代码)
1.模数不同
vector<int> add (vector<int> &A, vector<int> &B)
{
    vector<int> c;

    int t = 0;
    for(int i = 0 ; i < A.size() || i < B.size() ; i ++ )
    {
        if(i < A.size()) t += A[i];
        if(i < B.size()) t += B[i];
        c.push_back(t % mod); // ***
        t /= mod; // ***压九位数mod = 10^9
    }

    if(t) c.push_back(1);

    return c;
}

2.存储方式不同
for(int i = a.size() - 1, sum = 0, j = 0, t = 1 ; ~i ; i -- )
{
    sum += (a[i] - '0') * t; // sum表示数的和，j表示压的位数
    j ++ , t *= 10;
    if(j == 9 || i == 0) // 九位一个元素
    {
        A.push_back(sum);
        sum = j = 0; // 存下一个数，重新设置参数
        t = 1;
    }
}
for(int i = b.size() - 1, sum = 0, j = 0, t = 1 ; ~i ; i -- ) 
{
    sum += (b[i] - '0') * t;
    j ++ , t *= 10;
    if(j == 9 || i == 0)
    {
        B.push_back(sum);
        sum = j = 0;
        t = 1;
    }
}

3.输出方式不同
printf("%d", c.back()); // 第一个元素不需要补前导零
for(int i = c.size() - 2 ; ~i ; i -- ) printf("%09d", c[i]);

仔细体会压位过程，会发现很巧妙。

4.7：数位统计DP

例题：338. 计数问题（模板题）

从这题开始的后面几题都有难度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。
例如，a=1024，b=1032，则 a 和 b 之间共有 9 个数如下：
1024 1025 1026 1027 1028 1029 1030 1031 1032
其中 0 出现 10 次，1 出现 10 次，2 出现 7 次，3 出现 3 次等等…

输入格式
输入包含多组测试数据。
每组测试数据占一行，包含两个整数 a 和 b。
当读入一行为 0 0 时，表示输入终止，且该行不作处理。

输出格式
每组数据输出一个结果，每个结果占一行。
每个结果包含十个用空格隔开的数字，第一个数字表示 0 出现的次数，第二个数字表示 1 出现的次数，以此类推。

数据范围
0<a,b<100000000
输入样例：
1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0
输出样例：
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

本题有难度！数位统计DP细节很多，比较麻烦。（先看提高课数位专题会清楚一点）

分情况讨论很重要！注意处理前导零！

image-20210910223602956

参考题解： https://www.acwing.com/solution/content/52109/。

本题的关键在与理解count函数的原理。

不妨设n=abcdefgh。

首先我们要计算count(n,i)。

对照count函数模拟一遍计算过程：

进入函数，res = 0，dgt = 8；

进入for循环，从左往右（高位—>低位）取出n中的每一位数字；

…

当j = 3时，看看第3位数字为i共有多少个数，第3位数的权为p = 10^(8-3)，第3位左边的数l = n / 10^6，第3位右边的数为r = n % 10^5，第3位数字为dj = n / 10^5 % 10。（n/p得到的是第j位及它左边的数，n%p得到的是第j位它右边的数）

…

  • 情况1：当xx = 00~ab-1时，

    • 当i不等于0时，defgh可以取00000~99999，方案数是：l*p;
    • 当i等于0时，要处理前导零，左边xx第一个x不能取0，方案数是：(l-1)*p。

  • 情况2：当xx = ab时，

    • 情况2.1：当i = dj时，defgh可以取0~r，方案数是：r+1；
    • 情况2.2：当i < dj时，defgh可以取00000~99999，方案数是：p。

把所有情况的方案数加起来就是count(n,i)的值了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define IOS \
    ios::sync_with_stdio(false); \
    cin.tie(0); \
    cout.tie(0)

int get(int n){ // 计算n一共有多少位数字
    int res = 0;
    while (n){
        res ++;
        n /= 10;
    }
    return res;
}

int count(int n,int i){
    int res = 0,dgt = get(n);

    for (int j = 1;j <= dgt;j ++){ // 从高位到低位（从左往右）枚举每一位数字
        // p表示第j位上的权，l表示第j位左边的数，r表示第j位右边的数，dj表示第j位上的数字
        int p = pow(10,dgt - j),l = n / p / 10,r = n % p,dj = n / p % 10;
        /* 情况1：
            若i != 0，方案数为：i*p；
            若i == 0，需要处理前导零，第一位数字不能为0，方案数为：(i-1)*p；
         */   
        if (i) res += l*p;
        else res += (l-1)*p;
        /* 情况2：
            若i == dj，方案数为：r + 1：
            若i < dj，方案数为：p。
        */
        if (i == dj) res += r + 1;
        if (i < dj) res += p;
    }
    return res; // 不要写在循环里面了
}

int main(){
    IOS;
    
    int a,b;
    while (cin >> a >> b,a){
        if (a > b) swap(a,b);
        for (int i = 0;i <= 9;i ++)
            cout << count(b,i) - count(a-1,i) << ' ';
        cout << '\n';
    }

    return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！