第 05 周的 18 道题按模型分成六组,同一组里的代码骨架往往只差一行:
| 模型 | 题目 |
|---|---|
| 计数与质数 | 笨小猴、小红的 ABC、爱吃素、kotori 和气球 |
| 区间 | 主持人调度(一)、主持人调度(二) |
| 0/1 背包 | 分割等和子集 |
| 序列 DP | 不相邻取数、最长上升子序列(二)、最长公共子序列(一)、二叉树中的最大路径和 |
| 排序后的窗口 | 空调遥控、相差不超过 k 的最多数、消减整数 |
| 搜索与模拟 | 走迷宫、体操队形、游游的重组偶数、排序子序列 |
计数与质数:先缩小参与比较的范围
笨小猴给一个只含小写字母的单词,统计出现次数最多和最少的字母,若 maxn - minn 是质数就输出 Lucky Word 与该差值,否则输出 No Answer 与 0。
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
bool isPrime(int n)
{
if (n < 2) return false;
for (int i = 2; i <= sqrt(n); ++i)
if (n % i == 0) return false;
return true;
}
int main()
{
string s;
cin >> s;
int cnt[26] = {0};
for (char ch : s) cnt[ch - 'a']++;
int mn = 1000, mx = 0;
for (int i = 0; i < 26; ++i)
if (cnt[i]) // 没出现过的字母不参与比较
{
mn = min(mn, cnt[i]);
mx = max(mx, cnt[i]);
}
if (isPrime(mx - mn)) cout << "Lucky Word\n" << mx - mn << '\n';
else cout << "No Answer\n0\n";
return 0;
}mn 的初值不能写 0。26 个桶里大部分是 0,一旦让 0 参与 min,最小值永远是 0,差值退化成最大次数。if (cnt[i]) 和初值 1000 是同一件事的两面:只让真正出现过的字母进比较。
质数判断必须挡住 n < 2。maxn - minn 可能是 0 或 1:aaa 的差值是 0,aab 的差值是 1,两者都不是质数。循环从 2 开始一次都不执行时,isPrime 会返回 true,程序就会把 aaa 判成 Lucky Word。
字符串长度不超过 100,26 个桶加一次到 sqrt(100) 的试除,时间可以忽略;空间是一个长度 26 的数组。
小红的 ABC只有 a、b、c 三种字符,要求最短的、长度超过 1 的回文子串。长度大于 3 的回文一定包含一个短 2 或短 3 的回文:把首尾同时去掉,回文仍是回文,反复剥到长度 2 或 3 为止。因此只需枚举相邻的两个字符和间隔一个的三个字符。
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
cin >> s;
int n = s.size(), ret = -1;
for (int i = 0; i < n; ++i)
{
if (i + 1 < n && s[i] == s[i + 1]) { ret = 2; break; }
if (i + 2 < n && s[i] == s[i + 2]) ret = 3;
}
cout << ret << '\n';
return 0;
}先扫到二元组就直接 break,因为 2 已经是最小可能值;三元组只负责把答案从 -1 抬到 3。复杂度 O(n),空间 O(1)。把每个子串都取出来判回文是 O(n³),长度 100 虽然也能过,但没必要。
爱吃素判断 a × b 是否为素数,1 ≤ a, b ≤ 10^11。乘积最大到 10^22,超过 64 位整数(约 9.22 × 10^18)的上限,乘法本身就溢出;即使换成大整数,试除到 sqrt(10^22) = 10^11 也必然超时。
素数只有两个正因子,所以 a × b 是素数只有一种可能:其中一个因子是 1,另一个是素数。1 × 1 = 1 不是素数,1 × 合数 也不是。
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
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()
{
int T;
cin >> T;
while (T--)
{
LL a, b;
cin >> a >> b;
bool ok = (a == 1 && isPrime(b)) || (b == 1 && isPrime(a));
cout << (ok ? "YES" : "NO") << '\n';
}
return 0;
}a、b 最大 10^11,试除只到约 316228,T 不超过 10,时间充裕。
kotori 和气球有 n 种颜色、摆 m 个位置,相邻不能同色,求方案数对 109 取模。第一位有 n 种选法,之后每一位只要和上一位不同,各有 n-1 种,共 n × (n-1)^(m-1)。边算边取模,幂不需要单独写快速幂。
#include <iostream>
using namespace std;
const int MOD = 109;
int main()
{
int n, m;
cin >> n >> m;
int ret = n % MOD;
for (int i = 1; i < m; ++i)
ret = (long long)ret * (n - 1) % MOD; // 中间乘积用 64 位
cout << ret << '\n';
return 0;
}n = 1 且 m > 1 时答案为 0,循环自然算出 0,不需要特判。时间复杂度 O(m)。
区间调度:先排序,再决定比较谁
**主持人调度(一)**问一个主持人能否参加全部活动。活动占据 (start, end),端点相接不算冲突,题面用 [0,10]、[10,20]、[20,30] 给出 true。
#include <algorithm>
#include <vector>
using namespace std;
class Solution
{
public:
bool hostschedule(vector<vector<int>>& schedule)
{
sort(schedule.begin(), schedule.end()); // 先按左端点
for (size_t i = 1; i < schedule.size(); ++i)
if (schedule[i][0] < schedule[i - 1][1]) return false;
return true;
}
};排序后只需比较相邻区间。反证:若存在 i < j 使 l_j < r_i,而所有相邻对都不重叠,那么 l_{i+1} >= r_i;左端点单调不减,又有 l_j >= l_{i+1},合起来得到 l_j >= r_i,与 l_j < r_i 矛盾。所以任意一对重叠都会在某个相邻位置暴露,检查相邻就够。
比较用 < 而不是 ≤:l == r 表示前一场刚结束、后一场刚开始,按题面允许。把所有区间两两比较是 O(n²),n 到 10^5 时超时;排序后 O(n log n)。
**主持人调度(二)**问最少需要几个主持人,做法是左端点排序加一个小根堆,堆里存每个主持人当前最后一场的结束时间。
#include <algorithm>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
class Solution
{
public:
int minmumNumberOfHost(int n, vector<vector<int>>& startEnd)
{
sort(startEnd.begin(), startEnd.end());
priority_queue<int, vector<int>, greater<int>> freeAt; // 小根堆
freeAt.push(startEnd[0][1]);
for (int i = 1; i < n; ++i)
{
int l = startEnd[i][0], r = startEnd[i][1];
if (l >= freeAt.top()) { freeAt.pop(); freeAt.push(r); } // 有人已空闲
else freeAt.push(r); // 只能加人
}
return (int)freeAt.size();
}
};堆顶是最早空闲的时间。左端点排序后,当前活动的开始时间不早于之前所有活动,所以只要堆顶能接上,就一定有一个人可以复用;接不上时,堆里所有人都还在忙,必须新增。l >= freeAt.top() 的等号对应端点可相接。最终堆的大小就是人数,复杂度 O(n log n)。
std::priority_queue 默认是 less,也就是大根堆;漏写 greater<int> 时 top() 拿到的是最晚空闲的人,复用判断整体反过来,程序仍能编译。
Java 版比较器写的是 return a[0] - b[0];。题面允许端点接近 int 边界,两个大数相减会溢出,排序结果可能错乱;应写 Integer.compare(a[0], b[0])。
0/1 背包:把“最大价值”换成“能不能凑出”
分割等和子集给 n 个正整数,判断能否分成两组且两组和相等。总和为奇数直接 false;否则目标 target = sum / 2,问题变成从 n 个数中选若干个,和恰好为 target。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
int sum = 0;
for (int& x : a) { cin >> x; sum += x; }
if (sum % 2) { cout << "false\n"; return 0; }
int target = sum / 2;
vector<char> dp(target + 1, 0); // dp[j]:能否凑出和 j
dp[0] = 1;
for (int x : a)
for (int j = target; j >= x; --j) // 逆序,保证每个数只用一次
dp[j] = dp[j] || dp[j - x];
cout << (dp[target] ? "true" : "false") << '\n';
return 0;
}j 必须从大到小。正序时 dp[j - x] 可能在本轮刚被当前这个数更新过,同一个数被用了两次。比如 target 是 10、数组里只有一个 5,正序会让 dp[5] 先变 1,dp[10] 再拿这个 1 更新成 1,凭空凑出 10;逆序时 dp[10] 查到的还是上一轮的 0。
课件用二维 dp[i][j],N = 510、M = 510 * 110 / 2,int 表约占 510 × 28050 × 4 ≈ 57 MB,再算上其他数组,离常见 64 MB 限制很近。一维表只需要 target + 1 个字节(char),空间降到 O(sum/2),时间仍是 O(n × sum/2)。
序列 DP:四种表,四种返回方式
不相邻取数从数组中取若干不相邻的数,求最大和。定义两个状态:f[i] 表示取第 i 个数时的最大和,g[i] 表示不取第 i 个数时的最大和。
f[i] = g[i - 1] + a[i]; // 取了 i,i-1 一定不能取
g[i] = max(f[i - 1], g[i - 1]);
// 答案 max(f[n], g[n])f 和 g 都只依赖上一项,可以滚成两个变量:
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, a[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
long long f = 0, g = 0; // f:取当前数;g:不取当前数
for (int i = 1; i <= n; ++i)
{
long long nf = g + a[i]; // 取了 i,i-1 一定不能取
long long ng = max(f, g); // 不取 i,i-1 取不取都行
f = nf;
g = ng;
}
cout << max(f, g) << '\n';
return 0;
}时间复杂度 O(n),空间 O(1)。只用一个 dp[i] = max(dp[i-1], dp[i-2] + a[i]) 也等价,但两个状态分得更清楚。
**最长上升子序列(二)**要求严格上升子序列的最大长度,n 到 10^5,O(n²) 的写法会超时。维护 tail[len]:长度为 len 的所有上升子序列中,末尾元素的最小值。
#include <algorithm>
#include <vector>
using namespace std;
class Solution
{
public:
int LIS(vector<int>& a)
{
vector<int> tail;
for (int x : a)
{
auto it = lower_bound(tail.begin(), tail.end(), x); // 第一个 >= x
if (it == tail.end()) tail.push_back(x);
else *it = x;
}
return (int)tail.size();
}
};新元素比当前最长末尾大,就能接在后面,长度加一;否则替换掉第一个 >= x 的末尾。替换不会让已有长度变短,只是让同一长度的结尾更小,给后面的数留出更多空间。严格上升用 lower_bound(第一个 >=);如果允许相等,改用 upper_bound。复杂度 O(n log n),空间 O(n)。
**最长公共子序列(一)**给两个字符串,求 LCS 长度。dp[i][j] 表示 s1 前 i 个字符与 s2 前 j 个字符的 LCS 长度。
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1010;
char s1[N], s2[N];
int dp[N][N];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> s1[i];
for (int i = 1; i <= m; ++i) cin >> s2[i];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
cout << dp[n][m] << '\n';
return 0;
}字符相同时,两个末尾一定能配上,答案来自左上角加一;不相同时,至少有一个末尾不在 LCS 里,取上方或左方。把字符串存到 1 号下标,[0][*] 和 [*][0] 自然表示空串,省掉边界判断。
课件这里有两处要改。第一处是状态定义写成“s1 的 [0, i] 区间与 s2 的 [0, j] 区间”,但代码从 1 开始存、循环也从 1 起,dp[i][j] 实际表示的是前 i 个字符,也就是 [1, i]。第二处是转移式里的 do[i][j - 1],dp 被打成了 do,照抄编译不过。
二维表可以压成一维,但更新 dp[j] 时要用到上一轮的 dp[j-1],得额外保存一个 prev 变量;不写这层优化时,O(nm) 空间对 1000 × 1000 的 int 是 4 MB,可以接受。
二叉树中的最大路径和的路径可以从任意节点出发,沿父子边走到任意节点。对每个节点,左右子树各能提供一条向下的最大单链;经过当前节点的路径和是 val + 左单链 + 右单链,而向上返回的只能是 val + max(左, 右)。
#include <algorithm>
#include <climits>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution
{
int best = INT_MIN;
int dfs(TreeNode* root)
{
if (!root) return 0;
int l = max(0, dfs(root->left)); // 负的单链直接不要
int r = max(0, dfs(root->right));
best = max(best, root->val + l + r);
return root->val + max(l, r);
}
public:
int maxPathSum(TreeNode* root)
{
best = INT_MIN;
dfs(root);
return best;
}
};dfs 的返回值不能包含“左右都走”的分叉,因为父节点只能接其中一条;全局 best 负责记录分叉形成的完整路径。取子树返回值与 0 的较大值,表示负贡献的子树直接舍弃。时间复杂度 O(n),递归栈 O(h)。
答案初值课件写的是 -1010,这个数只比 -1000 更小一点,是按“节点值不低于 -1000”取的;值域一变,地板就要跟着改。用 INT_MIN 不依赖具体值域。

