|
【问题描述】给定一个整数的集合 S 和一个整数 X，问是否存在 S 的一个子集满足其中所有元素的和为 X。
【分析】
子集和问题是一个 NPC 问题，与 0/1 背包问题并不相同。
这个问题有一个时间复杂度为 O(2^N/2)的较高效的搜索算法，其中 N 是集合 S 的大小。
第一步思想是二分。将集合 S 划分成两个子集 S1和 S2，它们的大小都是 N/2。对于 S1和 S2，分别枚举出它们所有的 2N/2 个子集和，保存到某种支持查找的数据结构中（如散列表）。然后就要将两部分结果合并，寻找是否有和为 X 的 S 的子集。事实上，对于 S1的某个和为 X1 的子集，只需寻找 S2 是否有和为 X－X1 的子集。假设采用的散列表是理想的，每次查找和插入都仅花费 O(1)的时间。两步的时间复杂度显然都是 O(2^N/2)。
实践中，往往可以先将第一步得到的两组子集和分别排序，然后再用两个指针扫描的方法查找是否有满足要求的子集和。这样的实现，在可接受的时间内可以解决的最大规模约为 N=42。
预告?
第八单元 排序算法................ 85
8.1 常用排序算法 ................. 85
8.2 简单排序算法 ................. 87
8.3 线性时间排序 ................. 88
8.4 使用二叉树的排序算法*.......... 89
8.5 小结 ........................ 90
第九单元 基本数据结构 ............ 91
9.1 线性表（顺序结构） .............91
9.2 线性表（链式结构） .............91
9.3 栈 ..........................93
9.4 队列.........................94
9.5 二叉树 .......................95
9.6 并查集! ......................99
9.7 小结........................102
第十单元 查找与检索 ............. 104
10.1 顺序查找 ...................104
10.2 二分查找! ..................104
10.3 查找第 k 小元素! .............105
10.4 二叉排序树..................106
10.5 堆和优先队列* ...............108
10.6 哈夫曼（Huffman）树 .........110
10.7 哈希（Hash）表..............111
第十一单元 数学基础 ............. 116
11.1 组合数学 ...................116
11.2 组合数的计算! ...............117
11.3 排列和组合的产生（无重集元素）! 117
11.4 排列和组合的产生（有重集元素） .120
11.5 秦九韶算法..................122
11.6 进制转换（正整数） ...........123
11.7 高精度算法（压位存储）!.......123
11.8 快速幂! ....................128
11.9 表达式求值..................129
11.10 解线性方程组* ..............133
第十二单元 数论算法 ............. 135
12.1 同余的性质!.................135
12.2 最大公约数、最小公倍数!.......135
12.3 解不定方程 ax＋by＝c!* .......135
12.4 同余问题* ..................136
12.5 素数和素数表 ................136
12.6 分解质因数..................137
第十三单元 图与图论算法.......... 139
13.1 图的实现 ...................139
13.2 图的遍历 ...................141
13.3 连通性问题..................142
13.4 欧拉回路 [邻接矩阵] .........146
13.5 最小生成树（MST） ...........147
13.6 单源最短路问题（SSSP 问题） ...148
13.7 每两点间最短路问题（APSP 问题）!152
13.8 拓扑排序 ...................152
13.9 关键路径 ...................155
13.10 二分图初步.................157
13.11 小结......................160
第十四单元 STL 简介 ............. 164
14.1 STL 概述 ...................164
14.2 常用容器 ...................164
14.3 容器适配器..................170
14.4 常用算法 ...................171
14.5 迭代器 .....................175
14.6 示例：合并果子.............. 175
附录 A 思想和技巧 ............... 177
A.1 时间/空间权衡 ............... 177
A.2 试验、猜想及归纳 ............. 177
A.3 模型化 ..................... 177
A.4 随机化* .................... 178
A.5 动态化静态 .................. 178
A.6 前序和! .................... 179
A.7 状态压缩*................... 180
A.8 抽样测试法* ................. 182
A.9 离散化* .................... 183
A.10 Flood Fill* .............. 184
附录 B 调试 .................... 185
B.1 常见错误类型 ................ 185
B.2 调试过程.................... 185
B.3 调试功能.................... 185
B.4 符号 DEBUG 的应用 ............ 186
B.5 代码审查表 .................. 186
B.6 故障检查表 .................. 187
B.7 命令行和批处理*.............. 188
附录 C 竞赛经验和教训............ 192
C.1 赛前两星期 .................. 192
C.2 赛前 30 分钟................. 192
C.3 解题表 ..................... 193
C.4 测试数据.................... 195
C.5 交卷前 5 分钟 ................ 196
C.6 避免偶然错误 ................ 196
C.7 骗分 ....................... 197
附录 D 学习建议................. 198
D.1 学习方法.................... 198
D.2 学习能力.................... 198
D.3 关于清北学堂 ................ 198
附录 E 竞赛简介................. 199
E.1 从 NOIP 到 IOI............... 199
E.2 NOIP 简介 .................. 199
E.3 常用语 ..................... 201
E.4 第一次参加复赛…… ........... 202
附录 F NOIP 复赛知识点分布 ....... 204
附录 G 资料推荐................. 205
G.1 书籍 ....................... 205
G.2 网站 ....................... 205
参考文献 ....................... 206
计算机专业是朝阳还是夕阳？ ........ 207
杜子德在 CCF NOI2012 开幕式上的讲话 209
多数奥赛金牌得主为何难成大器 ...... 210
|