六道算法题完整题解与 C++17 参考实现

本册按题目出现顺序整理，包含题意、思路、正确性说明、易错点、复杂度、样例和完整可提交代码。

题目总览

1. 猫狗分类统计

算法定位： 直接计数。统计模型判断为猫的图片数。

题意与数据范围

100 张图片中有 60 张真实猫图、40 张真实狗图。8 张猫图被误判为狗，5 张狗图被误判为猫，其余判断均正确。无输入，输出模型判为猫的图片总数。

核心观察与算法推导

1. 真正的猫图中，有 60 − 8 = 52 张被判为猫；真正的狗图中，有 5 张被错误判为猫。

2. 因此答案是 52 + 5 = 57。这道题是固定数据的输出题，不需要读取标准输入。

正确性说明

按真实类别将所有被预测为猫的图片分成“正确预测的猫”与“误判为猫的狗”两类，两类互不重叠且覆盖全部情况，故求和正确。

易错点与复杂度

题目问的是“预测为猫”的数量，不是“真正为猫”的数量，也不是正确分类总数。

复杂度： 时间 O（1），额外空间 O（1）。

样例输入

（无输入）

样例输出

57

C++17 完整代码

#include <iostream>
using namespace std;

int main() {
    cout << 60 - 8 + 5 << '\n';
    return 0;
}

2. 三机器人最小距离和

算法定位： 排序与贪心。至多移动一台机器人 K 个单位。

题意与数据范围

有三台位于一维整数坐标 A、B、C 的机器人。可以只移动其中一台，不移动或向任意方向移动不超过 K 个单位；要求移动后两两距离之和最小。共有 Q 组测试，坐标与 K 均不超过 10⁹。

核心观察与算法推导

1. 将三个坐标排序成 x ≤ y ≤ z。两两距离之和为 （y−x）+（z−y）+（z−x），也就是 2（z−x）。所以只需缩小最左端与最右端的跨度。

2. 移动中间的机器人无法降低最值跨度。若移动左端向右，最小跨度为 max（z−x−K， z−y）;若移动右端向左，最小跨度为 max（z−x−K， y−x）。

3. 两者取最小，最终答案为 2 × max（z−x−K， min（y−x， z−y））。

正确性说明

最值跨度至多降低 K，且只移动一台机器人的条件下，至少有原来的一对中间点与未移动端点被保留，其跨度下界为 min（y−x，z−y）。移动对应极值机器人至恰当位置，可以达到两种下界中的较大者，故公式最优。

易错点与复杂度

坐标可能相同；K 可以超过跨度。注意三点两两距离之和是最值跨度的两倍，并使用 long long。

复杂度： 每组只对 3 个数排序：时间 O（1），额外空间 O（1）;全部为 O（Q）。

样例输入

3
0 4 10 3
0 4 10 10
2 2 2 5

样例输出

14
8
0

C++17 完整代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q;
    cin >> Q;
    while (Q--) {
        ll a[3], K;
        cin >> a[0] >> a[1] >> a[2] >> K;
        sort(a, a + 3);

        ll x = a[0], y = a[1], z = a[2];
        ll span = max(z - x - K, min(y - x, z - y));
        cout << 2 * span << '\n';
    }
    return 0;
}

3. 排列平均分组

算法定位： 质因数分解与二分答案。寻找使 N！被 B 的 E 次幂整除的最小 n。

题意与数据范围

选取 n 张互不相同的图片，可生成 n！种排列。要求将全部排列等分为 B^E 个非空组，其中 B ≥ 2、E ≥ 1，求最小正整数 n。Q ≤ 2000，B， E ≤ 10⁹。

核心观察与算法推导

1. 平均分组且每组非空，等价于 n!可以被 B^E 整除。B^E 不应直接计算，因为它可能远超 64 位范围。

2. 对 B 做质因数分解：若质因子 p 在 B 中出现 a 次，则在 B^E 中至少 a×E 次。

3. 勒让德公式给出 p 在 n！中的指数：floor（n/p）+floor（n/p²）+...;代码以反复执行 n /= p 累加的方式安全实现。

4. 指数随 n 单调不减，可以对每个质因子二分最小 n，取所有结果的最大值。B×E 一定是合法上界，因为 （B×E）！至少包含 E 个 B 的倍数。

正确性说明

