第二周的题面普遍短,数据范围也不大,失分点集中在“选择哪种枚举对象”和“状态在两次调用之间是否干净”。前者决定复杂度,后者决定评测机跑第二个用例时会不会翻车。

题目模型时间复杂度
在字符串中找出连续最长的数字串双指针分段O(n)
岛屿数量floodfill(DFS/BFS)O(mn)
拼三角排序 + 枚举分法O(t)
求最小公倍数辗转相除O(log min(a,b))
数组中的最长连续子序列排序 + 去重扫描O(n log n)
字母收集路径 DPO(mn)
添加逗号从右往左数三位O(n)
跳台阶线性递推O(n)
扑克牌顺子布尔哈希O(5)
最长回文子串中心扩展O(n²)
买卖股票的最好时机(一)前缀最小值O(n)
过河卒路径计数 DPO(nm)
游游的水果大礼包枚举一种礼包的数量O(min(n,m))
买卖股票的最好时机(二)正差分求和O(n)
倒置字符串整体反转 + 逐词反转O(n)
删除公共字符布尔哈希O(n+m)
两个链表的第一个公共结点双指针换头O(n+m)
mari 和 shiny计数型 DPO(n)

从后往前扫:数字串、逗号、倒置

连续最长的数字串。扫到第一个数字时,把右指针一路推到这段数字的末尾,更新答案后从段尾继续,整串只走一遍。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
 
    int begin = -1, len = 0;
    for (int i = 0; i < (int)s.size(); )
    {
        if (!(s[i] >= '0' && s[i] <= '9')) { i++; continue; }
 
        int j = i;
        while (j < (int)s.size() && s[j] >= '0' && s[j] <= '9') j++;
        if (j - i > len)
        {
            len = j - i;
            begin = i;
        }
        i = j;
    }
 
    if (begin == -1) cout << endl;
    else cout << s.substr(begin, len) << endl;
    return 0;
}

i = j 是这段代码的关键:段尾的 j 指向第一个非数字字符,它是下一段的起点候选,外层再从 j 继续,不会重复扫描。用严格大于更新答案,长度相同时保留更靠左的那段,符合“输出第一个最长数字串”的要求。

添加逗号。给一个数字字符串,从右往左每三位插一个逗号。不需要真的从右往左遍历,只要判断当前位置右侧还有几个字符:n - i - 1 是右侧字符数,它能被 3 整除且当前位置不是最后一个字符时,补一个逗号。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    int n = s.size();
    string ret;
 
    for (int i = 0; i < n; i++)
    {
        ret += s[i];
        if ((n - i - 1) % 3 == 0 && i != n - 1) ret += ',';
    }
    cout << ret << endl;
    return 0;
}

i != n - 1 是唯一需要额外判断的边界:把 123 的每个字符都处理完时,右侧字符数为 0,能被 3 整除,但末尾不能再补逗号。这个条件合并了“长度正好是 3 的倍数”和“不是最后一位”两种情况,比先分组再拼接短。

倒置字符串。把 I am a student 变成 student a am I。整体反转得到 tneduts a ma I,每个单词内部再反转一次就回到正确顺序。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main()
{
    string s;
    getline(cin, s);
 
    reverse(s.begin(), s.end());
 
    int left = 0, n = s.size();
    while (left < n)
    {
        int right = left;
        while (right < n && s[right] != ' ') right++;
        reverse(s.begin() + left, s.begin() + right);
 
        while (right < n && s[right] == ' ') right++;
        left = right;
    }
 
    cout << s << endl;
    return 0;
}

第二个 while 跳过连续空格,所以输入里有多个空格时不会把空格算进单词。getline 必须用,因为 cin >> s 只会读到一个单词。

排序、枚举与贪心:候选数量决定复杂度

