《深入浅出程序设计竞赛进阶篇》勘误

kkksc03 · 2024-10-03 16:05:35 · 算法·理论

感谢读者阅读本书。因为作者有时候脑抽或者其他原因，本书不可避免出现一些疏漏。我们每次印刷都会尝试修正。如果你读书时遇到了一些困惑，也有可能是书确实写错了。

我们勘误时会记录第一次给提出这个错误的读者的用户名。感谢所有读者的反馈。

反馈链接：https://www.luogu.com.cn/discuss/946364

（于 2025 年 8 月更新）2024 年 9/12 月第一/二次印刷

已知的较大问题，但是暂未完成修复，有待我们和作者讨论

P299-300 宝藏存在代码错误：1. 对于相关数组与变量，应开 long long,不开连样例都过不了。2. 第 13-14 行循环范围应是“i<n”不包括 n,虽不影响程序正常运行仍应当更正。此外，代码出现了多个表述不清，前文用 f 表示 dp 状态，后文又用 f 预处理最短距离，用 g 表示 dp 状态，在代码中更是用 d 作为预处理数组，f 作为 dp 状态，给读者造成很大阅读负担。第 16-17 行用 cnt 表示上一个合法子集状态，与 cnt 计数器的意义明显不搭。我们会在修复后提供本题合理的讲解说明。PulsarEcho
P303 ~ P305 一双木棋的代码似乎会被卡到无法通过。ethansang

严重错误

这类错误存在概念或者事实性错误，可能会对读者产生误导。

中等错误

这类错误因为疏忽而出现，虽然不至于误导读者，但是可能会给读者造成迷惑，一些读者可以意识到写错了。

P50 计算 T(n)=2T(n/2)+O(\sqrt n) 的答案有误（过程正确），应当为 O(n)。AstralSparkle
P166 树上任何一个结点到根的路径上经过的重链条数不会超过路径上的轻边数减去 1 存在错误，应当是重链数 \leq 轻边数 + 1。xu_jh
P295 讲解中的状态定义是 f_{i,j,k} 表示前 i 行，二进制表示为 j，放置了 k 个国王的方案数。代码的 f_{i,j,k} 表示前 i 行放置了 j 个国王，二进制表示为 k，无法对应。这一部分代码或者讲解可能会重新编写。bus_man
P369 排列计数一题的代码有细节问题：第 10 行三目运算符少了问号，应为 D[i] = (1ll * D[i - 1] * i + (i % 2 ? MOD - 1 : 1)) % MOD;。Lucas 定理的函数定义 pow 应当为 ll 类型。x12345678901

小错误

这类错误包括错别字或者语病、笔误，不影响意思，读者不一定可以意识到这些错误。