n!被 B^E 整除，当且仅当每个质因子 p 的出现次数不少于对应需求 aE。每个条件关于 n 均单调，因此二分找到各条件的最小满足值；全部条件同时成立的最小 n 正是这些最小值的最大者。

易错点与复杂度

不要直接构造 B^E 或 n！;指数 a×E、上界 B×E 要用 long long。若分解结束仍有大于 1 的剩余因子，它也是质因子。

复杂度： 每组分解 O（√B）;设 B 有 t 个不同质因子，二分约 O（t·log（BE）·log₂（BE））;空间 O（t）。

样例输入

4
12 1
12 2
7 2
2 3

样例输出

4
6
14
4

C++17 完整代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll exponentInFactorial(ll n, ll p) {
    ll count = 0;
    while (n > 0) {
        n /= p;
        count += n;
    }
    return count;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q;
    cin >> Q;
    while (Q--) {
        ll B, E;
        cin >> B >> E;
        ll rest = B;
        vector<pair<ll, ll>> factors;

        for (ll p = 2; p * p <= rest; ++p) {
            if (rest % p != 0) continue;
            ll a = 0;
            while (rest % p == 0) {
                rest /= p;
                ++a;
            }
            factors.push_back({p, a});
        }
        if (rest > 1) factors.push_back({rest, 1});

        ll answer = 0;
        for (auto [p, a] : factors) {
            ll need = a * E;
            ll lo = 1, hi = B * E;
            while (lo < hi) {
                ll mid = lo + (hi - lo) / 2;
                if (exponentInFactorial(mid, p) >= need)
                    hi = mid;
                else
                    lo = mid + 1;
            }
            answer = max(answer, lo);
        }
        cout << answer << '\n';
    }
    return 0;
}

4. 图片抽查

算法定位： 三维含义二维实现的背包 DP。恰好选择 M 个非空文件夹且共取 K 张。

题意与数据范围

N 个文件夹中第 i 个有 Ai 张已排序且互不相同的图片。可从每个文件夹取出前 t 张，0 ≤ t ≤ Ai。要求总共取出 K 张，且恰好 M 个文件夹取了至少 1 张，求方案数对 998244353 取模。N ≤ 60，K ≤ 2000。

核心观察与算法推导

1. 定义 dp[j][k]：处理过的文件夹中，恰好有 j 个非空、共取 k 张的方案数。初始 dp[0][0] = 1。

2. 当前文件夹取 0 张，贡献原 dp[j][k];取 t 张（1 ≤ t ≤ Ai），贡献 dp[j−1][k−t]。

3. 因此 new[j][k] = dp[j][k] + sum（dp[j−1][k−t]）。后一项是连续下标区间和，可用滑动窗口在 O(1) 时间维护，避免再枚举 t。

4. 窗口随 k 前移时，加入 dp[j−1][k−1]，如果 k−Ai−1 ≥ 0，再移除 dp[j−1][k−Ai−1]。

正确性说明

每种方案按当前文件夹是否取图唯一划分成两种情况；取正数 t 时，之前必定恰好使用 j−1 个文件夹及 k−t 张图片。转移不重不漏。滑动窗口仅改变求和实现方式，不改变所求区间和。

易错点与复杂度

“取前 t 张”在给定 t 后只有一种选择，不需要组合数。取 0 张不计入 M。特别注意 M=0、K=0、Ai=0 的边界。

复杂度： 时间 O（NMK），空间 O（MK）。

样例输入

3 2 3
1 2 3

样例输出

4

C++17 完整代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;
    vector<int> A(N);
    for (int &x : A) cin >> x;

    vector<vector<ll>> dp(M + 1, vector<ll>(K + 1, 0));
    dp[0][0] = 1;

    for (int i = 0; i < N; ++i) {
        auto next = dp;  // 当前文件夹取 0 张
        for (int j = 1; j <= min(M, i + 1); ++j) {
            ll window = 0;
            for (int k = 0; k <= K; ++k) {
                if (k >= 1) window += dp[j - 1][k - 1];
                if (k - A[i] - 1 >= 0)
                    window -= dp[j - 1][k - A[i] - 1];

                window = (window % MOD + MOD) % MOD;
                next[j][k] = (dp[j][k] + window) % MOD;
            }
        }
        dp.swap(next);
    }

    cout << dp[M][K] << '\n';
    return 0;
}