拼三角。六根木棍,分成两组各三根,问能否两组都成三角形。直接枚举“选三根”的组合有 20 种,两组互换后剩 10 种分法。把六根排好序之后,只需要检查四种分法:

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        long long a[6];
        for (int i = 0; i < 6; i++) cin >> a[i];
        sort(a, a + 6);
 
        bool ok =
            (a[0] + a[1] > a[2] && a[3] + a[4] > a[5]) ||
            (a[0] + a[2] > a[3] && a[1] + a[4] > a[5]) ||
            (a[0] + a[3] > a[4] && a[1] + a[2] > a[5]) ||
            (a[0] + a[4] > a[5] && a[1] + a[2] > a[3]);
 
        cout << (ok ? "Yes" : "No") << endl;
    }
    return 0;
}

排序后,一组三根能否成三角形只取决于“两条短边之和是否大于最长边”。固定最小的 a[0] 后,它的两个搭档从 a[1] 到 a[5] 里选,共有 10 种组合;这四种对应的是“搭档相邻”的极端情况,其余的搭配要么让 a[0] 组更容易成立,要么让剩下的三根更容易成立,不会比这四种更差。用十种分法暴力对拍可以验证四种条件与二十种组合等价。

木棍长度小于 1e9,两数之和最多接近 2e9,int 刚好不溢出;写成 long long 不用记这个界限。

数组中的最长连续子序列。这里的“连续”指数值连续(x, x+1, x+2),与下标无关。排序后相同的数会挨在一起,扫描时要跳过重复值,但不能把它们算进长度。

#include <algorithm>
#include <vector>
using namespace std;
 
class Solution
{
public:
    int MLS(vector<int>& arr)
    {
        sort(arr.begin(), arr.end());
 
        int n = arr.size(), best = 0;
        int i = 0;
        while (i < n)
        {
            int j = i + 1, len = 1;
            while (j < n)
            {
                int d = arr[j] - arr[j - 1];
                if (d == 1)
                {
                    len++;
                    j++;
                }
                else if (d == 0)
                {
                    j++;
                }
                else
                {
                    break;
                }
            }
            best = max(best, len);
            i = j;
        }
        return best;
    }
};

d == 0 时只移动 j 不加长度,因为同一个值不能重复计数;d > 1 时序列断开,外层直接从 j 开始新的一段。复杂度 O(n log n),空间取决于排序实现。

另一种做法是把所有数丢进 unordered_set,只从“没有前驱 x−1 的数”开始沿 x+1 往上数,平均 O(n)。它的缺点是哈希表的常数大、最坏情况退化;排序版更稳,代码也短。

游游的水果大礼包。一号礼包用 2 个苹果 + 1 个桃子,价值 a;二号礼包用 1 个苹果 + 2 个桃子,价值 b。直觉上会先做“单位水果价值更高”的那种,但这个贪心是错的:两种礼包的材料配比不同,先做一种会把另一种需要的材料耗掉。

正确做法是枚举一号礼包的个数:

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    long long n, m, a, b;
    cin >> n >> m >> a >> b;
 
    long long ans = 0;
    for (long long x = 0; x <= min(n / 2, m); x++)
    {
        long long leftApple = n - 2 * x;
        long long leftPeach = m - x;
        long long y = min(leftApple, leftPeach / 2);
        ans = max(ans, a * x + b * y);
    }
    cout << ans << endl;
    return 0;
}

固定 x 之后,二号礼包的个数由剩余材料直接算出,没有第二种选择,所以枚举 x 就覆盖了所有方案。四个数都能到 1e6,a * x 能到 1e12,必须用 long long。枚举上界是 min(n/2, m),最坏 5e5 次。

贪心错在比较的维度:两种礼包同时消耗苹果和桃子,按“单位材料价值”排序只能盯住一种材料,另一种材料先被耗光时,剩下的材料就凑不成任何礼包。枚举 x 相当于把所有可能的材料分配都走一遍,不会漏掉“少做一个一号、多做两个二号”这种交换。

哈希记“还差什么”

