这一周的题面里,“最多”“最小”“是否可行”这些词背后往往藏着一个可以直接算出来的量。回合制战斗如果写成 while 会跑十亿次,写成除法只需要三行;区间 DP 如果把状态定义成“两端”,循环方向就决定了递推表能不能填对。

题目模型时间复杂度
小易的升级之路模拟 + gcdO(n log A)
礼物的最大价值路径 DPO(mn)
对称之美逐对判断字符集合O(total chars + 26n)
经此一役小红所向无敌公式化模拟O(1)
连续子数组最大和线性 DPO(n)
非对称之美字符串规律O(n)
爱丽丝的人偶构造O(n)
集合有序集合O((n+m) log(n+m))
最长回文子序列区间 DPO(n²)
添加字符枚举对齐位置O(nm)
数组变换位运算判定O(n)
装箱问题01 背包O(nV)
打怪公式化模拟O(1)/组
字符串的分类排序 + 哈希去重O(n·L log L)
城市群数量连通块 DFSO(n²)
判断是不是平衡二叉树递归返回值O(n)
最大子矩阵二维前缀和O(n⁴)
小葱的 01 串环形定长窗口O(n)

把模拟翻译成算式

小易的升级之路。初始能力 a,依次遇到 n 个怪物,每个怪物能力 b:b 不大于 a 时能力直接加 b,否则加 gcd(a, b)。每组数据独立,读到 EOF。

#include <iostream>
using namespace std;
 
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
 
int main()
{
    int n, a, b;
    while (cin >> n >> a)
    {
        for (int i = 0; i < n; i++)
        {
            cin >> b;
            if (b <= a) a += b;
            else a += gcd(a, b);
        }
        cout << a << endl;
    }
    return 0;
}

while (cin >> n >> a) 处理“组数未知”的输入,和第一周的 while (cin >> s) 是同一个套路。能力值只会增加,不会溢出 int 的前提是题面范围;gcd 的递归深度是 O(log A)。

经此一役小红所向无敌。双方每回合同时出手,各自扣掉对方攻击力的血量;一方死亡后,活着的一方释放一次十倍攻击力的大招。问总伤害。逐回合循环会跑十亿次,正确做法是把“双方都还活着”的阶段整段算出来:

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    long long a, h, b, k;
    cin >> a >> h >> b >> k;
 
    long long rounds = min(h / b, k / a);
    long long ret = rounds * (a + b);
    h -= rounds * b;
    k -= rounds * a;
 
    if (h > 0 && k > 0)
    {
        h -= b;
        k -= a;
        ret += a + b;
    }
 
    if (h > 0 || k > 0) ret += 10 * (h > 0 ? a : b);
 
    cout << ret << endl;
    return 0;
}

min(h / b, k / a) 是“在某一方血量归零之前,双方还能完整互砍的回合数”。整除向下取整,正好对应“不能多砍一回合”。这段结束后,至少有一方的血量已经不大于 0;如果两方都还大于 0,说明双方是在同一回合各剩一点血,需要再补一回合。

大招的伤害是“活着那一方的攻击力 × 10”,不是对面。三元表达式 h > 0 ? a : b 挑的就是这个。若补刀回合后两方同时死亡,h > 0 || k > 0 为假,不再放大招,这也符合“死了就放不出技能”的语义。

血量与攻击到 1e9,回合数乘伤害能到 1e18 量级,四个变量和 ret 都要 long long。

打怪。我方血量 h、攻击 a,怪物血量 H、攻击 A,轮流攻击且我方先手。问活着的前提下最多连续杀几只;若可以杀无限只,输出 -1。

#include <iostream>
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int h, a, H, A;
        cin >> h >> a >> H >> A;
 
        if (a >= H)
        {
            cout << -1 << endl;
            continue;
        }
 
        int hits = H / a + (H % a != 0);   // 怪物需要挨几下
        int taken = (hits - 1) * A;        // 杀一只,我方挨几下
        int ans = (h - 1) / taken;         // 全程血量保持为正
 
        cout << ans << endl;
    }
    return 0;
}

