第 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)。

矩阵最长递增路径给一个非负矩阵,可以上下左右移动,要求路径上的值严格递增,求最长路径长度。
从每个格子出发做 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,同一条后缀会被不同起点反复展开,最坏退化成指数级。

【模板】哈夫曼编码给 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。
还没有评论 — 第一条由你来留。