删除公共字符。第二个串里的字符全部不能出现在结果里。先把第二个串标进哈希,再扫第一个串,跳过被标记的字符。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string s, t;
    getline(cin, s);
    getline(cin, t);
 
    bool del[256] = {false};
    for (char c : t) del[(unsigned char)c] = true;
 
    string ret;
    for (char c : s)
        if (!del[(unsigned char)c]) ret += c;
 
    cout << ret << endl;
    return 0;
}

两行输入都可能含空格,必须用 getline;用 cin >> 会只读到第一个单词。下标强转 unsigned char 是因为 char 在部分平台上是有符号的,非 ASCII 字符会变成负下标,越界写。输入只含 ASCII 时两种写法都对,但强转一次没有成本。

扑克牌顺子。五张牌,0 可以当任意牌,问能否凑成顺子。判定只有两条:非零牌不能重复;最大值减最小值不超过 4。

#include <vector>
#include <algorithm>
using namespace std;
 
class Solution
{
public:
    bool IsContinuous(vector<int>& numbers)
    {
        bool seen[14] = {false};
        int mx = 0, mn = 14;
 
        for (int x : numbers)
        {
            if (x == 0) continue;
            if (seen[x]) return false;
            seen[x] = true;
            mx = max(mx, x);
            mn = min(mn, x);
        }
        return mx - mn <= 4;
    }
};

第二条的推理:五张牌要连成五连,跨度最多 4;反过来,跨度不超过 4 时,中间缺的每一张都能用 0 补上,而 0 的个数正好等于缺口数(五张牌减去非零张数,等于跨度加一减非零张数)。两条一起既充分也必要。五张全是 0 时循环一次都不更新,mx - mn = -14,判断为真,正确。

课件把 hash 写成类成员 bool hash[14],函数里从不清空。评测机如果在同一个 Solution 对象上连续调用两次,第二次读到的是上一局的 true,一张没重复的牌会被判成重复。把数组放进函数体,每次调用重新初始化,问题消失。

窗口、中心扩展与差分

最长回文子串。回文一定有一个中心:奇数长度以某个字符为中心,偶数长度以两个字符之间的空隙为中心。一共有 2n−1 个中心,每个向两边扩到不能扩为止。

#include <string>
#include <algorithm>
using namespace std;
 
class Solution
{
public:
    int getLongestPalindrome(string s)
    {
        int n = s.size(), ret = 1;
        for (int i = 0; i < n; i++)
        {
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; }
            ret = max(ret, r - l - 1);
 
            l = i;
            r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; }
            ret = max(ret, r - l - 1);
        }
        return ret;
    }
};

循环结束时 l 和 r 已经越过了回文的两端,所以长度是 r - l - 1,不是 r - l。中心枚举把候选从 O(n²) 个子串降到 O(n) 个中心,每个中心最多扩 O(n),总时间 O(n²)、额外空间 O(1)。暴力“枚举所有子串再验证”是 O(n³),n 到 1000 时必超时。

ret 初始为 1 依赖 n ≥ 1;空串要单独返回 0。

买卖股票的最好时机(一)。只能买卖一次,卖出必须在买入之后。固定卖出日 i,最优买价就是 [0, i] 里的最低价,所以扫描时维护前缀最小值。

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    long long x;
    cin >> x;
    long long mn = x, ans = 0;
 
    for (int i = 1; i < n; i++)
    {
        cin >> x;
        ans = max(ans, x - mn);
        mn = min(mn, x);
    }
    cout << ans << endl;
    return 0;
}

先更新答案、再更新最小值,mn 始终是“当前天之前的最低价”。反过来先更新 mn 也不会错(当天买当天卖收益为 0),但语义上不如前者清楚。ans 初值 0 表示“不交易”也是一种选择,收益为负的区间自动被忽略。

买卖股票的最好时机(二)。可以无限次交易,但再次买入前必须清仓。答案等于所有相邻正差分之和。

long long ans = 0;
for (int i = 1; i < n; i++)
    if (a[i] > a[i - 1]) ans += a[i] - a[i - 1];

