第 06 周的 18 道题里,重复出现的是四种骨架:小根堆每次取最小、排序后按区间分情况、布尔数组做 01 背包、以及“枚举到某个位置时顺手更新答案”的线性 DP。

小根堆与分情况:口罩、春游

小红的口罩有 n 个口罩,第 i 个的不舒适度是 a[i]。每次选当前不舒适度最小的戴上,戴过之后该口罩的不舒适度翻倍;累计不舒适度超过 k 时停止,问最多能戴几次。

每次都要取最小值,用小根堆。取出堆顶、累加、把 2t 放回去,计数加一;一旦累加值超过 k,最后这次不算,输出 cnt - 1。

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    long long k;
    cin >> n >> k;
    priority_queue<long long, vector<long long>, greater<long long>> heap;
    for (int i = 0; i < n; ++i)
    {
        long long x;
        cin >> x;
        heap.push(x);
    }
 
    long long sum = 0;
    int cnt = 0;
    while (true)
    {
        long long t = heap.top();
        heap.pop();
        sum += t;
        ++cnt;
        heap.push(t * 2);
        if (sum > k) { cout << cnt - 1 << '\n'; break; }
    }
    return 0;
}

t * 2 用 long long,避免不舒适度接近 10^9 时翻倍溢出。堆里始终有 n 个元素;每个元素会随着被选中反复翻倍,翻倍次数与 log k 同阶,整体时间 O(n log k · log n)。

春游有 n 个人,双人船每条 a 元,三人船每条 b 元,船必须整条租,求最小花费。

先比较单价:a / 2 与 b / 3,等价于 3a < 2b 时双人船更划算。余下 0、1、2 个人时,不能只看一种船,还要考虑“把一条已租的船换成另一种”的差价。

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
 
LL solve(LL n, LL a, LL b)
{
    if (n <= 2) return min(a, b);          // 一条船就能装下
    LL ret = 0;
    if (3 * a < 2 * b)                     // 双人船更便宜
    {
        ret += n / 2 * a;
        n %= 2;
        if (n) ret += min(min(a, b), b - a);
        // 剩 1 人:再租双人船 a、直接租三人船 b,或把一条双人船换成三人船,补 b-a
    }
    else                                   // 三人船更便宜
    {
        ret += n / 3 * b;
        n %= 3;
        if (n == 1) ret += min(min(a, b), 2 * a - b);
        // 剩 1 人:单人船、三人船,或把一条三人船换成两条双人船,补 2a-b
        if (n == 2) ret += min(min(a, b), 3 * a - b);
        // 剩 2 人:双人船、三人船,或把一条三人船换成三条双人船,补 3a-b
    }
    return ret;
}
 
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        LL n, a, b;
        cin >> n >> a >> b;
        cout << solve(n, a, b) << '\n';
    }
    return 0;
}

n <= 2 时直接取 min(a, b):三个人以内的船价可以互换,租哪种都合法。时间 O(1),乘法用 long long,避免 3 * a 在 32 位里溢出。

布尔背包:数位染色

数位染色给一个正整数,把每一位染成红或蓝,问能否让两种颜色对应的数字之和相等。

所有数位之和为奇数时不可能相等。否则目标是把数位之和的一半凑出来,每个数位只能用一次,是标准的 01 背包,只是价值维度换成“能不能”。

#include <iostream>
using namespace std;
 
int main()
{
    long long x;
    cin >> x;
    int a[20], n = 0, sum = 0;
    while (x > 0)
    {
        a[n++] = x % 10;
        sum += x % 10;
        x /= 10;
    }
 
    if (sum % 2) { cout << "No\n"; return 0; }
    int target = sum / 2;
    bool dp[200] = {false};
    dp[0] = true;
    for (int i = 0; i < n; ++i)
        for (int j = target; j >= a[i]; --j)
            dp[j] = dp[j] || dp[j - a[i]];
 
    cout << (dp[target] ? "Yes" : "No") << '\n';
    return 0;
}

