# Algorithm Notebook 4

Canonical: https://www.mirstar.net/2026/04/25/alogorithm-notebook-4/
Author: onlymatt
Published: 2026-04-25T08:23:05.000Z
Updated: 2026-10-21T11:21:55.743Z
Categories: Programming, Algorithms
Tags: Algorithm Notes

## P1249最大乘积

题意：给出一个大自然数n，分解为一系列自然数的和，求其最大值。

思路：在纸上手动分解之后会发现，当数小于4时，分解没有意义；当数更大的时候，可以先从2开始慢慢分解，
到分解到无法继续分解，还有剩的时候，可以将剩下的数从最大数往最小的数加上去，加完了还有剩，再从最大的地方加。

```cpp
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN = 1000 + 5;

struct Bigint{
    int len;
    int a[MAXN];

    Bigint(int x = 0){
        memset(a, 0, sizeof(a));
        for (len = 1; x; len++){
            a[len] = x % 10;
            x /= 10;
        }
        len--;
    }
    int &operator[](int i) {return a[i];}

    void flatten(int L){
        len = L;
        for (int i = 1; i <= len; i++){
            a[i + 1] += a[i] / 10;
            a[i] = a[i] % 10;
        }
        while(!a[len])
            len--;
    }

    Bigint operator*(int b) const{
        Bigint c;
        for (int i = 1; i <= len; i++)
            c[i] = a[i] * b;
        c.flatten(len + to_string(b).length());
        return c;
    }

    void print(){
        for (int i = len; i >= 1; i--){
            cout << a[i];
        }
    }
};

int main(){
    int n;
    cin >> n;

    vector <int> q;
    int sum = 0;
    if (n >= 4){ 
        for (int i = 2; i + sum <= n; i++){
            q.push_back(i);
            sum += i;
        }
        int p = q.size() - 1;
        int t = n - sum;
        while (t){
            if (p == -1) p = q.size() - 1;
            q[p]++;
            p--;
            t--;
        }
        for (auto tmp : q) cout << tmp << " ";
        cout << "\n";

        Bigint ans(1);
        for (auto tmp : q){
            ans = ans * tmp;
        }
        ans.print();
    }
    else cout << n;
    return 0;
}
```

总结：

- 1.当看到题没有思路的时候，可以找几个特例，寻找规律
- 2.不需要执着于数学上的最优解与证明，可以先找到一个可行解，之后再优化

坑点：

- 1.当n小于4时，分解没有意义，直接输出n
- 2.有可能会遇到无法分解的情况，剩下的部分要往回加

## Luogu P1045 麦森数

题意：求$2^p - 1$的位数及其前500位

### 总结

---

- 1. 越发觉得细节是很重要的，我们要预见每一行代码的执行会造成什么样的影响
- 1. 一开始使用的是暴力高精度得到位数位最后五百位，最后TLE
- 1. 应该使用的是矩阵快速幂，而高精度也不必保留那么多位，可以只运算最后500位，高位只会影响更高位，与我们无关！

---

细节：

### 1. init函数

```cpp
    void init(int x){
        int index = 1;
        memset(a, 0, sizeof(a));
        while (x){
            a[index++] = x % 10;
            x /= 10;
        }
        len = max(index - 1, 1);
    }
```

一开始直接index=1, len = index--;但是index--是先用后减，这使得init的时候len就加1

### flatten函数

这个也重灾区

```cpp
    void flatten(int l){//不要遮蔽原len
        len = l;
        for (int i = 1; i <= len; i++){
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        len++;
        while(len > 1 &&!a[len])
            len--;
        if (len > 500)
            len = 505;
    }
```

我一开始遮蔽了原len，直接flatten(len)进来，遮蔽了this->len

### 乘法重载搞错

```cpp
    BigInt operator*(const BigInt &other){
        BigInt res;
        res.init(0);
        for (int i = 1; i <= len; i++)
            for (int j = 1; j <= other.len; j++)
                res.a[i + j - 1] += a[i] * other.a[j];
        res.flatten(len + other.len);
        return res;
    }
```

应该是`res.a[i + j - 1] += a[i] * other.a[j]`而不是`res.a[i + j - 1] = a[i] * other.a[j]`。
容易手滑写成=，这样就出现了大问题。

### 完整调试过程记录

本题从最初的暴力写法到最终 AC，经历了 **5 轮迭代**，每一轮暴露的问题都值得记下来。

#### 第 1 轮：暴力 TLE

最初的写法是 `while(n--) res = res * Bg_2`，P 最大 310 万，O(P) 次高精度乘法直接超时。

**→ 改用快速幂**（`quick_pow`），O(log P) 次乘法。

#### 第 2 轮：WA × 5 — 致命细节连环炸

此时编译通过但全 WA，逐一排查：