为什么这样等价于“低买高卖”?把一次跨多天的持仓拆成每天“昨天买、今天卖”的若干笔,只要中间某天在涨,拆开就能多赚这一天的差价;如果某天在跌,拆开后那天不交易,收益不变。所以把所有上升段逐日累加,不会比任何真实交易方案差,也不会超过最优。时间 O(n)、空间 O(n)(读入数组)或 O(1)(边读边算)。

网格上的三类问题:连通块、路径和、路径计数

岛屿数量。1 是陆地,上下左右相连的 1 属于同一个岛。扫到 1 就把整块连通区域淹掉,计数加一。

#include <vector>
#include <queue>
using namespace std;
 
class Solution
{
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
 
public:
    int solve(vector<vector<char>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        int ret = 0;
 
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] != '1') continue;
                ret++;
 
                queue<pair<int, int>> q;
                q.push({i, j});
                grid[i][j] = '0';
                while (!q.empty())
                {
                    auto [a, b] = q.front();
                    q.pop();
                    for (int k = 0; k < 4; k++)
                    {
                        int x = a + dx[k], y = b + dy[k];
                        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1')
                        {
                            grid[x][y] = '0';
                            q.push({x, y});
                        }
                    }
                }
            }
        return ret;
    }
};

课件 C++ 版用 DFS 并直接改写 grid,Java 版用 vis 保留 grid。两种都对,但 C++ 版把入参改掉了:如果评测在同一个网格上再调用一次,第二次会返回 0。要么在入口拷贝一份,要么和 Java 版一样用 vis。

网格最大 200×200,最坏情况一整块陆地有 40000 个格子。DFS 的递归深度等于连通块大小,在栈较小的平台上可能溢出;BFS 用显式队列,深度只有 1,写法也只多几行。

字母收集。从左上角走到右下角,每次只能向右或向下,格子上的 l/o/v/e 分别值 4/3/2/1 分,求最大得分。路径 DP 的状态是“走到 (i, j) 的最大得分”。

#include <iostream>
#include <algorithm>
using namespace std;
 
const int N = 510;
char g[N][N];
int dp[N][N];
 
int main()
{
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];
 
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            int v = 0;
            char c = g[i][j];
            if (c == 'l') v = 4;
            else if (c == 'o') v = 3;
            else if (c == 'v') v = 2;
            else if (c == 'e') v = 1;
 
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + v;
        }
    cout << dp[m][n] << endl;
    return 0;
}

dp[0][*] 和 dp[*][0] 全是 0,第一行和第一列不需要特判。cin >> g[i][j] 读 char 时会跳过空白,逐行输入整串字母也能正确读满。值映射写成 if-else 链是因为只有四个字母;字母集合更大时用数组映射。

过河卒。棋盘上 A 在 (0,0),B 在 (n,m),只能向右或向下走。马在 (x,y),马本身和马一步能到的八个点都不能走,问路径条数。

过河卒的控制点:马跳一步的落点满足横纵坐标都不同、坐标差绝对值之和为 3,图中 P1 到 P8 就是这八个点

#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
 
long long dp[25][25];
 
int main()
{
    int n, m, x, y;
    cin >> n >> m >> x >> y;
 
    x += 1;
    y += 1;
    dp[0][1] = 1;
 
    for (int i = 1; i <= n + 1; i++)
        for (int j = 1; j <= m + 1; j++)
        {
            bool blocked = (i == x && j == y) ||
                           (i != x && j != y && abs(i - x) + abs(j - y) == 3);
            dp[i][j] = blocked ? 0 : dp[i - 1][j] + dp[i][j - 1];
        }
 
    cout << dp[n + 1][m + 1] << endl;
    return 0;
}

两个技巧:

  • 整体平移一格,棋盘变成 1..n+1,dp[0][j] 和 dp[i][0] 这一圈 0 就是天然边界,转移里不用判断越界。
  • 把起点的 1 塞进 dp[0][1]。于是 dp[1][1] = dp[0][1] + dp[1][0] = 1,起点自然为 1;如果马正好在起点,blocked 会把 dp[1][1] 清零。