数位最多 19 个、每位最大 9,目标和不超过 85,布尔表很小。j 逆序保证同一个数位不会被选两次。时间复杂度 O(位数 × 目标和)。

三个模拟:回文构造、ISBN 校验、逆序去重

素数回文给一个数字串,把它补成回文(末尾接上前面数字的逆序,去掉原末位),判断这个回文数是不是素数。

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
typedef long long LL;
 
LL make(string s)
{
    for (int i = (int)s.size() - 2; i >= 0; --i) s += s[i];
    return stoll(s);
}
 
bool isPrime(LL x)
{
    if (x < 2) return false;
    for (LL i = 2; i * i <= x; ++i)
        if (x % i == 0) return false;
    return true;
}
 
int main()
{
    string s;
    cin >> s;
    cout << (isPrime(make(s)) ? "prime" : "noprime") << '\n';
    return 0;
}

拼接后的长度约为输入的两倍。stoll / Long.parseLong 只能装 18~19 位,输入位数一多就会溢出;这题的数据范围让它能过,但不要把这段当成通用模板。判断素数只需试除到 sqrt(x)。

ISBN 号码形如 0-670-82162-4,前 9 个数字依次乘 1 到 9,求和后对 11 取模;余数 10 记作 X。校验位正确输出 Right,否则把末位改成正确值再输出。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    int sum = 0, w = 1;
    for (int i = 0; i + 1 < (int)s.size(); ++i)
        if (s[i] >= '0' && s[i] <= '9')
        {
            sum += (s[i] - '0') * w;
            ++w;
        }
    sum %= 11;
 
    char need = (sum == 10 ? 'X' : char('0' + sum));
    if (s.back() == need) cout << "Right\n";
    else
    {
        s.back() = need;
        cout << s << '\n';
    }
    return 0;
}

权重只加在数字字符上,遇到 - 跳过。比较时统一先算出“应该是什么字符”,X 和数字两种情况就合并了。时间 O(长度)。

提取不重复的整数把一个数从右往左读,第一次出现的数字输出,之后再出现就跳过。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    bool seen[10] = {false};
    for (int i = (int)s.size() - 1; i >= 0; --i)
    {
        int d = s[i] - '0';
        if (!seen[d]) { cout << d; seen[d] = true; }
    }
    cout << '\n';
    return 0;
}

用 10 个布尔值代替哈希表,时间和空间都是 O(位数)。

区间贪心:活动安排

活动安排给 n 个区间 [a[i], b[i]),求最多能选多少个两两不重叠的活动。

按左端点排序。维护当前这一“组”里最小的右端点 r:下一个区间的左端点小于 r 就有重叠,把 r 收紧成两者右端点的较小值;否则说明上一组已经结束,答案加一并开始新的一组。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> seg(n);
    for (auto& p : seg) cin >> p.first >> p.second;
    sort(seg.begin(), seg.end());
 
    int ret = 1, r = seg[0].second;
    for (int i = 1; i < n; ++i)
    {
        if (seg[i].first < r) r = min(r, seg[i].second);   // 重叠,收紧右端
        else { ++ret; r = seg[i].second; }                 // 断开,开始新组
    }
    cout << ret << '\n';
    return 0;
}

为什么收紧右端而不是保留原来的 r:同一组里最早结束的那个区间,才是给后面留空间最多的选择。相邻两组被计数时,第二组的左端点不小于第一组的最小右端点,所以两组选出的区间互不重叠,答案不会虚高。另一种等价写法是按右端点排序,每次选结束最早的区间;这里按左端点扫,则是在每一组内部收紧最小右端。复杂度 O(n log n)。

课件的 Java 比较器写成 a[0] <= b[0] ? -1 : 1。当两个左端点相等时,compare(a,b) 和 compare(b,a) 都返回 -1,违反比较器的反对称性,Arrays.sort 在数据量大时可能抛出 IllegalArgumentException。改成 Integer.compare(a[0], b[0])。