| 问题 | 位置 | 错误写法 | 正确写法 | 影响 |
| ---- | ---- | ------- | ------- | ---- |
| `len` 算错 | `init` | `len = index--`（后置--，先用后减） | `len = max(index - 1, 1)` | 长度凭空多 1，乘法全错 |
| 参数遮蔽 | `flatten` | `void flatten(int len)` 遮蔽了 `this->len` | 参数改名 `int l`，显式 `this->len = ...` | `len` 永远不更新 |
| 变量名手滑 | `flatten` | `while(!a[l])`（l 是常量） | `while(len > 1 && !a[len])` | 死循环或逻辑错误 |
| 乘法用 `=` | `operator*` | `res.a[i+j-1] = a[i] * other.a[j]` | `res.a[i+j-1] += a[i] * other.a[j]` | 覆盖之前的累加 |
| 位数写错 | `main` | `p * log10(p)` 抄成 P×logP | `p * log10(2)` | 位数输出错误 |
| 输出格式 | `main` | `cnt == 10`（每行 10 个） | `cnt == 50`（每行 50 个） | 格式不匹配 |

#### 第 3 轮：RE — 数组越界

把 `MAXN` 缩小到 550 极限优化后，运行时出现 RE。

根本原因：`res.a[i + j - 1]` 中 `i` 最大 500，`j` 最大 500，`i+j-1` 最大可达 **999**，远超 550。

**→ `MAXN` 需 ≥ 1000**（500 位 × 500 位的中间结果）。

#### 第 4 轮：细节收尾

| 问题 | 位置 | 说明 |
| ---- | ---- | ---- |
| `len = 505` | `flatten` 末尾 | 手滑，应是 `len = 500` |
| 缺少 `#include <algorithm>` | 文件头 | `std::max` 需要此头文件，某些编译器不会隐式引入 |
| `while(!a[len])` 无守卫 | `flatten` | 结果为 0 时 `len` 会减到 0 导致越界，需加 `len > 1 &&` |

#### 第 5 轮：思维层面的反思

这次调试暴露出的根本问题**不在于知识，而在于思维流程**：

> 看到"减 1"就无脑套借位减法模板，完全没想过 $2^P$ 的末位永远是偶数，减 1 根本不需要借位。

**写代码前应该养成三问习惯：**

1. **数据范围有没有可利用的？** → P ≤ 310 万 → 不能用 O(P)，必须快速幂
1. **操作对象有没有特殊性质？** → $2^P$ 末位永远是偶数 → 减 1 不借位
1. **输出有没有边界约束？** → 只要 500 位 → MAXN 只需 1005，且可以截断 len

---

#### 最终修正后的完整代码

```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 1005;

struct BigInt{
    int len;
    int a[MAXN];
    void init(int x){
        int index = 1;
        memset(a, 0, sizeof(a));
        while (x){
            a[index++] = x % 10;
            x /= 10;
        }
        len = max(index - 1, 1);
    }
    int& operator[](int i){ return a[i]; }
    void flatten(int l){
        len = l;
        for (int i = 1; i <= len; i++){
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        len++;
        while (len > 1 && !a[len])
            len--;
        if (len > 500)
            len = 500;
    }
    BigInt operator*(const BigInt &other) const {
        BigInt res;
        res.init(0);
        for (int i = 1; i <= len; i++)
            for (int j = 1; j <= other.len; j++)
                res.a[i + j - 1] += a[i] * other.a[j];
        res.flatten(len + other.len);
        return res;
    }
};

BigInt quick_pow(BigInt base, int exp){
    BigInt res;
    res.init(1);
    while (exp){
        if (exp & 1)
            res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}

int main(){
    int p;
    cin >> p;
    BigInt Bg_2;
    Bg_2.init(2);
    BigInt res = quick_pow(Bg_2, p);
    res.a[1]--;

    // 位数公式：floor(p * log10(2)) + 1
    cout << (int)(p * log10(2)) + 1 << endl;

    int cnt = 0;
    for (int i = 500; i >= 1; i--){
        printf("%d", res[i]);
        cnt++;
        if (cnt == 50 && i > 1){
            printf("\n");
            cnt = 0;
        }
    }
    return 0;
}
```

## Luogu P1923 求第 k 小的数

输入 $n$ 个数字 $a_i$，输出这些数字中第 $k$ 小的数。最小的数是第 $0$ 小。

我们直接将快排的代码改一下就好了。

```cpp
void quick_sort(int l, int r) {
    if (l >= r) return;
    int pivot = a[(l + r) / 2];
    int i = l - 1, j = r + 1;
    int mid; 
    while (i < j) {
        do i++; while (a[i] < pivot);
        do j--; while (a[j] > pivot);
        if (i < j) swap(a[i], a[j]); 
    }
    mid = j;
    quick_sort(l, mid);
    quick_sort(mid + 1, r);
}

void quick_select(int l, int r){
    if (l >= r) return;
    int pivot = a[(l + r) / 2];
    int i = l - 1, j = r + 1;
    while (i < j){
        do i++; while (a[i] < pivot);
        do j--; while (a[j] > pivot);
        if (i < j) swap(a[i], a[j]);
    }
    if (k <= j) quick_select(l, j);
    else quick_select(j + 1, r);
}
```

可以看到就只是改了一下最后的部分，关键在于i,j双指针的理解。

- 排序结束，pivot的位置就是它应该待的位置，设为pos
- pos与i,j的关系可能是，[i,pos,j]、[pos(i),j]、[i,pos(j)]，因此我们不能简单地`quick_select(j + 1, r)`;
- 需要加入if-else判断 `if (k <= j) quick_select(l, j); else quick_select(j + 1, r);`