排序后的窗口与倍增
空调遥控给 n 个学生对温度的敏感值,空调设成 t 时,只有 |t - a[i]| ≤ p 的学生满意,求最多满意人数。
满意的一组学生,其敏感值的最大值与最小值之差不超过 2p;反过来,只要极差不超过 2p,把温度设成区间左端加 p,就能覆盖整组。排序后问题变成“最长的一段,极差不超过 2p”。
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n, p, a[N];
int main()
{
cin >> n >> p;
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a, a + n);
int left = 0, ret = 0;
for (int right = 0; right < n; ++right)
{
while ((long long)a[right] - a[left] > 2LL * p) ++left;
ret = max(ret, right - left + 1);
}
cout << ret << '\n';
return 0;
}右端右移会把极差撑大,超过 2p 就把左端右推。数组有序,a[right] - a[left] 随 left 增大而减小,left 不必回退,总移动次数 O(n)。复杂度 O(n log n),瓶颈在排序;2 * p 用 64 位算,避免 p 接近 10^9 时乘二溢出。另一种做法是枚举温度 t,在有序数组里二分出 [t-p, t+p] 覆盖的区间;t 的候选范围由学生温度决定,直接用窗口更省事。
相差不超过 k 的最多数是同一个窗口,只把 2p 换成 k:
sort(a, a + n);
int left = 0, ret = 0;
for (int right = 0; right < n; ++right)
{
while ((long long)a[right] - a[left] > k) ++left;
ret = max(ret, right - left + 1);
}课件 C++ 版把 ret 初始化成 1、Java 版初始化成 0,两者在 n ≥ 1 时结果相同;统一写成 0 更省心。
消减整数给 H,第一次必须减 1,之后每次减的数必须与上一次相同,或者是上一次的两倍,求减到 0 的最少次数。
贪心策略是“能翻倍就翻倍”:减掉当前的 a 后,如果剩余 h 能被 2a 整除,就把 a 翻倍。翻倍之后所有未来的减数都是 2a 的倍数,所以剩余必须能被 2a 整除,否则永远减不到 0;翻倍越早,后面的减数起点越大,总步数不会更多。
#include <iostream>
using namespace std;
int solve(int h)
{
int cnt = 0, a = 1;
while (h > 0)
{
h -= a;
++cnt;
if (h % (2 * a) == 0) a *= 2;
}
return cnt;
}
int main()
{
int T;
cin >> T;
while (T--)
{
int h;
cin >> h;
cout << solve(h) << '\n';
}
return 0;
}每个 a 上最多减两次就会因为奇偶变化而满足翻倍条件,a 每次至少翻倍,所以单组复杂度 O(log H);H 到 10^9、T 到 10^4,总操作量很小。
搜索:BFS 的边界与 DFS 的剪枝
走迷宫给 n × m 的网格,. 是空地、* 是障碍,求起点到终点的最少移动次数。BFS 第一次到达某格时就是最短距离。
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1010;
int n, m, x1, y1, x2, y2;
char grid[N][N];
int dist[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int bfs()
{
if (x1 == x2 && y1 == y2) return 0; // 起点就是终点
if (grid[x2][y2] == '*') return -1;
memset(dist, -1, sizeof dist);
queue<pair<int, int>> q;
q.push({x1, y1});
dist[x1][y1] = 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 &&
grid[nx][ny] == '.' && dist[nx][ny] == -1)
{
dist[nx][ny] = dist[x][y] + 1;
if (nx == x2 && ny == y2) return dist[nx][ny];
q.push({nx, ny});
}
}
}
return -1;
}
int main()
{
cin >> n >> m >> x1 >> y1 >> x2 >> y2;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> grid[i][j];
cout << bfs() << '\n';
return 0;
}坐标按 1 开始存,边界就写 1..n、1..m。课件的 C++ 版把列边界写成 y >= 0 && y <= m,而读入只有 1..m;同一处给出的 Java 版是 y >= 1,是正确的。y == 0 那一列从未赋值,默认是 '\0',== '.' 又挡了一层,所以样例没暴露;换一道把空地记成 0 的题就会越界。
另一个边界是起点与终点重合。课件的 BFS 只在扩展到邻居时才比较终点,起点等于终点时会一路搜完并返回 -1;在入队前加一句 if (x1 == x2 && y1 == y2) return 0;。
BFS 每个格子最多进队一次,时间 O(nm),空间 O(nm)。用 DFS 也能走通,但第一次到达不保证最短,必须搜完所有路径再取最小,代价高得多。