线性 DP:合唱团、编辑距离、abb

合唱团从 n 个人里按顺序选 k 个,要求相邻两人的位置差不超过 d,求最大乘积。能力值可能为负,所以最大值和最小值要一起维护。

f[i][j] 表示以 i 结尾、选了 j 个人时的最大乘积,g[i][j] 表示最小乘积。上一个人只能来自 [i-d, i-1],且至少要有 j-1 个人。

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
 
const int N = 1010, K = 15;
const LL INF = (LL)4e18;
int n, k, d, a[N];
LL f[N][K], g[N][K];
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> k >> d;
 
    for (int i = 1; i <= n; ++i)
    {
        f[i][1] = g[i][1] = a[i];
        for (int j = 2; j <= min(i, k); ++j)
        {
            f[i][j] = -INF;
            g[i][j] = INF;
            for (int p = max(i - d, j - 1); p < i; ++p)
            {
                f[i][j] = max(f[i][j], max(f[p][j - 1] * a[i], g[p][j - 1] * a[i]));
                g[i][j] = min(g[i][j], min(f[p][j - 1] * a[i], g[p][j - 1] * a[i]));
            }
        }
    }
 
    LL ans = -INF;
    for (int i = k; i <= n; ++i) ans = max(ans, f[i][k]);
    cout << ans << '\n';
    return 0;
}

负负得正,所以最大乘积既可能来自上一个最大值,也可能来自上一个最小值,转移里两项都要算。p 从 j-1 起,保证前面至少放过 j-1 个人。n ≤ 1000、k ≤ 10、能力值 ±50,乘积最大约 50^10 ≈ 9.8 × 10^16,64 位整数装得下。时间 O(n·k·d),空间 O(n·k)。

课件的 Java 版注释了 0x3f3f3f3f3f3f3f3f 并标注“报错”。Java 的整数字面量默认按 32 位解析,这个值超出 int,必须写成 0x3f3f3f3f3f3f3f3fL,或者像课件那样改用 Long.MIN_VALUE。

编辑距离给两个字符串,求把 a 改成 b 的最少操作数,允许插入、删除、替换。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
const int N = 1010;
int dp[N][N];
 
int main()
{
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
 
    for (int j = 0; j <= m; ++j) dp[0][j] = j;   // 空串插入 j 个
    for (int i = 0; i <= n; ++i) dp[i][0] = i;   // 删掉 i 个
 
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
        }
 
    cout << dp[n][m] << '\n';
    return 0;
}

字符相同就不用操作,直接继承左上角;不同时,删除对应上方、插入对应左方、替换对应左上角,三者取最小加一。时间 O(nm),空间 O(nm);只保留相邻两行可以压到 O(m)。

abb统计满足“长度为 3、后两位相同、前两位不同”的子序列个数。

按子序列的第二个 b 结算。设 g[c] 是字符 c 已经出现的次数,f[c] 是形如“某个不等于 c 的字符在前、c 在后”的二元组个数。扫描到位置 i 的字符 c 时,f[c] 里的每个二元组都能和当前这个 c 组成 abb,答案累加 f[c];随后把当前 c 作为新的“后一个字符”补进 f[c]。

#include <iostream>
using namespace std;
typedef long long LL;
 
const int N = 1e5 + 10;
char s[N];
 
int main()
{
    int n;
    cin >> n >> s;
    LL f[26] = {0}, g[26] = {0}, ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int c = s[i] - 'a';
        ans += f[c];                 // 结算:以当前 c 作为第二个 b
        f[c] += i - g[c];            // 前面不等于 c 的位置,都能和当前 c 配对
        ++g[c];
    }
    cout << ans << '\n';
    return 0;
}

i - g[c] 就是前 i 个位置里与 c 不同的字符个数,因为 i 是当前位置之前的元素总数。结算必须写在更新之前,否则当前字符会和自己配对。时间 O(n),空间是 26 个计数。

