第 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 不依赖具体值域。

题面里的示例树:根 1 的左孩子 2、右孩子 3,最优路径 2→1→3,路径和为 6

排序后的窗口与倍增

空调遥控给 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 也能走通,但第一次到达不保证最短,必须搜完所有路径再取最小,代价高得多。

题面里的 5×5 样例地图:. 是空地,* 是障碍,起点 (1,1),终点 (5,5),样例答案是 12 步

体操队形有 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)。