5. 连续 N 天解题安排

算法定位： 子集和计数与同余类前缀和。每一天比前一天多 1 道或 K 道。

题意与数据范围

连续 N 天安排题目，第一天至少 1 道，此后每天比前一天恰好多 1 道或多 K 道。对于 Q 个 S，统计总题数为 S 的不同安排数，模 998244353。N ≤ 400，K ≤ 10⁹，Q ≤ 10⁵，S ≤ 10¹⁸。

核心观察与算法推导

1. 最小安排为 1,2,...,N，总题数 base = N（N+1）/2。若首日增加 x 道，则总数额外增加 Nx。

2. 把第 i 次增量由 1 改为 K，会令余下 N−i 天各多 K−1 道。所有“改为 K”的选择，因此对应集合 {1,2,...,N−1} 的一个子集，其元素和记为 w。

3. 令 T = S−base，问题转化为数有多少个子集和 w 满足 T = Nx + （K−1）w，x 为非负整数。先用 01 背包求 dp[w]（每种子集各计一次）。

4. 可行 w 同时需满足 （K−1）w ≡ T （mod N） 与 w ≤ T/（K−1）。设 d=gcd（K−1，N）、period=N/d，则满足条件的 w 属于 period 意义下的唯一余数类，或根本不存在。

5. 对每个 w mod period 建前缀和，并预处理从 T mod N 到余数类的映射。查询时只需取该类中不大于上界的前缀和。

正确性说明

从首日题数及 N−1 个“选 1 或 K”的增量，可唯一确定一份安排；反之，每份安排对应唯一的 x 与子集。公式建立双射。01 背包统计每个子集和的方案数，同余映射筛去无法使 x 为整数的子集，上界筛去 x 为负的子集，故前缀和恰好给出答案。

易错点与复杂度

题目是每天“多 1 或多 K”，不是“多 1 至 K 中任意数”。K−1 为正;S 最高 10¹⁸，必须使用 long long。N=1 时每个 S≥1 恰有一种方案，程序也自然支持。

复杂度： 背包预处理 O（N³），同余前缀 O（N²），每次查询 O（1），总空间 O（N²）。实际最大子集和仅 N（N−1）/2 ≤ 79800。

样例输入

3 3 6
6
7
8
10
12
18

样例输出

1
0
1
1
2
2

C++17 完整代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    ll K;
    cin >> N >> K >> Q;

    int W = N * (N - 1) / 2;
    vector<int> dp(W + 1, 0);
    dp[0] = 1;

    int total = 0;
    for (int x = 1; x < N; ++x) {
        for (int s = total; s >= 0; --s) {
            dp[s + x] += dp[s];
            if (dp[s + x] >= MOD) dp[s + x] -= MOD;
        }
        total += x;
    }

    ll base = 1LL * N * (N + 1) / 2;
    ll d = gcd(K - 1, (ll)N);
    int period = N / d;
    vector<vector<int>> pref(period);

    for (int w = 0; w <= W; ++w) {
        int r = w % period;
        int val = dp[w];
        if (!pref[r].empty()) {
            val += pref[r].back();
            if (val >= MOD) val -= MOD;
        }
        pref[r].push_back(val);
    }

    vector<int> residueToClass(N, -1);
    for (int r = 0; r < period; ++r) {
        int residue = ((K - 1) * r) % N;
        residueToClass[residue] = r;
    }

    while (Q--) {
        ll S;
        cin >> S;
        if (S < base) {
            cout << 0 << '\n';
            continue;
        }
        ll T = S - base;
        int r = residueToClass[T % N];
        ll cap = min((ll)W, T / (K - 1));
        if (r == -1 || cap < r) {
            cout << 0 << '\n';
        } else {
            int index = (cap - r) / period;
            cout << pref[r][index] << '\n';
        }
    }
    return 0;
}

6. 相册整理与动态替换

算法定位： 三状态 DP 与 Min Plus 线段树。动态修改类型与分数后求最小删除损失。

题意与数据范围

长度 N 的相册由 A（写实）、B（卡通）、S（过渡）组成，第 i 张图片删除代价为 Ci。删除后剩余相对顺序不变，且不能存在相邻的 AB 或 BA。每次把位置 P 替换为类型 X、分数 W，保留修改，输出此时最小删除损失。N、Q ≤ 5×10⁴，Ci、W ≤ 10⁹。