马的控制点条件必须同时要求 i != x 和 j != y。只写 |i-x| + |j-y| == 3 会把正上方三格和正右方三格也算进去,那些点并不是马能一步到达的位置。

棋盘最大 20×20,路径数最多到 C(40,20) 量级(约 1.37e11),int 装不下,dp 必须是 long long。时间 O(nm)、空间 O(nm)。

数论与链表

求最小公倍数。lcm(a,b) = a / gcd(a,b) * b,先除后乘。辗转相除的递归版两行:

#include <iostream>
using namespace std;
 
long long gcd(long long a, long long b)
{
    return b == 0 ? a : gcd(b, a % b);
}
 
int main()
{
    long long a, b;
    cin >> a >> b;
    cout << a / gcd(a, b) * b << endl;
    return 0;
}

课件把 a、b 写成 int,输出 a * b / gcd(a, b)。题面给的范围是 1 <= a, b <= 100000,100000 * 99999 = 9999900000,已经超过 32 位有符号整数的上限(2147483647)。乘法先溢出,再除以 gcd 也救不回来,结果是一个看似正常、实际错误的数。两种改法:把变量改成 long long;或者按 a / gcd(a,b) * b 的顺序做,中间结果一定整除,且量级只有答案那么大。后者即使 a、b 是 long long 也值得保留,能避免不必要的溢出。

两个链表的第一个公共结点。两条链表可能共享一段后缀。让两个指针分别从两个头出发,走到空就换到另一条链的头,再次相遇的位置就是公共结点。

struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
{
    ListNode* a = pHead1;
    ListNode* b = pHead2;
    while (a != b)
    {
        a = a ? a->next : pHead2;
        b = b ? b->next : pHead1;
    }
    return a;
}

设两条链的独有部分长度分别为 x、y,公共部分为 z。指针 a 走 x + z + y,指针 b 走 y + z + x,总步数相同,要么在公共结点相遇,要么都走到空(没有公共结点时返回 nullptr)。时间 O(n+m)、空间 O(1)。用哈希存第一条链的所有结点也能做,但要多 O(n) 空间。

线性 DP 与计数

跳台阶。一次可以跳 1 级或 2 级,问跳上 n 级有多少种走法。最后一步要么从 n−1 跳 1 级,要么从 n−2 跳 2 级,所以 f(n) = f(n-1) + f(n-2)。

#include <iostream>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    int a = 1, b = 1, c = 1;
    for (int i = 2; i <= n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    cout << (n <= 1 ? 1 : c) << endl;
    return 0;
}

a 和 b 分别是 f(i-2) 和 f(i-1),初值 f(0) = 1、f(1) = 1。课件在最后写 if (n == 0 || n == 1) cout << n,n = 1 输出 1 没问题,n = 0 会输出 0;按“不跳也是一种方案”的定义,0 级台阶有 1 种走法。题面一般保证 n ≥ 1,所以不影响评测,但这个特判和递推的初值在语义上是对不上的。

mari 和 shiny。统计字符串里有多少个形如 shy 的子序列(不要求连续)。扫一遍,维护“到当前位置为止有多少个 s”“多少个 sh”,遇到 y 就把当前的 sh 数累加进答案。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    int n;
    string str;
    cin >> n >> str;
 
    long long s = 0, h = 0, y = 0;
    for (char ch : str)
    {
        if (ch == 's') s++;
        else if (ch == 'h') h += s;
        else if (ch == 'y') y += h;
    }
    cout << y << endl;
    return 0;
}

h += s 表示“以当前这个 h 结尾的 sh 子序列有 s 个”;y += h 同理。这样每个三元组只在最右边的 y 处被统计一次,不重不漏。n 到 1e5 时三元组数量能到 10^13 量级,三个计数器必须是 long long。

复杂度 O(n)、空间 O(1)。