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

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

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

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

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

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

严重错误

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

P299 宝藏，原代码存在一些问题，请对照下文代码进行阅读。新代码将 D、F、Ans 改为 long long，避免在累加和乘法中溢出；将初始化 Log[1 << i]、F[0][1 << i] 的两处循环及最后求答案的循环统一改为 i < N，把保存上一个枚举子集的 cnt 改名为 Pre，并补齐命名空间与常量定义。算法说明中，删除 Floyd 和“最短距离”的错误表述，明确预处理的是新点连向已选集合的最小直接边权：统一用 a_{u,v} 对应 A[u][v]，用 d_{s,t} 对应 D[s][t]，表示新点集 t 中各点连向已选点集 s 的最小直接边权之和；取 t 的最低有效位对应顶点 v，按 d_{s,\varnothing}=0、d_{s,t}=d_{s,t\setminus\{v\}}+\min_{u\in s}a_{u,v} 递推。DP 全文统一使用 f_{h,s} 对应 F[h][s]，表示进行 h 轮扩展、已选点集为 s 时的最小计费值，第 h 轮新增边按 h 倍边权计费；初始化 f_{0,\{v\}}=0，其余为无穷大，转移明确写为 f_{h,s}=\min_{\varnothing\ne t\subsetneq s}\{f_{h-1,s\setminus t}+h\cdot d_{s\setminus t,t}\}，最终答案为 \min_{0\le h<n}f_{h,V}，其中 V 为全部顶点的集合。ThroneofThorns
```
#include <bits/stdc++.h>
using namespace std;
const int MAX = 4100, MAXN = 15, Inf = 0x3f3f3f3f;
int Pre, T, a, b, c ;
long long D[MAX][MAX], F[MAXN][MAX], Ans ;
int Next[MAX], Sup, Now ;
int N, M, i, j, k, Log[MAX], Max, A[MAXN][MAXN] ;   
```

int main(){ memset(A, 63, sizeof(A)) ; memset(F, 63, sizeof(F)), Ans = Inf ; cin >> N >> M ; Max = (1 << N) - 1 ; for (i = 1 ; i <= M ; ++ i) scanf("%d%d%d", &a, &b, &c), A[a][b] = A[b][a] = min(c, A[a][b]) ; //注意处理重边 for (i = 0 ; i < N ; ++ i) Log[1 << i] = i ; for (i = 0 ; i < N ; ++ i) F[0][1 << i] = 0 ; for (i = 1 ; i <= Max ; ++ i){ Pre = 0 ; for (j = Sup = Max ^ i; j ; j = (j - 1) & Sup) Next[j] = Pre, Pre = j ; for (j = Pre ; j ; j = Next[j]){ Now = Log[j & (-j)] + 1, T = Inf ; for (k = 1; k <= N ; ++ k) if (1 << (k - 1) & i) T = min(T, A[Now][k]) ; D[i][j] = D[i][j ^ (j & -j)] + T ; } }//预处理新加入点集到已选点集的最小直接边权之和 for (i = 1 ; i < N ; ++ i) for (j = 1 ; j <= Max; ++ j) for (k = j ; k ; k = (k - 1) & j) F[i][j] = min(F[i][j], F[i - 1][j ^ k] + i * D[j ^ k][k]) ; for (i = 0 ; i < N ; ++ i) Ans = min(Ans, F[i][Max]) ; cout << Ans << endl ; return 0 ; }



## 中等错误

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

- P50 计算 $T(n)=2T(n/2)+O(\sqrt n)$ 的答案有误（过程正确），应当为 $O(n)$。[AstralSparkle](https://www.luogu.com.cn/user/1263338)
- P166 树上任何一个结点到根的路径上经过的重链条数不会超过路径上的轻边数减去 $1$ 存在错误，应当是重链数 $\leq$ 轻边数 $+ 1$。[xu_jh](https://www.luogu.com.cn/user/1208986)
- P295 讲解中的状态定义是 $f_{i,j,k}$ 表示前 $i$ 行，二进制表示为 $j$，放置了 $k$ 个国王的方案数。代码的 $f_{i,j,k}$ 表示前 $i$ 行放置了 $j$ 个国王，二进制表示为 $k$，无法对应。这一部分代码或者讲解可能会重新编写。[bus_man](https://www.luogu.com.cn/user/1632230)
- P305 一双木棋一题，在代码 dfs 函数中缺少花括号，代码无法编译通过。
  ```cpp
  for (int i = 1; i <= n; ++ i) {
      if (cnt[i] >= m || cnt[i] >= cnt[i - 1])
          continue; cnt[i] ++; 
      dfs(); cnt[i] --;
  }

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
P14 图 1-6(c)，第 1 行第 2 个图的小图，最左下角的小方块应该是涂成浅蓝色。匿名用户。
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
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 月第一/二次印刷

严重错误

中等错误

小错误

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