一只怪物要挨 ceil(H/a) 下才死,这期间我方挨 ceil(H/a) − 1 下(最后一下之后怪物已经死了,不会再反击)。杀一只的净损耗是 taken。要活着,累计损耗必须小于 h,所以最多 floor((h-1)/taken) 只。

a >= H 时一击必杀,我方不掉血,怪物数量没有上限,返回 -1。只要 a < H,hits >= 2,taken >= A >= 1,除法不会出现零。

题面给的四项都不超过 1000,taken 最大约 1e6,int 足够,这里不需要 64 位。(h-1)/taken 比课件那句 h / taken - (h % taken == 0 ? 1 : 0) 短,而且“整除时只能少杀一只”的边界由 h-1 直接表达出来。

以 i 结尾,还是区间两端

连续子数组最大和。状态定义成“以 i 结尾的最大和”,转移就只剩两个选择:接在前一段后面,或者从 i 重新开始。

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    int cur = 0, ans = INT_MIN;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        cur = max(cur, 0) + x;
        ans = max(ans, cur);
    }
    cout << ans << endl;
    return 0;
}

max(cur, 0) 的含义是“前面那段如果是负收益,就不带它”。全负数数组时 ans 会落在最大的那个单元素上,而不是 0,因为本题要求非空子数组。课件把 ans 初始化成 -101,依赖元素不小于 -100;用 INT_MIN 或“第一个元素”作初值,和值域无关。时间 O(n)、额外空间 O(1)。

最长回文子序列。状态是区间:dp[i][j] 表示 s[i..j] 里最长回文子序列的长度。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    int n = s.size();
    if (n == 0) { cout << 0 << endl; return 0; }
 
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = n - 1; i >= 0; i--)
    {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++)
        {
            if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
            else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[0][n - 1] << endl;
    return 0;
}

s[i] == s[j] 时,两端的字符可以同时放进回文,长度在 dp[i+1][j-1] 的基础上加 2。课件在讲状态转移的文字里写的是 dp[i][j] = dp[i + 1][j - 1],漏了这个 2;同一页的代码写的是 + 2。照文字推,任何一对相同字符都不增加长度,"bbbab" 会退化成 1,而正确答案是 4(bbbb)。

i 从 n-1 往 0 走、j 从 i+1 往 n-1 走,是为了保证 dp[i+1][j-1] 先被算出来。区间 DP 的“短区间先算”比转移方程更容易写错。i 和 j 相邻且字符相同时,dp[i+1][j-1] 是一个空区间,全局零初始化让它等于 0,加 2 就是 "aa" 的长度;这里的“没填过是 0”是设计出来的,不是巧合。

题面的输出描述写的是“输出最长回文子序列”,但样例输出的是长度(abccsb 输出 4),按样例返回长度。

路径 DP 与 01 背包

礼物的最大价值。从左上角走到右下角,只能向右或向下,每个格子的礼物只能拿一次,求最大价值。状态就是“走到 (i, j) 的最大价值”。

#include <vector>
#include <algorithm>
using namespace std;
 
class Solution
{
public:
    int maxValue(vector<vector<int>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
 
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
 
        return dp[m][n];
    }
};

多开一行一列的 0 作为边界,转移里不用判断 i-1、j-1 是否越界。原网格与 dp 的下标差 1,读值时要写 grid[i-1][j-1]。时间 O(mn)、空间 O(mn);每行只依赖上一行,可以压成一维,但这里 m、n 都不大,没必要。

装箱问题。箱子容量 V,n 个物品各有体积,每个最多放一次,求剩余空间最小。把“体积”同时当作 01 背包的“体积”和“价值”,答案是 V - dp[V]。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int V, n;
    cin >> V >> n;
 
    vector<int> dp(V + 1, 0);
    for (int i = 0; i < n; i++)
    {
        int v;
        cin >> v;
        for (int j = V; j >= v; j--)
            dp[j] = max(dp[j], dp[j - v] + v);
    }
    cout << V - dp[V] << endl;
    return 0;
}