P8 注释中说：对答案的贡献为 x，即在最终求解的答案中需要加上 x。虽然没有错误，但是题目中也有定义变量 x，容易造成歧义。可以改为：对答案的贡献为 A（A 为一个数字），即在最终求解的答案中需要加上 A。Beacon_wolf
P8 表格有误，左上角不应为 i\j，而应当为 x\z。wwwidk1234
P16 长度为的 k 区间改为长度为 k 的区间。Kun_is_Me
P61 中代码的最后一行的问号疑似非英语问号，字体有误。此外，P123 的第十行，P163 的倒数第三行都出现了这样的问题。还有 P365、P428、P436。x12345678901
P69 下方文字，应当改为：用 std::map 或 Hash 的方式来分别存储。x12345678901
P83 数据范围的小于号应当改为小于等于号。Phigros_11calors
P91 最后一段文字中的 c_i 应当为 \sum \limits_{j = i -\operatorname{lowbit}(i) + 1}^i a_j。BeeAC
P103 图 6-4(a) 线段树节点 #4 到 #8#9 中间少画了两条连线。YLF_Cat
P109 代码的第五行出现了空白注释。not_so_littlekayen
P118 S = s1 + '@' + s2 应当为 S = s2 + '@' + s1，原叙述与下文和代码不符。mizimo
P119 中代码的倒数第三行输出应当是 cout<<b[i]<<' ';，书上的代码漏了空格。x12345678901
P133 可持久化线段树的总复杂度为 O((n + m)\log n)，而非 O(n \log n)。tangzirui1016
P154 “分析”部分第二段第二行中，“被它分成了若棵子树”应作“被它分成了若干棵子树”。Kun_is_Me
P157 cout << center << '' << sum; 应当改为 cout << center << ' ' << sum;wangzih123
P171 例 9-10，应当是“y 的权值减去 x 的权值最大”，题意写反了。[丘李]Chilllee](https://www.luogu.com.cn/user/706209)
P195 习题 9 的第三行，应当为若 x 或 y 未重建好。wisdom2010
P219 第五行代码 putchar 里缺了空格，且注释字体不一致。EDJIW
P222 因为如果 u 能到 v，v 能到 w，就有 u 能到 v。应当改为：就有 u 能到 w。hczyy
P222 图 12-6 中，\{1\} 不是一个强连通分量（它不是极大的），\{2\} 是一个强连通分量。YLF_Cat
P224 图 12-8(b) 中，结点 3 的 low 应当为 2。Wh1t5Zz
P243 分析里的代码应当改为 f[i][j] = max(f[i - 1][j], f[i - 1][j - a[i]] + v[i])。oxenxu
P254 注释里“枚举 1 到 i-1 中小于或等于 a[i] 的数”，应当改为“大于或等于”。xc_ty
P263 应当明确 f_{k,i,j} 的定义是表示字符串 A 以第 i 个字符结尾取出 k 段，在字符串 B 恰好匹配到 j 的方案数。tangzirui1016
P270 分别对应以上子结构的 3 类中的第二类，应当是把 S_i 接在这个串的右边。mizimo
P277 习题 2 中“例如”一段，“希望把它别涂上……”应作“希望把它涂上……”Kun_is_Me
P297 中代码所有的分号看起来不像是英语分号，字体有误。NIUNIUcow

P304 中，dfs 函数的最后一个 for 循环缺少大括号。应当改为：

for (int i = 1; i <= n; ++i) {
  if (cnt[i] >= m || cnt[i] >= cnt[i - 1])
      continue;
  cnt[i]++; dfs(); cnt[i]--;
}

ethansang

P345 普通筛代码的第一行未在 int 和 i 之间打空格。int_inf
P367 上方代码中的乘号被错误排版为了感叹号。应当改为：
```
d3 = (d3 + 1) * c3;
d4 = (d4 + 1) * c4;
```
P403 线性方程组的等号应当换为同余符号。x12345678901
P414 最上方程序第九行 cout << Rand() % MAXN << "" 应改为 cout << Rand() % MAXN << " "，原文少了空格。x12345678901

（于 2025 年 2 月更新）2024 年 9/12 月第一/二次印刷

严重错误

这类错误存在概念或者事实性错误，可能会对读者产生误导。

（反馈：ToastBread）P265 例题 14-10 出现以下几个错误，将会在下一版处理：

未讲解动态规划的初始化，在代码中也未体现该部分。
代码无法通过本题。事实上，本题数据范围为 |a_i| \leq 10^9，需要使用 long long 类型存储计算变量。

一份可以通过该题的代码如下：

#include <bits/stdc++.h>
using namespace std;
long long a[110][110], f[110][110][110], n, K, ans = -2e18;
//数组 f 应当为 long long 类型，且 ans 设置的负值应当足够大
int main() {
cin >> n >> K;
for (int i = 1; i <= n; i++) {
   for (int j = 1; j <= i; j++)
       cin >> a[i][j];
}
for (int j = 1; j <= n; j++) {
   f[n][j][0] = a[n][j];
   f[n][j][1] = a[n][j] * 3;
   for (int k = 2; k <= K; k++) //遗漏了初始化
       f[n][j][k] = -2e18;
}
for (int i = n - 1; i >= 1; i--) {
   for (int j = 1; j <= i; j++) {
       for (int k = 0; k <= K; k++) {
           f[i][j][k] = max(f[i + 1][j][k], f[i + 1][j + 1][k]) + a[i][j];
           if (k >= 1)
               f[i][j][k] = max(f[i][j][k], a[i][j] * 3 + max(f[i + 1][j][k - 1], f[i + 1][j + 1][k - 1]));
       }
   }
}
for (int i = 0; i <= K; i++)
   ans = max(ans, f[1][1][i]);
cout << ans << endl;
return 0;
}

中等错误

这类错误因为疏忽而出现，虽然不至于误导读者，但是可能会给读者造成迷惑，一些读者可以意识到写错了。

P11 提供的代码无法处理第一行的问题。例如说有 hack 数据：
```
2 2
F F
R R
```
应当输出为 6，但是代码运行输出为 0。Null_h

应当将代码中的

if (i > 1 && a[i][j] == 'F') {
    if (a[i - 1][j] == 'F') {

改为

if (a[i][j] == 'F') {
    if (i > 1 && a[i - 1][j] == 'F') {

P55 习题 4 的题面应当是：会发出 \max\{V_i,V_j\} \times |X_i-X_j| 的音量。Manki23333333
P59-P60 使用卡时的代码无法通过本题，应当特别标注。同理，P63 中提供的 P1763 的代码无法通过本题，也应标注。@__galaxy_1202__
P105 下放 LazyTag 的图 6-5 有误：右侧图应当为 #2 [1,3](25) tag=0，#4 [1,2](16) tag=5。yc6317
P238 把 dfs(x,y) 这个壳脱掉对应的代码，应当为：g[i][j] = max(g[i + 1][j], g[i + 1][j + 1]) + a[i][j]。Hei_Xiaoyi311
P285-P286 例题 16-5 美食家，转移方程应当为：f_{t+1,v}=\max \limits_{(u,v) \in E}\{f_{t,u}+c\}；矩阵加速转移一句中，应当为：(\max,+) 的矩阵满足结合律。fogflea
P343 计算 x 的通解形式，应当为：x=a_1t_1M_1+a_2t_2M_2+a_3t_3M_3+kM，在书中缺漏 kM 一项。Oier_Dr_Wu

小错误

这类错误包括错别字或者语病、笔误，不影响意思，读者不一定可以意识到这些错误。

P7 第 14 行应当为 cout << j << ' ';。Cosine_Func
P31 应当为 a[x,y]=\sum \limits_{i=1}^x \sum \limits_{j=1}^y b[i,j]。Il1_1_3
P32 应当为区间 [a_i,b_i)，左闭右开，而非 [a_i,b_i]。chenlifeng
P44 倒数第二段，每次在答案数组中放入 a_i 时，应该有 j-1 个逆序对产生，因此答案加上 j-1。chenlifeng
P48-49、P297 代码注释字体与其他试题的注释不一致，但是注释内容无问题，不影响内容阅读理解。Alan6234
P56 习题 7 的数据范围应当为：N\leq 2\times 10^5，M<10^9，1\leq C_i,D_i \leq M。him的自我修养
P61、P62 的代码中，变量 mn、mx 无用。QQzhi
P76 脚注中，“本题尚未找到没有多项式复杂度解法”中，应当去掉“没有”二字，为：“本题尚未找到多项式复杂度解法”。HHC883
P88 题目中的 p=u/v，而非 p=uv。determination
P90 代码应当为：y -= q * i;，x -= q * i;。
P117 对于图 7-2(b) 来说，模式串第 5 位失配时，应当考察第 0 位到第 4 位这个子串。Manki23333333
P117 可以利用反证法证明：b_i 最多比 b_{i-1} 多 1，而非 b_i-1。zyl1543130456
P125 试题名异或综合应当为异或粽子。Null_h
P132 应当需要再强调一次，因为经过离散化，因此 n 为值域。zhangbo1000
P156 voiddfs(int u, int fa) 应当为 void dfs(int u, int fa)。

P213 代码缩进混乱。应当为：

void dfs(int u) {
  vis[u] = true;
  for (int i = head[u]; i; i = nxt[i])
        if (!vis[to[i]]) {
            AddEdgeToTree(u, to[i]);
            dfs(to[i]);
        }
}

hensier

P238 图 13-3，在圈 9 边上的数字应当是 22，而非 21。DarenNoob
P236、P241、P242 的代码读入应当是先读入 n,w，再读入一行 n 个整数 a_i。Starmoon_dhw、DarenNoob。
P254 代码中，第 10 行注释，应当为“枚举 1 到 i-1 中大于或等于 a[i] 的数”。zaolong
P270 考察的三种情况应当为：f_{i+1,j}，f_{i,j-1} 和 f_{i+1,j-1}。QQzhi

P273 输入部分应当写作：

for (int i = 1; i <= n; i++)
  scanf("%d", &a[i]);

QQzhi

P279 树上动态规则，应当写作“树上动态规划”。HHC883
P297 代码中定义了多个无用的大数组 H[MAXN] 和 Len[MAXN]。QQzhi
P300 代码中并未定义 MAX MAXN 两个常量，同时也没有使用 using namespace std;。pengyirui
P345 P346 的“埃式筛”应当写作“埃氏筛”。wangmingrui123456
P346 代码第五行中，因为注释在第四行写不下，因此多了一个突兀的 prime[j]，会做排版优化。yc6317
P354 第二行，应当为证明：a^{2\varphi(n)} \equiv a^{\varphi(n)} \pmod {p_i^{k_i}}。wsm52
P360 思维导图中，例 20-1 使用计数原理计算集合数量，而非计算几何数量。Birds_int_he_sky
P397-398 的定义矩阵中，并没有声明 reset() 函数，但直接在 expow 函数中直接调用了该函数。@roumeideclown
P435 tmp1>1 是常量，应当写作 tmp1>3 是常量。wangmingrui123456
P441 底部代码第三行应当是 else return 1LL * (P - P / x) * Inv (P % x) % P。原代码中的 x 打作了 i。wwt100127

《深入浅出程序设计竞赛 进阶篇》勘误

（于 2025 年 8 月更新）2024 年 9/12 月第一/二次印刷

已知的较大问题，但是暂未完成修复，有待我们和作者讨论

严重错误

中等错误

小错误

（于 2025 年 2 月更新）2024 年 9/12 月第一/二次印刷

严重错误

中等错误

小错误

《深入浅出程序设计竞赛进阶篇》勘误