Algorithm Notebook 4

P1249最大乘积

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

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

#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函数

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函数

这个也重灾区

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

乘法重载搞错

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)，必须快速幂
2. 操作对象有没有特殊性质？ → $2^P$ 末位永远是偶数 → 减 1 不借位
3. 输出有没有边界约束？ → 只要 500 位 → MAXN 只需 1005，且可以截断 len

---

最终修正后的完整代码

#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$ 小。

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

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);