dp[j] 表示容量不超过 j 时能装进去的最大体积。容量从大到小遍历,保证 dp[j-v] 还是“没考虑当前物品”的旧值,每个物品只用一次。V 不超过 2e4、n 不超过 30,一维数组足够。

二维前缀和、连通块与树

最大子矩阵。给定 n×n 矩阵,求元素和最大的子矩阵。二维前缀和把任意子矩阵的和降到 O(1),再枚举左上角和右下角。

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
 
const int N = 110;
int p[N][N];
 
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            int x;
            cin >> x;
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + x;
        }
 
    int ans = INT_MIN;
    for (int x1 = 1; x1 <= n; x1++)
        for (int y1 = 1; y1 <= n; y1++)
            for (int x2 = x1; x2 <= n; x2++)
                for (int y2 = y1; y2 <= n; y2++)
                {
                    int sum = p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1];
                    ans = max(ans, sum);
                }
 
    cout << ans << endl;
    return 0;
}

二维前缀和的容斥是“大矩形减上方减左方,再加回左上角被减两次的小矩形”。子矩阵和则是“右下角前缀减上边减左边,加回左上”。

n = 100 时子矩阵总数约 2.55×10⁷,四重循环在 C++ 里能过。ans 用 INT_MIN,不依赖元素的下界;课件 C++ 版用 -127 * N、Java 版用 -127,两个哨兵不一致,只有在元素都不小于 -127 时才恰好安全。

城市群数量。邻接矩阵表示城市之间的连接,m[i][j] = 1 表示 i 和 j 相连,求连通块个数。扫到未访问的点就计数加一,DFS 把整块标记掉。

#include <vector>
using namespace std;
 
class Solution
{
    int n;
    vector<bool> vis;
 
    void dfs(vector<vector<int>>& m, int u)
    {
        vis[u] = true;
        for (int v = 0; v < n; v++)
            if (!vis[v] && m[u][v]) dfs(m, v);
    }
 
public:
    int citys(vector<vector<int>>& m)
    {
        n = m.size();
        vis.assign(n, false);
 
        int ret = 0;
        for (int i = 0; i < n; i++)
            if (!vis[i])
            {
                ret++;
                dfs(m, i);
            }
        return ret;
    }
};

邻接矩阵的 DFS 每个点要扫一整行,复杂度 O(n²);n 到 200,四万次访问很小。vis 放在对象里会在多次调用之间残留,这里在 citys 入口 assign 一次,避免上一组数据污染。

判断是不是平衡二叉树。每个结点的左右子树高度差不超过 1,且左右子树都平衡。让递归函数返回树高,不平衡时返回 -1,父结点看到 -1 就直接向上返回。

#include <algorithm>
#include <cstdlib>
using namespace std;
 
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
class Solution
{
    int dfs(TreeNode* root)
    {
        if (root == nullptr) return 0;
 
        int l = dfs(root->left);
        if (l == -1) return -1;
 
        int r = dfs(root->right);
        if (r == -1) return -1;
 
        if (abs(l - r) > 1) return -1;
        return max(l, r) + 1;
    }
 
public:
    bool IsBalanced_Solution(TreeNode* pRoot)
    {
        return dfs(pRoot) != -1;
    }
};

树高一定是非负数,所以 -1 可以安全地当“失败”的哨兵。先算左、再算右,任意一边返回 -1 就剪枝,不用继续往下走。每个结点只被访问一次,时间 O(n)、递归栈深度 O(h)。

如果先写一个求高度的函数,再对每个结点调用一次判断平衡,复杂度会退化成 O(n²)——每层都把子树高度重复算了一遍。带返回值的写法把“高度”和“是否平衡”合并在一次后序遍历里。

字符串的对称与对齐

