这一周的题面里,“最多”“最小”“是否可行”这些词背后往往藏着一个可以直接算出来的量。回合制战斗如果写成 while 会跑十亿次,写成除法只需要三行;区间 DP 如果把状态定义成“两端”,循环方向就决定了递推表能不能填对。
| 题目 | 模型 | 时间复杂度 |
|---|---|---|
| 小易的升级之路 | 模拟 + gcd | O(n log A) |
| 礼物的最大价值 | 路径 DP | O(mn) |
| 对称之美 | 逐对判断字符集合 | O(total chars + 26n) |
| 经此一役小红所向无敌 | 公式化模拟 | O(1) |
| 连续子数组最大和 | 线性 DP | O(n) |
| 非对称之美 | 字符串规律 | O(n) |
| 爱丽丝的人偶 | 构造 | O(n) |
| 集合 | 有序集合 | O((n+m) log(n+m)) |
| 最长回文子序列 | 区间 DP | O(n²) |
| 添加字符 | 枚举对齐位置 | O(nm) |
| 数组变换 | 位运算判定 | O(n) |
| 装箱问题 | 01 背包 | O(nV) |
| 打怪 | 公式化模拟 | O(1)/组 |
| 字符串的分类 | 排序 + 哈希去重 | O(n·L log L) |
| 城市群数量 | 连通块 DFS | O(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,答案会正好是正确值的两倍。
还没有评论 — 第一条由你来留。