滑动窗口、全排列与 2^k-1

跳台阶扩展问题的青蛙一次可以跳 1 到 n 级,求跳上 n 级的方法数。把每一步的“落脚点”看作 1..n-1 的一个子集:选了哪些中间台阶,就确定了整条跳法,因此答案是 2^(n-1)。

#include <iostream>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    cout << (1 << (n - 1)) << '\n';
    return 0;
}

题面 n ≤ 20,1 << 19 在 int 范围内;n 更大时要换成 1LL << (n - 1)。

包含不超过两种字符的最长子串用滑动窗口,窗口内维护每种字符的次数和字符种类数。

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    int cnt[26] = {0}, kinds = 0, left = 0, ret = 0;
    for (int right = 0; right < (int)s.size(); ++right)
    {
        if (cnt[s[right] - 'a']++ == 0) ++kinds;
        while (kinds > 2)
        {
            if (cnt[s[left] - 'a']-- == 1) --kinds;
            ++left;
        }
        ret = max(ret, right - left + 1);
    }
    cout << ret << '\n';
    return 0;
}

0 -> 1 时种类加一,1 -> 0 时种类减一,两个判断都写在自增自减表达式的返回值里,省掉一次查找。左右指针都只向右走,时间 O(n)。

字符串的排列要求按字典序输出字符串的所有不同排列。先排序,让相同字符相邻;DFS 填每个位置,跳过“和前一个相同、且前一个还没用过”的字符,避免重复。

#include <algorithm>
#include <string>
#include <vector>
using namespace std;
 
class Solution
{
    vector<string> ret;
    string path, s;
    vector<bool> vis;
    int n;
 
    void dfs()
    {
        if ((int)path.size() == n) { ret.push_back(path); return; }
        for (int i = 0; i < n; ++i)
        {
            if (vis[i]) continue;
            if (i > 0 && s[i] == s[i - 1] && !vis[i - 1]) continue;  // 去重
            vis[i] = true;
            path.push_back(s[i]);
            dfs();
            path.pop_back();
            vis[i] = false;
        }
    }
 
public:
    vector<string> Permutation(string str)
    {
        s = str;
        sort(s.begin(), s.end());
        n = s.size();
        ret.clear();
        path.clear();
        vis.assign(n, false);   // 每次调用都重置,避免残留
        dfs();
        return ret;
    }
};

去重条件是 !vis[i-1]:s[i-1] 已经用过时,允许 s[i] 接在不同前缀后面;没用过时,两个相同字符在同一层只能选一次。课件把 ret、path、vis 做成成员却不在入口清空,同一个 Solution 对象调用两次会拼出上一次的结果。

奇数位丢弃的序列是 0..n 共 n+1 个数,每轮丢掉当前序列里奇数位置的数,直到剩一个。第一轮之后留下的是原下标为偶数的元素,第二轮再筛一次,最后留下的是不超过 n 的最大 2^k - 1。

#include <iostream>
using namespace std;
 
int main()
{
    int n;
    while (cin >> n)          // 多组输入
    {
        int p = 1;
        while (p - 1 <= n) p *= 2;
        cout << p / 2 - 1 << '\n';
    }
    return 0;
}

循环结束时 p 是第一个满足 p - 1 > n 的 2 的幂,p / 2 - 1 就是最大的 2^k - 1 ≤ n。n = 500 时 p = 512,输出 255,与样例一致。O(log n)。

求和从 1..n 中选若干个数,使和为 m,输出所有方案。每个数有选和不选两种情况,DFS 枚举;当前和等于 m 时输出,超过 m 或下标超过 n 时剪枝。

#include <iostream>
using namespace std;
 
int n, m, sum;
bool choose[11];
 
void dfs(int x)
{
    if (sum == m)
    {
        for (int i = 1; i <= n; ++i)
            if (choose[i]) cout << i << ' ';
        cout << '\n';
        return;
    }
    if (sum > m || x > n) return;
 
    sum += x;                 // 选 x
    choose[x] = true;
    dfs(x + 1);
    sum -= x;
    choose[x] = false;
 
    dfs(x + 1);               // 不选 x
}
 