对称之美。给 n 个字符串,从每个串里取一个字符拼成长度 n 的串,问能否是回文。第 i 个串和第 n−1−i 个串必须能取到同一个字符,每一对独立。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
 
        vector<vector<bool>> has(n, vector<bool>(26, false));
        for (int i = 0; i < n; i++)
        {
            string s;
            cin >> s;
            for (char c : s) has[i][c - 'a'] = true;
        }
 
        bool ok = true;
        for (int l = 0, r = n - 1; l < r; l++, r--)
        {
            bool share = false;
            for (int c = 0; c < 26; c++)
                if (has[l][c] && has[r][c]) { share = true; break; }
            if (!share) { ok = false; break; }
        }
        cout << (ok ? "Yes" : "No") << endl;
    }
    return 0;
}

vector<vector<bool>> 每组重新构造,天然清空;课件用全局 vis[110][26] 并在每组 memset,n 一旦超过 110 就越界,而且清空逻辑要靠人记得写。把字符集合挂在每个串上,检查一对只需要扫 26 个字母。

复杂度是 O(总字符数 + 26n),t ≤ 50、n ≤ 100、串长 ≤ 50,完全够。

非对称之美。求最长“非回文”子串的长度。结论分三种:全是同一个字符时无解,输出 0;本身是回文但不是全同字符时,答案是 n−1;本身不是回文时,答案是 n。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string s;
    cin >> s;
    int n = s.size();
 
    bool allSame = true;
    for (int i = 1; i < n; i++)
        if (s[i] != s[0]) { allSame = false; break; }
    if (allSame) { cout << 0 << endl; return 0; }
 
    bool pal = true;
    for (int l = 0, r = n - 1; l < r; l++, r--)
        if (s[l] != s[r]) { pal = false; break; }
 
    cout << (pal ? n - 1 : n) << endl;
    return 0;
}

为什么回文时是 n−1?回文去掉首字符和去掉尾字符得到的两个长度 n−1 的子串,如果它们也都是回文,连锁推导会迫使整个串所有字符相同(与“不是全同”矛盾)。所以至少有一个长度 n−1 的子串不是回文,答案取 n−1;又不可能取到 n(整串是回文),所以正好是 n−1。

串长到 1e7,只允许 O(n) 扫描和 O(1) 额外空间。ios::sync_with_stdio(false) 关掉 C 与 C++ 流的同步,读入大字符串会快很多。s.size() 是无符号类型,int n 在 1e7 范围内没问题。

添加字符。给两个串 a 和 b,只能在 a 的头尾加字符把它补到 b 的长度,问补完后最少有多少位不同。枚举 a 对齐到 b 的每一个起点即可。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main()
{
    string a, b;
    cin >> a >> b;
    int m = a.size(), n = b.size();
 
    int ans = m;
    for (int i = 0; i <= n - m; i++)
    {
        int diff = 0;
        for (int j = 0; j < m; j++)
            if (a[j] != b[i + j]) diff++;
        ans = min(ans, diff);
    }
    cout << ans << endl;
    return 0;
}

i <= n - m 的等号不能少:i = n - m 表示 a 对齐到 b 的末尾,也就是“只在左边补字符”的方案。ans 初值取 m,差异数不可能超过 a 的长度,不需要造一个 INT_MAX。两层循环最多 50×50 次,KMP 在这里没有意义。

字符串的分类。两个字符串如果字符集合相同就算同一类,求类数。把每个串内部排序,排序后的串就是这一类的代表,丢进 unordered_set 去重。

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    unordered_set<string> st;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        st.insert(s);
    }
    cout << st.size() << endl;
    return 0;
}

排序把“字符的顺序”抹掉,只留下“每种字符出现几次”。unordered_set 的 insert 对重复键不改变大小,最后直接输出 size()。复杂度 O(n·L log L),L 是串长。

排序、集合与构造

爱丽丝的人偶。n 个人偶身高 1 到 n,要求除两端外的每个人偶,左右邻居一个比它高、一个比它矮(即每个内部位置都是波峰或波谷)。构造 1, n, 2, n−1, 3, … 即可。

