第1页 / 共220页
第2页 / 共220页
第3页 / 共220页
第4页 / 共220页
第5页 / 共220页
第6页 / 共220页
第7页 / 共220页
第8页 / 共220页
noip史上最全复习资料！.doc
前 言
目 录
第一单元 C++语言基础
1.1 程序结构
(1) 程序框架
(2) 选择结构
(3) 循环结构
(4) goto语句
(5) C与C++的区别
1.2 数据类型
(1) 基本数据类型
(2) 变量与常量
(3) 数组
(4) 指针
(5) 引用
(6) 结构体
1.3 运算符
(1) 运算符的优先级
(2) 常用运算符的作用
(3) 真值表
(4) 类型强制转换
1.4 函数
(1) 定义和使用函数
(2) 传递实参
1.5 输入和输出!
(1) 使用标准输入/输出
(2) 使用流输入/输出
1.6 其他常用操作!
(1) 库函数
(2) 宏定义
1.7 字符串操作!
1.8 文件操作!
(1) 输入/输出重定向
(2) 文件流
(3) FILE指针
1.9 简单的算法分析和优化
(1) 复杂度
(2) 常用算法的时空复杂度
(3) 简单的优化方法
1.10 代码编辑器
第二单元 基础算法
2.1 经典枚举问题
(1) 韩信点兵
(2) 百鸡问题
(3) 求水仙花数
(4) 砝码称重
2.2 火柴棒等式
2.3 梵塔问题
2.4 斐波那契数列
(1) 递归
(2) 记忆化搜索
(3) for循环
2.5 常见的递推关系!
2.6 选择客栈
2.7 2k进制数
2.8 Healthy Holsteins
2.9 小结
第三单元 搜索
3.1 N皇后问题
(1) 深度优先搜索（DFS）
(2) 状态压缩*
3.2 走迷宫
(1) 预处理
(2) 深度优先搜索（DFS）
(3) 广度优先搜索（BFS）
3.3 8数码问题
(1) BFS
(2) 顺序化*
(3) 使用哈希表判重
3.4 埃及分数
3.5 Mayan游戏
3.6 预处理和优化
(1) 预处理
(2) 通用优化方法
(3) 剪枝
3.7 代码模板
(1) DFS（递归实现）!
(2) BFS!
(3) 迭代加深搜索
3.8 搜索题的一些调试技巧
3.9 小结
第四单元 贪心算法
4.1 装载问题
(1) 简单的装载问题
(2) 部分背包问题
(3) 乘船问题
4.2 区间问题
(1) 选择不相交区间
(2) 区间选点问题
(3) 区间覆盖问题
4.3 删数问题
4.4 工序问题
4.5 种树问题
4.6 马的哈密尔顿链
4.7 三值的排序
4.8 田忌赛马
4.9 小结
第五单元 分治算法
5.1 一元三次方程求解
5.2 快速幂
5.3 排序
(1) 快速排序
(2) 归并排序
(3) 求逆序对个数
5.4 最长非降子序列
5.5 循环赛日程表问题
5.6 棋盘覆盖
5.7 删除多余括号
5.8 聪明的质监员
5.9 模板
5.10 小结
第六单元 动态规划
6.1 导例：数字三角形
(1) 数据存储
(2) 递推
(3) 记忆化搜索——用递归代替递推
(4) 记录路径
(5) 使用滚动数组
(6) 非完美解法
6.2 区间问题：石子合并
(1) 环的处理方法
(2) 求解
(3) 能量项链
6.3 坐标问题
(1) 单向取数问题
(2) 变式问题
(3) 传纸条
6.4 背包问题
6.5 编号问题
(1) 最长非降子序列（LIS）
(2) 最长公共子序列（LCS）
6.6 递归结构问题
(1) 乘积最大
(2) 加分二叉树
6.7 DAG上的最短路径
(1) 特殊DAG的最短路径
(2) 关键工程
(3) 街道
6.8 树形动态规划*
(1) 苹果树
(2) 选课
6.9 状态压缩类问题：过河
6.10 Bitonic旅行
6.11 小结
第七单元 背包专题
7.1 部分背包问题
7.2 0/1背包问题!
(1) 二维数组表示
(2) 一维数组表示
(3) 一维之下的一个常数优化
(4) 初始化时的细节
7.3 完全背包问题
(1) 基本算法
(2) 更优的算法
7.4 多重背包问题
7.5 二维费用的背包问题
(1) 0/1背包的表示方法
(2) 限制物品总个数的0/1背包
(3) 二维费用的完全背包和多重背包问题
(4) 二维费用背包的另一种解法
7.6 分组的背包问题
7.7 有依赖的背包问题
7.8 泛化物品
7.9 混合背包问题
7.10 特殊要求
(1) 输出字典序最小的最优方案
(2) 求方案总数
(3) 最优方案的总数
(4) 求次优解、第K优解
7.11 背包问题的搜索解法
(1) 代码
(2) 预处理和剪枝
(3) 搜索还是DP
7.12 子集和问题
第八单元 排序算法
8.1 常用排序算法
(1) 使用STL算法!
(2) 快速排序!
(3) 归并排序
8.2 简单排序算法
(1) 插入排序!
(2) 选择排序!
(3) 冒泡排序!
8.3 线性时间排序
(1) 桶排序!
(2) 计数排序
(3) 基数排序*
8.4 使用二叉树的排序算法*
(1) 二叉树排序
(2) 堆排序
8.5 小结
第九单元 基本数据结构
9.1 线性表（顺序结构）
9.2 线性表（链式结构）
(1) 单链表!
(2) 静态链表
(3) 循环链表
(4) 双链表
(5) 将元素插入到有序链表中*
9.3 栈
(1) 栈的实现!
(2) DFS和栈
9.4 队列
(1) 顺序队列!
(2) 循环队列!
(3) BFS和队列
9.5 二叉树
(1) 二叉树的链表存储法!
(2) 完全二叉树的一维数组存储法!
(3) 二叉树的遍历!
(4) 二叉树重建
(5) 求二叉树的直径*
9.6 并查集!
(1) 并查集的实现
(2) 团伙
(3) 银河英雄传说
(4) 可爱的猴子
9.7 小结
第十单元 查找与检索
10.1 顺序查找
10.2 二分查找!
(1) 普通的二分查找（非递归）
(2) 二分查找求下界
(3) 二分查找求上界
10.3 查找第k小元素!
10.4 二叉排序树
(1) 二叉排序树
(2) 插入一个元素
(3) 删除一个元素*
(4) 查找一个元素
10.5 堆和优先队列*
(1) 堆
(2) 插入一个元素
(3) 插入一组元素
(4) 删除一个元素*
(5) 查找一个元素*
10.6 哈夫曼（Huffman）树
(1) 建立哈夫曼树
(2) 哈夫曼编码
10.7 哈希（Hash）表
(1) 实现
(2) 散列函数
(3) 开散列方法
(4) 闭散列方法（开地址方法）
(5) 删除*
第十一单元 数学基础
11.1 组合数学
(1) 加法定理与乘法原理
(2) 排列与组合
(3) 鸽巢原理（抽屉原理）
(4) 容斥原理
11.2 组合数的计算!
(1) 使用加法递推——O（n2）
(2) 使用乘法递推——O（n）
11.3 排列和组合的产生（无重集元素）
(1) 全排列
(2) 一般组合
(3) 全组合
(4) 由上一排列产生下一排列
(5) 由上一组合产生下一组合
11.4 排列和组合的产生（有重集元素）
(1) 全排列
(2) 全组合
11.5 秦九韶算法
11.6 进制转换（正整数）
(1) 十进制变N进制
(2) N进制变十进制
11.7 高精度算法（压位存储）!
(1) 定义
(2) 赋值和初始化
(3) 比较运算符
(4) 四则运算
(5) 输入/输出
11.8 快速幂!
(1) 递归算法
(2) 非递归算法
11.9 表达式求值
(1) 模拟
(2) 分治
(3) 表达式树
11.10 解线性方程组*
(1) 列主元
(2) 全主元
第十二单元 数论算法
12.1 同余的性质!
12.2 最大公约数、最小公倍数!
12.3 解不定方程ax＋by＝c!*
12.4 同余问题*
(1) 同余式
(2) 同余式组
12.5 素数和素数表
(1) 素数定理
(2) 判断素数!
(3) 筛法产生素数表!
12.6 分解质因数
(1) 分解质因数
(2) 除数函数
(3) 欧拉函数
第十三单元 图与图论算法
13.1 图的实现
(1) 邻接矩阵!
(2) 边目录!
(3) 邻接表（链表）!
(4) 邻接表（静态数组）!
(5) 邻接表（STL）!
13.2 图的遍历
(1) 深度优先遍历（递归）! [邻接矩阵]
(2) 广度优先遍历! [邻接矩阵]
13.3 连通性问题
(1) 两个小问题
(2) 强连通分量（Kosaraju算法） [邻接矩阵]
(3) 强连通分量（Tarjan算法） [邻接表]
(4) 强连通分量（Gabow算法） [邻接表]
(5) 有向图的传递闭包（Floyd-Warshall算法） [邻接矩阵]
13.4 欧拉回路 [邻接矩阵]
13.5 最小生成树（MST）
(1) Prim算法 [邻接矩阵]
(2) Kruskal算法! [边目录]
13.6 单源最短路问题（SSSP问题）
(1) Dijkstra算法! [邻接矩阵]
(2) 使用优先队列的Dijkstra算法* [邻接表]
(3) Bellman-Ford算法 [边目录]
(4) SPFA! [邻接表]
13.7 每两点间最短路问题（APSP问
13.8 拓扑排序
(1) DFS! [邻接矩阵]
(2) 模拟堆栈# [邻接矩阵]
(3) 使用辅助队列! [邻接矩阵]
13.9 关键路径
(1) 对DAG求关键路径 [邻接矩阵/邻接表]
(2) 对拓扑序列求关键路径 [邻接矩阵]
13.10 二分图初步
(1) 二分图的判定 [邻接表]
(2) 匹配的概念
(3) 匈牙利算法（DFS） [邻接矩阵]
(4) 棋盘
(5) 不要早恋
13.11 小结
第十四单元 STL简介
14.1 STL概述
14.2 常用容器
(1) STL容器共同的操作!
(2) vector（矢量）
(3) deque（双端队列）
(4) list（表）
(5) 关联容器
(6) 功效表
(7) 字符串
14.3 容器适配器
(1) queue（队列）!
(2) stack（堆栈）!
(3) priority_queue（优先队列）!
14.4 常用算法
(1) for_each（遍历）
(2) 非变动性算法
(3) 变动性算法
(4) 移除性算法
(5) 变序性算法
(6) 排序算法!
(7) 有序区间算法
(8) 集合算法
(9) 堆算法
(10) 数值算法
14.5 迭代器
14.6 示例：合并果子
附录A 思想和技巧
A.1 时间/空
(1) 时间换空间
(2) 空间换时间
A.2 试验、猜
A.3 模型化
A.4 随机化*
(1) 随机化搜索
(2) 随机＋贪心
A.5 动态化静
A.6 前序和!
(1) 区间求和
(2) 带条件的区间求和
(3) 最大子矩阵和
A.7 状态压缩
(1) 集合的表示方法
(2) 集合的交、并、补、差
(3) 集合中的元素
(4) 统计*
(4) 其他*
A.8 抽样测试
(1) 等价表达式
(2) Miller-Rabin素性测试*
A.9 离散化*
A.10 Flo
附录B 调试
B.1 常见错误
B.2 调试过程
B.3 调试功能
B.4 符号DE
B.5 代码审查
B.6 故障检查
B.7 命令行和
(1) 常用命令
(2) 简易对拍器（Windows）
(3) 简易对拍器（Linux）
(4) g++和gdb
附录C 竞赛经验和教训
C.1 赛前两星
C.2 赛前30
C.3 解题表
C.4 测试数据
C.5 交卷前5
C.6 避免偶然
C.7 骗分
附录D 学习建议
D.1 学习方法
D.2 学习能力
D.3 关于清北
附录E 竞赛简介
E.1 从NOI
E.2 NOIP
(1) NOIP时间和题型
(2) 初赛内容与要求
(3) 复赛内容与要求
E.3 常用语
E.4 第一次参
附录F NOIP复赛知识点分布
附录G 资料推荐
G.1 书籍
G.2 网站
参考文献
计算机专业是朝阳还是夕阳？
杜子德在CCF NOI2012开幕式上的讲话
多数奥赛金牌得主为何难成大器
NOIP 复习资料
（C++版）
主 编
葫芦岛市一高中 李思洋
完成日期
2012 年 8 月 27 日
前 言
0
前 言
前 言
有一天，我整理了 NOIP 的笔记，并收集了一些经典算法。不过我感觉到笔记比较凌乱，并且有很多需要
修改和补充的内容，于是我又搜集一些资料，包括一些经典习题，在几个月的时间内编写出了《NOIP 复习资
料》。
由于急于在假期之前打印出来并分发给同校同学（我们学校既没有竞赛班，又没有懂竞赛的老师。我们大
家都是自学党），《NOIP 复习资料》有很多的错误，还有一些想收录而未收录的内容。
在“减负”的背景下，暑期放了四十多天的假。于是我又有机会认真地修订《NOIP 复习资料》。
我编写资料的目的有两个：总结我学过（包括没学会）的算法、数据结构等知识；与同学共享 NOIP 知识，
同时使我和大家的 RP++。
大家要清醒地认识到，《NOIP 复习资料》页数多，是因为程序代码占了很大篇幅。这里的内容只是信息
学的皮毛。对于我们来说，未来学习的路还很漫长。
基本假设
作为自学党，大家应该具有以下知识和能力：
① 能够熟练地运用 C++语言编写程序（或熟练地把 C++语言“翻译”成 Pascal 语言）；
② 能够阅读代码，理解代码含义，并尝试运用；
③ 对各种算法和数据结构有一定了解，熟悉相关的概念；
④ 学习了高中数学的算法、数列、计数原理，对初等数论有一些了解；
⑤ 有较强的自学能力。
代码约定
N、M、MAX、INF 是事先定义好的常数（不会在代码中再次定义，除非代码是完整的程序）。N、M、MAX
针对数据规模而言，比实际最大数据规模大；INF 针对取值而言，是一个非常大，但又与 int 的最大值有一定
差距的数，如 100000000。
对于不同程序，数组下标的下限也是不同的，有的程序是 0，有的程序是 1。阅读程序时要注意。
阅读顺序和方法
没听说过 NOIP，或对 NOIP 不甚了解的同学，应该先阅读附录 E，以加强对竞赛的了解。
如果不能顺利通过初赛，你就应该先补习初赛知识。这本《NOIP 复习资料》总结的是复赛知识。
如果没有学过 C++语言，应该先选择一本 C++语言教材。一般情况下，看到“面向对象编程”一章的前一
页就足够了（NOIP 不用“面向对象编程”，更不用摆弄窗口对话框）。
附录 G 介绍了一些书籍和网站。你应该选择一本书，认真地学习。再选择一个网站，作为练习的题库。
第一单元对竞赛中常用的操作和简单的算法分析进行了总结，算作对 C++语言的巩固。同时，阅读这一单
元之后，你应该选择一个合适的 C++代码编辑器。
第二到第六单元介绍了竞赛常用的算法。阅读每一章时，应该先阅读“小结”——名曰“小结”，实际上
是“导读”。
这五个单元除了经典习题，还有某些思想和算法的具体实现方法。这些信息可能在明处，也可能在暗处，
阅读时要注意挖掘和体会。如果有时间，应该在不看解析和代码的前提下独立完成这些题。
第七单元是第六单元的一个部分，由于它的内容来自《背包九讲》，所以单独放在一个单元。
从第八单元开始，到第十三单元，基本上就没有习题了。换句话说，该“背课文”了。
第八单元介绍了常用的排序算法。你可以有选择地学习，但一定要掌握“STL 算法”和“快速排序”。
第九单元介绍了基本数据结构，你一定要掌握第九单元前五小节的内容（本单元也有应该优先阅读的“小
结”）。有余力的话，第六小节的并查集也应该掌握。
1
前 言
第十单元介绍了与查找、检索有关的数据结构和算法。你也可以有选择地学习。
第十一单元与数学有关。数学对于信息学来说具有举足轻重的地位。标有“！”的应该背下来，至于其他
内容，如果出题，你应该能把它解决。
第十二单元仍与数学有关。
第十三单元是图论。学习时要先阅读“小结”，把概念弄清楚。之后要掌握图的实现方法。接下来要掌握
一些经典图论算法：Kruskal 算法、Dijkstra 算法、SPFA、Floyd 算法、拓扑排序。
附录 F 总结了 2004 年以来 NOIP 考察的知识点，可以作为选择性学习的参考。
在学习算法和数据结构的同时，应该阅读和学习附录 A。
如果你还有余力，你应该学习第十四单元。第十四单元的内容不是必须要掌握的，但是一旦学会，可以发
挥 C++语言的优势，降低编程复杂度。
临近竞赛时，应该阅读附录 B 和附录 C，以增加经验，减少失误。
面临的问题
1. 这是复赛复习资料——需要有人能用心总结、整理初赛的知识，就像这份资料一样。
2. 潜在的问题还是相当多的，只是时间不够长，问题尚未暴露。
3. 部分代码缺少解说，或解说混乱。
4. 个人语文水平较差，《资料》也是如此。
5. 没有对应的 Pascal 语言版本。
如果有人能为 P 党写一个 Pascal 版的 STL，他的 RP 一定会爆增！
6. 希望有人能用 LATEX整理《资料》，并以自由文档形式发布。
最后，欢迎大家以交流、分享和提高为目的修改、复制、分发本《资料》，同时欢迎大家将《资料》翻译
成 Pascal 语言版供更多 OIer 阅读！
谢谢大家的支持！
葫芦岛市一高中 李思洋
2012 年 8 月 27 日
2
目 录
目 录
标题上的符号：
1. !：表示读者应该熟练掌握这些内容，并且在竞赛时能很快地写出来。换句话说就是应该背下来。
2. *：表示内容在 NOIP 中很少涉及，或者不完全适合 NOIP 的难度。
3. #：表示代码存在未更正的错误，或算法本身存在缺陷。
前 言 ............................ 1
目 录 ............................ I
第一单元 C++语言基础 .............. 1
1.1 程序结构 ...................... 1
1.2 数据类型 ...................... 4
1.3 运算符 ........................ 6
1.4 函数 .......................... 8
1.5 输入和输出! ....................9
1.6 其他常用操作! ................. 10
1.7 字符串操作! ...................13
1.8 文件操作! .................... 13
1.9 简单的算法分析和优化 ........... 14
1.10 代码编辑器 ...................16
第二单元 基础算法 ................ 17
2.1 经典枚举问题 .................. 17
2.2 火柴棒等式 ....................18
2.3 梵塔问题 ..................... 19
2.4 斐波那契数列 .................. 19
2.5 常见的递推关系! ............... 20
2.6 选择客栈 ..................... 22
2.7 2k 进制数 ..................... 23
2.8 Healthy Holsteins ........... 24
2.9 小结 .........................25
第三单元 搜索 ................... 27
3.1 N 皇后问题 .................... 27
3.2 走迷宫 ....................... 29
3.3 8 数码问题 .................... 31
3.4 埃及分数 ..................... 34
3.5 Mayan 游戏 ................... 36
3.6 预处理和优化 .................. 40
3.7 代码模板 ..................... 41
3.8 搜索题的一些调试技巧 ........... 43
3.9 小结 .........................44
第四单元 贪心算法 ................ 47
4.1 装载问题 ..................... 47
4.2 区间问题 ..................... 47
4.3 删数问题 ..................... 48
4.4 工序问题 ..................... 48
4.5 种树问题 ..................... 48
4.6 马的哈密尔顿链 ................ 48
4.7 三值的排序 ....................50
4.8 田忌赛马 ..................... 51
4.9 小结 .........................51
第五单元 分治算法 ................ 52
5.1 一元三次方程求解 ...............52
5.2 快速幂 ....................... 52
5.3 排序 .........................52
5.4 最长非降子序列 ................ 54
5.5 循环赛日程表问题 ...............54
5.6 棋盘覆盖 ..................... 55
5.7 删除多余括号 .................. 56
5.8 聪明的质监员 .................. 57
5.9 模板 .........................59
5.10 小结 ........................60
第六单元 动态规划 ................ 61
6.1 导例：数字三角形 ...............61
6.2 区间问题：石子合并 ............. 64
6.3 坐标问题 ..................... 66
6.4 背包问题 ..................... 68
6.5 编号问题 ..................... 68
6.6 递归结构问题 .................. 69
6.7 DAG 上的最短路径 ...............72
6.8 树形动态规划* ................. 73
6.9 状态压缩类问题：过河 ........... 75
6.10 Bitonic 旅行 ................ 77
6.11 小结 ........................78
第七单元 背包专题 ................ 79
7.1 部分背包问题 .................. 79
7.2 0/1 背包问题! ................. 79
7.3 完全背包问题 .................. 80
7.4 多重背包问题 .................. 80
7.5 二维费用的背包问题 ............. 81
7.6 分组的背包问题 ................ 82
7.7 有依赖的背包问题 ...............82
7.8 泛化物品 ..................... 82
7.9 混合背包问题 .................. 83
7.10 特殊要求 .................... 83
7.11 背包问题的搜索解法 ............ 84
7.12 子集和问题 ...................85
第八单元 排序算法 ................ 86
8.1 常用排序算法 .................. 86
8.2 简单排序算法 .................. 88
8.3 线性时间排序 .................. 89
8.4 使用二叉树的排序算法* .......... 90
8.5 小结 .........................91
第九单元 基本数据结构 .............92
I
目 录
9.1 线性表（顺序结构） ............. 92
9.2 线性表（链式结构） ............. 92
9.3 栈 .......................... 94
9.4 队列 .........................95
9.5 二叉树 ....................... 96
9.6 并查集! ..................... 100
9.7 小结 ........................103
第十单元 查找与检索 ............. 105
10.1 顺序查找 ................... 105
10.2 二分查找! .................. 105
10.3 查找第 k 小元素! ............. 106
10.4 二叉排序树 ..................107
10.5 堆和优先队列* ............... 109
10.6 哈夫曼（Huffman）树 ......... 111
10.7 哈希（Hash）表 ..............112
第十一单元 数学基础 ............. 117
11.1 组合数学 ................... 117
11.2 组合数的计算! ............... 118
11.3 排列和组合的产生（无重集元素）! 118
11.4 排列和组合的产生（有重集元素） .121
11.5 秦九韶算法 ..................123
11.6 进制转换（正整数） ........... 124
11.7 高精度算法（压位存储）! .......124
11.8 快速幂! .................... 129
11.9 表达式求值 ..................130
11.10 解线性方程组* .............. 134
第十二单元 数论算法 ............. 136
12.1 同余的性质! .................136
12.2 最大公约数、最小公倍数! .......136
12.3 解不定方程 ax＋by＝c!* .......136
12.4 同余问题* .................. 137
12.5 素数和素数表 ................ 137
12.6 分解质因数 ..................138
第十三单元 图与图论算法 .......... 140
13.1 图的实现 ................... 140
13.2 图的遍历 ................... 142
13.3 连通性问题 ..................143
13.4 欧拉回路 [邻接矩阵] ......... 147
13.5 最小生成树（MST） ........... 148
13.6 单源最短路问题（SSSP 问题） ... 149
13.7 每两点间最短路问题（APSP 问题）!153
13.8 拓扑排序 ................... 153
13.9 关键路径 ................... 156
13.10 二分图初步 .................158
13.11 小结 ......................161
第十四单元 STL 简介 ............. 165
14.1 STL 概述 ................... 165
14.2 常用容器 ................... 165
14.3 容器适配器 ..................171
14.4 常用算法 ................... 172
14.5 迭代器 ..................... 176
II
14.6 示例：合并果子 .............. 176
附录 A 思想和技巧 ............... 178
A.1 时间/空间权衡 ................ 178
A.2 试验、猜想及归纳 ..............178
A.3 模型化 ...................... 178
A.4 随机化* ..................... 179
A.5 动态化静态 ...................179
A.6 前序和! ..................... 180
A.7 状态压缩* ................... 181
A.8 抽样测试法* ..................183
A.9 离散化* ..................... 184
A.10 Flood Fill* ............... 185
附录 B 调试 .................... 186
B.1 常见错误类型 ................. 186
B.2 调试过程 .................... 186
B.3 调试功能 .................... 186
B.4 符号 DEBUG 的应用 .............187
B.5 代码审查表 ...................187
B.6 故障检查表 ...................188
B.7 命令行和批处理* .............. 189
附录 C 竞赛经验和教训 ............ 193
C.1 赛前两星期 ...................193
C.2 赛前 30 分钟 ..................193
C.3 解题表 ...................... 194
C.4 测试数据 .................... 196
C.5 交卷前 5 分钟 ................. 197
C.6 避免偶然错误 ................. 197
C.7 骗分 ........................198
附录 D 学习建议 ................. 199
D.1 学习方法 .................... 199
D.2 学习能力 .................... 199
D.3 关于清北学堂 ................. 199
附录 E 竞赛简介 ................. 200
E.1 从 NOIP 到 IOI ............... 200
E.2 NOIP 简介 ................... 200
E.3 常用语 ...................... 202
E.4 第一次参加复赛…… ............ 203
附录 F NOIP 复赛知识点分布 ....... 206
附录 G 资料推荐 ................. 207
G.1 书籍 ........................207
G.2 网站 ........................207
参考文献 ....................... 208
计算机专业是朝阳还是夕阳？ ........ 209
杜子德在 CCF NOI2012 开幕式上的讲话 211
多数奥赛金牌得主为何难成大器 .......212
第一单元 C++语言基础
第一单元 C++语言基础
1.1 程序结构
(1) 程序框架
注释：注释有两种，一种是“//”，另一种是“/* … */”。“//”必须单独放置一行，或代码所在行
的后面；而“/*”、“*/”成对存在，可以插入到代码的任意位置。
引用头文件：在代码开头写“#include <头文件名>”。如果想引用自己的头文件，需要把尖括号（表
示只从系统目录搜索头文件）换成双引号（表示先从 cpp 所在文件夹搜索，然后再到系统文件夹搜索）。
命名空间：很多 C++的东西都要引用 std 命名空间，所以代码中会有“using namespace std;”。
main()：所有程序都要从 main()开始。
在所有的算法竞赛中，main()的返回值必须是 0，否则视为程序异常结束，得分为 0 分。
语句和语句块：
1. 语句：一般情况下，一条语句要用一个分号“;”结束。为了美观和可读性，可以把一条语句扩展成
几行，也可以把多个语句写到同一行上。
2. 语句块：用“{”和“}”包围的代码是语句块。无论里面有多少代码，在原则上，语句块所在的整体
都视为一条语句。
(2) 选择结构
1. if 语句：if 表示判断。如果条件为真，就执行接在 if 后的语句（语句块），否则执行 else 后的语句（语
句块）。如果没有 else，就直接跳过。if 有以下几种格式：
// 如果条件成立，就执行if后面的语句或语句块。
if (条件)
语句或语句块
// 如果条件成立，就执行if后面的A，否则执行B。
// 实际上，这是if语句内的if语句，即if的嵌套。所以else和if中间要有空格。
if (条件)
语句或语句块A
else
语句或语句块B
if (条件1)
语句或语句块A
else if (条件2)
语句或语句块B
……
else
语句或语句块N
2. switch 语句：switch 表示选择。它根据条件的不同取值来执行不同的语句。格式如下：
switch (表达式)
{
case 值1:
代码段A
break;
case 值2:
代码段B
break;
1
第一单元 C++语言基础
……
default:
代码段N
break;
};
如果表达式的值是值 1，就执行代码段 A；如果表达式的值是值 2，就执行代码段 B……否则执行代码段 N。
注意：
如果不使用 break，那么紧随其后的 case 部分代码也会被执行，直到遇到 break 或 switch 语句
default 一部分可以省略。
结束为止！
switch 结尾要有一个分号。
3. if、switch 都可以嵌套使用。
【问题描述】输入一个日期，判断它所在年份是否为闰年，并输出所在月份的天数。闰年的判断方法：四年一
闰，百年不闰，四百年又闰。
int year,month,day;
bool b=false;
cin>>year>>month>>day;
// 判断是否为闰年
if (n%400==0)
else if (n%100!=0 && n%4==0)
b=true;
b=true;
if (b)
else
cout<
第一单元 C++语言基础
2. do…while 语句：如果条件成立，就继续循环，直到条件不成立为止。它与 while 的最大区别在于，do…
while 循环中的语句会被执行至少一次，而 while 中的语句可能一次都没有被执行。格式如下：
do
{
循环体
}
while (条件);
4. for 语句：for 分四部分，有初始条件、继续循环的条件、状态转移的条件和循环体。格式如下：
for (初始条件; 继续循环的条件; 状态转移的条件)
// 注意分号
循环体
转换成 while 循环，即：
初始条件
while (继续循环的条件)
{
循环体
状态转移
for 后三个条件不是必需的，可以省略不写，但分号必须保留。
5. 在循环语句内部使用 break，可以跳出循环；使用 continue，可以忽略它后面的代码，马上进入下一轮
循环。
注意，这两个语句只对它所在的一层循环有效。
6. 写 for 循环时，一定要注意：
不要把计数器的字母打错，尤其是在复制/粘贴一段代码的时候。
根据算法要明确不等号是“<”、“>”，还是“<=”、“>=”。
逆序循环时，不要把自减“--”写成自增“++”！
【问题描述】输入 n，输出 n!（n!＝1×2×3×4×……×n）。结果保证小于 long long 的范围。当输入值
为负数时结束程序。
int n;
long long r=1;
cin>>n;
while (n>-1)
{
}
}
r=1;
for (int i=1; i<=n; i++)
r*=i;
cout<>n;
(4) goto 语句
然后才能 goto 那个标签。
goto 语句用于无条件跳转。要想跳转，首先要定义标签（在代码开头的一段标识符，后面紧跟冒号），
很多教程不提倡使用无条件跳转，因为它破坏了程序结构，还容易给代码阅读者带来麻烦。不过，这不代
表 goto 没有使用价值。goto 的一个用途是跳出多层循环：
for (int i=0; i<9; i++)
for (int j=0; j<9; j++)
3
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