核心观察与算法推导

1. 不能只覆盖原串中相邻的 AB/BA：删除一张图后，原来不相邻的 A 与 B 可能重新相邻。动态规划应跟踪“最后一张实际保留的图片”类型。

2. 设状态 0、1、2 分别代表最后保留 A、B、S;把尚未保留任何图片视作状态 S。处理一张类型 X、分数 W 的图片时，可以删除它（原状态不变，代价 W），或在不造成 AB/BA 的前提下保留它（新状态为 X，代价 0）。

3. 每张图片对应 3×3 的转移矩阵。将矩阵乘法改为 Min-Plus：C[i][j] = min（A[i][k]+B[k][j]）。区间的转移等于该区间各矩阵的有序 Min-Plus 乘积。

4. 线段树每个叶子存一张图片的矩阵，内部节点维护左右儿子矩阵的乘积。替换仅修改一个叶子，向上重算 O（log N） 个节点。根矩阵第 2 行的最小值是答案。

正确性说明

三状态 DP 根据最后一张保留图片的类型判断当前保留是否合法，因此删除导致的“新相邻关系”也被准确识别。每一步只在删除、合法保留两种互斥选择中取最小，覆盖所有可能子序列。Min-Plus 矩阵乘法正是这类 DP 转移的结合运算，线段树维护其有序乘积不改变结果。

易错点与复杂度

替换是累计生效的，不是每个询问都从初始相册重新开始。原始位置从 1 开始，代码要转成 0 下标;费用总和可达 5×10¹³，应使用 long long。

复杂度： 建树 O（N）;每次替换 O（log N），根节点读答案 O（1）;空间 O（N）。矩阵大小固定为 3。

样例输入

5 3
ABSAB
5 2 7 4 6
3 A 7
2 S 2
5 S 6

样例输出

8
6
0

C++17 完整代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = (1LL << 60);

struct Matrix {
    ll a[3][3];
    Matrix(bool identity = false) {
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < 3; ++j)
                a[i][j] = (identity && i == j) ? 0 : INF;
    }
};

Matrix multiply(const Matrix &A, const Matrix &B) {
    Matrix C;
    for (int i = 0; i < 3; ++i) {
        for (int k = 0; k < 3; ++k) {
            if (A.a[i][k] == INF) continue;
            for (int j = 0; j < 3; ++j) {
                if (B.a[k][j] == INF) continue;
                C.a[i][j] = min(C.a[i][j],
                                A.a[i][k] + B.a[k][j]);
            }
        }
    }
    return C;
}

int typeOf(char c) {
    if (c == 'A') return 0;
    if (c == 'B') return 1;
    return 2;
}

Matrix makeMatrix(char c, ll cost) {
    Matrix M;
    int t = typeOf(c);
    for (int i = 0; i < 3; ++i) M.a[i][i] = cost;
    for (int i = 0; i < 3; ++i) {
        if ((i == 0 && t == 1) || (i == 1 && t == 0))
            continue;
        M.a[i][t] = 0;
    }
    return M;
}

struct SegmentTree {
    int size;
    vector<Matrix> tree;

    SegmentTree(const string &s, const vector<ll> &c) {
        size = 1;
        while (size < (int)s.size()) size <<= 1;
        tree.assign(size * 2, Matrix(true));
        for (int i = 0; i < (int)s.size(); ++i)
            tree[size + i] = makeMatrix(s[i], c[i]);
        for (int p = size - 1; p >= 1; --p)
            tree[p] = multiply(tree[p * 2], tree[p * 2 + 1]);
    }

    void update(int pos, char c, ll cost) {
        int p = size + pos;
        tree[p] = makeMatrix(c, cost);
        while (p > 1) {
            p /= 2;
            tree[p] = multiply(tree[p * 2], tree[p * 2 + 1]);
        }
    }

    ll answer() const {
        ll ans = INF;
        for (int j = 0; j < 3; ++j)
            ans = min(ans, tree[1].a[2][j]);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    string s;
    cin >> s;
    vector<ll> C(N);
    for (ll &x : C) cin >> x;

    SegmentTree seg(s, C);
    while (Q--) {
        int P;
        char X;
        ll W;
        cin >> P >> X >> W;
        seg.update(P - 1, X, W);
        cout << seg.answer() << '\n';
    }
    return 0;
}