体操队形有 n 个队员,第 i 个队员要求排在 a[i] 号前面(a[i] = i 表示没有要求),求满足所有要求的排列数。n 不超过 10,直接按位置枚举。
#include <iostream>
using namespace std;
const int N = 15;
int n, a[N], ret;
bool used[N];
void dfs(int pos)
{
if (pos > n) { ++ret; return; }
for (int i = 1; i <= n; ++i)
{
if (used[i]) continue; // i 已经排过
if (i != a[i] && used[a[i]]) return; // a[i] 已在前面,i 永远排不到 a[i] 前
used[i] = true;
dfs(pos + 1);
used[i] = false; // 回溯
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
dfs(1);
cout << ret << '\n';
return 0;
}这里用 return 而不是 continue 是有依据的:a[i] 已经被排过,说明 i 无论放在后面的哪个位置都晚于 a[i],当前分支不可能补全,整枝可以直接丢掉。若只是跳过 i 继续试别的队员,当前分支仍然无解,continue 只会多做无用功。a[i] = i 时 used[a[i]] 就是 used[i],而 i 尚未使用,条件自然不成立。
最坏枚举 10! 个排列,剪枝后远小于这个上界;空间是递归栈 O(n)。
两个模拟:偶数的末位与排序子序列的切分
游游的重组偶数给 q 个不超过 10^9 的正整数,可以任意重排数位,要求结果是偶数且没有前导零,输出任意一个合法结果,无解输出 -1。
偶数的判定只看最后一位。从右往左找最靠右的偶数字,把它换到末位;如果整个数没有偶数字,输出 -1。
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main()
{
int q;
cin >> q;
while (q--)
{
string s;
cin >> s;
int n = s.size(), p = -1;
for (int i = n - 1; i >= 0; --i)
if ((s[i] - '0') % 2 == 0) { p = i; break; }
if (p == -1) { cout << -1 << '\n'; continue; }
swap(s[p], s[n - 1]);
cout << s << '\n';
}
return 0;
}前导零的限制在这里被“取最靠右的偶数字”躲开了:如果末位本身是偶数,p 就是末位,交换等于没做;如果末位是奇数,换到首位的那个字符就是末位的奇数,不可能是 0。反过来,如果随手把第一个偶数字和末位的 0 交换,20 会变成 02,前导零就出现了。每问 O(位数),q 到 10^5,总量可接受。
排序子序列把数组切成尽量少的连续段,每段非递增或非递减。贪心是每次走完当前这段的单调方向,段数加一,再从下一个位置开始。
课件的写法先按 i 与 i+1 的大小关系分三支,其中“相等”那一支只推进指针、不计数,然后统一 i++。对 [1,1,2,1] 走一遍:开头两个 1 相等,指针推到下标 1,再 i++ 到 2;接着从 2 开始走递减段 [2,1],段数只加一次,答案输出 1。正确切法是 [1,1,2] 与 [1],应为 2。课件自己也注明“测试数据不严谨”,这个漏算在样例上看不出来。
把相等的一段当作切分点的一部分,先跨过相等段,再决定单调方向:
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, a[N];
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
int ans = 0, i = 0;
while (i < n)
{
int j = i;
while (j + 1 < n && a[j] == a[j + 1]) ++j; // 先吃掉相等段
if (j + 1 == n) { ++ans; break; } // 剩下全是同一个数
if (a[j] < a[j + 1])
while (j + 1 < n && a[j] <= a[j + 1]) ++j;
else
while (j + 1 < n && a[j] >= a[j + 1]) ++j;
++ans;
i = j + 1;
}
cout << ans << '\n';
return 0;
}样例 1 2 3 2 2 1:第一段走到 3,第二段从 2 开始把 2,2 和末尾的 1 一起带走,输出 2。每个元素只被扫一次,时间 O(n),空间 O(1)。
还没有评论 — 第一条由你来留。