#include <iostream>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    int left = 1, right = n;
    bool first = true;
    while (left <= right)
    {
        if (!first) cout << ' ';
        cout << left++;
        first = false;
 
        if (left <= right)
        {
            cout << ' ' << right--;
        }
    }
    cout << endl;
    return 0;
}

序列的相邻项一大一小交替,所以每个内部元素要么是“小-大-小”的波峰,要么是“大-小-大”的波谷。n = 3 时输出 1 3 2,样例说明里的 1 3 2、2 1 3、2 3 1 都合法。输出任意一种即可,注意行末不要多空格。

集合。给两个集合,求并集并按升序输出。std::set 插入时自动去重并保持有序。

#include <iostream>
#include <set>
using namespace std;
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    set<int> s;
    for (int i = 0; i < n + m; i++)
    {
        int x;
        cin >> x;
        s.insert(x);
    }
 
    bool first = true;
    for (int x : s)
    {
        if (!first) cout << ' ';
        cout << x;
        first = false;
    }
    cout << endl;
    return 0;
}

两组输入可以合并成一个循环,因为都只是往同一个集合里插。set 的插入是 O(log size),总复杂度 O((n+m) log(n+m))。用 vector 读进来再 sort + unique 也能做,代码略长但常数更小。

数组变换。每次可以把任意一个数乘 2,问能否让所有数相等(操作次数不限)。目标值一定是数组里的最大值 b:任何数只能变大,最终的共同值不可能小于 b,而取 b 又不需要把 b 再变大。

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    int b = 0;
    int a[55];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        b = max(b, a[i]);
    }
 
    for (int i = 0; i < n; i++)
    {
        if (b % a[i] != 0) { cout << "NO" << endl; return 0; }
        int x = b / a[i];
        if ((x & (x - 1)) != 0) { cout << "NO" << endl; return 0; }
    }
    cout << "YES" << endl;
    return 0;
}

b / a[i] 必须是整数,且必须是 2 的幂:不断乘 2 只能把 a[i] 变成 a[i] * 2^k,所以比值只能是 2 的幂。x & (x - 1) 清掉最低位的 1,结果为 0 当且仅当 x 只有一个二进制位为 1。a[i] 至少为 1,除法不会除零;n ≤ 50、a[i] ≤ 1e9,int 足够。

环上的定长窗口

小葱的 01 串。长度 n 为偶数的环形 01 串,选连续的一半染红、另一半染白,要求红白两段里 0 的个数相等、1 的个数也相等,问有多少种染色方案(红白分布区分)。

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    int n;
    string s;
    cin >> n >> s;
 
    int sum[2] = {0, 0};
    for (char c : s) sum[c - '0']++;
 
    int half = n / 2;
    int cnt[2] = {0, 0};
    int ret = 0, left = 0;
 
    for (int right = 0; right < n - 1; right++)
    {
        cnt[s[right] - '0']++;
        while (right - left + 1 > half)
        {
            cnt[s[left] - '0']--;
            left++;
        }
 
        if (right - left + 1 == half &&
            cnt[0] * 2 == sum[0] && cnt[1] * 2 == sum[1])
        {
            ret += 2;
        }
    }
    cout << ret << endl;
    return 0;
}

红色是一段长度为 n/2 的连续区间,所以问题变成“有多少个长度 n/2 的窗口,0 和 1 各占全部的一半”。窗口内 cnt[0] * 2 == sum[0] 成立时,1 的条件自动成立(总数和一半长度都固定)。

ret += 2 和 right < n - 1 是同一件事的两面。长度为 n/2 的窗口在环上有 n 个起点,起点 i 和起点 i + n/2 对应的两个方案正好互补:把红白对调。红白分布区分,所以这两个是不同方案,找到一个就加 2。反过来,只要枚举前 n/2 个起点就够了;right < n - 1 配合窗口长度限制,正好覆盖这些起点。

环上的方案容易被数两遍。验证方法很简单:把 n 取到 4 手算一遍,看每个方案被统计了几次。如果循环写到 right < n,答案会正好是正确值的两倍。