int main()
{
    cin >> n >> m;
    dfs(1);
    return 0;
}

元素都是正整数,一旦当前和等于 m 就不可能再选别的数,可以直接返回。方案按数字从小到大的顺序输出,与枚举顺序一致。最坏 O(2^n),n 很小。

BFS、记忆化与堆

kotori 和迷宫从 k 出发,e 是出口,* 是墙。求可达出口的数量和最近出口的步数。

BFS 时不要把出口再入队:题面说到达出口就会离开迷宫,从出口继续往外走没有意义。BFS 结束后扫描所有出口的 dist。

#include <cstring>
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
 
const int N = 35;
int n, m, sx, sy;
char g[N][N];
int dist[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
 
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            cin >> g[i][j];
            if (g[i][j] == 'k') sx = i, sy = j;
        }
 
    memset(dist, -1, sizeof dist);
    queue<pair<int, int>> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;
 
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k)
        {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (g[nx][ny] == '*' || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            if (g[nx][ny] != 'e') q.push({nx, ny});
        }
    }
 
    int cnt = 0, best = 1e9;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (g[i][j] == 'e' && dist[i][j] != -1)
            {
                ++cnt;
                best = min(best, dist[i][j]);
            }
 
    if (cnt == 0) cout << -1 << '\n';
    else cout << cnt << ' ' << best << '\n';
    return 0;
}

出口不出队,但它的距离已经写好,最后统一统计。时间 O(nm),空间 O(nm)。

题面里的 6×8 样例迷宫:k 是起点,. 是道路,* 是墙,e 是出口;两个可达出口的距离分别是 8 和 7,所以输出 2 7

矩阵最长递增路径给一个非负矩阵,可以上下左右移动,要求路径上的值严格递增,求最长路径长度。

从每个格子出发做 DFS,向比当前值大的邻居递归。路径值严格递增,不可能回到之前的格子,不需要额外的访问标记;memo[i][j] 存下以该格为起点的最长长度。

#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
 
class Solution
{
    int n, m, memo[1010][1010];
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
 
    int dfs(vector<vector<int>>& a, int i, int j)
    {
        if (memo[i][j] != -1) return memo[i][j];
        int len = 1;
        for (int k = 0; k < 4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] > a[i][j])
                len = max(len, 1 + dfs(a, x, y));
        }
        return memo[i][j] = len;
    }
 
public:
    int solve(vector<vector<int>>& matrix)
    {
        n = matrix.size();
        m = matrix[0].size();
        memset(memo, -1, sizeof memo);
        int ret = 1;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                ret = max(ret, dfs(matrix, i, j));
        return ret;
    }
};

每个格子只计算一次,时间 O(nm),空间 O(nm)。如果不加 memo,同一条后缀会被不同起点反复展开,最坏退化成指数级。

题面里的示例矩阵:按 1→2→3→6→9 走,递增路径长度为 5;灰色格子标出了路径经过的位置

【模板】哈夫曼编码给 n 个权值,求哈夫曼树的最短带权路径长度。每次取两个最小的合并,把合并值放回堆,累加所有合并值。

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    priority_queue<long long, vector<long long>, greater<long long>> heap;
    for (int i = 0; i < n; ++i)
    {
        long long x;
        cin >> x;
        heap.push(x);
    }
 
    long long ret = 0;
    while (heap.size() > 1)
    {
        long long a = heap.top(); heap.pop();
        long long b = heap.top(); heap.pop();
        ret += a + b;
        heap.push(a + b);
    }
    cout << ret << '\n';
    return 0;
}

每个权值被累加的次数等于它在树中的深度,所有合并值之和就是带权路径长度。堆操作 O(log n),总时间 O(n log n)。n = 1 时循环不执行,答案为 0。