信息学竞赛教程（初级）

本书是专门为中小学生编写的一套信息学竞赛教材。作者根据中国计算机学会发布的《全国青少年信息学奥林匹克系列竞赛大纲》，把涉及的知识点按难度等级分成了初级篇、中级篇、高级篇三篇，对应三本教材，每本教材包含40章。本书是初级篇，包括基础算法专题、进制转换、位运算、编码问题、数列问题、高精度、字符串处理、时间和日期处理、数据结构专题、排序专题、搜索专题、动态规划专题、数论专题、组合数学专题、图论专题等内容。每章都是先介绍算法思想或基础知识，再结合经典的竞赛题目来讲解算法的实现。本书配备了完善的题库、课件、教学视频等资源，可以作为中小学信息学竞赛集训队的训练教材，也可以作为少儿编程培训机构的培训教材，还可以作为少儿编程等级考试和编程竞赛的辅导教材。

王桂平计算机科学与技术专业博士、副教授、硕士研究生导师。自2003年起从事大学生程序设计竞赛指导工作，带队参加过浙江省、重庆市、四川省、广东省大学生程序设计大赛、中国大学生程序设计大赛、国际大学生程序设计大赛、团体程序设计天梯赛、蓝桥杯全国软件和信息技术专业人才大赛等赛事，指导学生累计获得奖项100余项，省级奖项1000余项。出版了《C++趣味编程及算法入门》《C+编程与信息学竞赛数学基础》《GESP编程能力等级认证一本通(C++一级)》《图论算法理论、实现及应用》等多部著作；主持省部级教学研究项目5项，建设重庆市一流课程一门，以第一作者发表教学研究论文近20篇、科学研究论文30余篇（含SCI论文9篇、EI论文10篇），主持省部级科研项目3项，参与科研项目3项。兼任多所中小学信息学奥林匹克竞赛特聘教练。周祖松中学信息技术高级教师，全国信息学竞赛金牌指导教师，重庆市育才中学信息学竞赛总教练。重庆市基础教育教研项目评审专家库成员，重庆市九龙坡区九龙名师、九龙坡区中小学信息技术名师工作室主持人。中国计算机学会中小学计算机教育研讨会副主席。担任全国信息学竞赛指导教师培训讲师和冬令营授课讲师。指导学生参加全国信息学决赛（NOI）有8人获金牌，7人进入国家集训队，2人获国际初中生信息学竞赛金牌。100多人获全国青少年信息学奥林匹克联赛（NOIP）一等奖。万毅中学一级教师，重庆第一中学校信息科技教师及信息学竞赛教练，重庆市沙坪坝区新秀骨干教师，全国青少年信息学奥林匹克竞赛指导教师，国培计划（2023）中西部骨干教师项目优秀学员。陈胤戬重庆市育才中学信息学竞赛教练，曾获得NOI2020金牌，多次参加ICPC和CCPC区域赛并全部获得金牌，2023年参加GPLT团体程序设计天梯赛并荣获个人登顶先锋。

目 录第1章 基础算法1：枚举算法1.1 枚举算法的思想及实现要点1.2 案例1：积木1.3 案例2：自我数1.4 案例3：龙虎斗第2章 基础算法2：模拟算法2.1 模拟算法的思想及实现要点2.2 笛卡儿坐标系和网格中的坐标系2.3 案例1：醉酒的狱卒2.4 案例2：扫雷游戏2.5 案例3：螺旋矩阵第3章 基础算法3：递推和递归3.1 递推和递归3.2 案例1：数的计算3.3 案例2：整数划分问题3.4 案例3：三角形的个数3.5 函数及递归函数设计第4章 基础算法4：贪心算法4.1 贪心算法的思想4.2 案例1：活动安排问题4.3 贪心算法的基本要素4.4 0-1背包问题和部分背包问题4.5 案例2：公路4.6 案例3：纪念品分组第5章 基础算法5：分治法5.1 分治法的思想5.2 案例1：棋盘覆盖问题5.3 案例2：幂次方5.4 案例3：分形第6章 基础算法6：二分法及应用6.1 二分法6.2 二分查找6.3 二分答案6.4 C++中的二分查找函数6.5 案例1：复合单词6.6 案例2：垦田计划6.7 案例3：跳石头第7章 进制的思想及进制转换7.1 数位和计数单位7.2 进制及进制转换7.3 实现进制转换的库函数7.4 标准模板库中的位组(bitset)7.5 案例1：统计好数7.6 案例2：优秀的拆分7.7 案例3：回文数第8章 位运算及应用8.1 位运算8.2 位运算的应用8.3 案例1：关灯游戏8.4 案例2：格雷码8.5 案例3：动物园第9章 编码问题及处理9.1 从ASCII编码说起9.2 字符编码问题9.3 案例1：圆括号编码9.4 案例2：莫尔斯电码9.5 案例3：Vigenère密码第10章 数列问题及处理10.1 数列及相关问题10.2 等差数列和等比数列10.3 案例1：数列1, 1, 2, 1, 2, 310.4 案例2：中位数数列10.5 案例3：数列第11章 高精度1：高精度计算的基本原理11.1 高精度数11.2 用字符型数组或整型数组实现算术运算11.3 高精度计算原理11.4 高精度计算要点11.5 案例1：统计加法运算的进位次数11.6 案例2：skew二进制11.7 案例3：双塔问题第12章 高精度2：高精度数加减法和乘法12.1 高精度数的加减法和乘法12.2 高精度运算的压位处理12.3 案例1：高精度数的加法12.4 案例2：高精度数的乘法12.5 案例3：麦森数第13章 字符及字符串处理（1）13.1 字符串处理函数13.2 字符串类string13.3 字符转换13.4 案例1：ISBN13.5 案例2：解密13.6 案例3：打字纠错第14章 字符及字符串处理（2）14.1 回文字符串14.2 案例1：构造回文14.3 案例2：镜像回文14.4 案例3：回文日期第15章 字符及字符串处理（3）15.1 子串与子序列的处理15.2 案例1：字符串包含问题15.3 案例2：字符串的幂15.4 案例3：统计单词数第16章 时间和日期的处理16.1 时间和日期处理的相关问题16.2 案例1：相隔天数16.3 案例2：黑色星期五16.4 案例3：儒略日第17章 数据结构1：数组和向量17.1 数据结构基本概念17.2 标准模板库17.3 向量17.4 案例1：明明的随机数17.5 案例2：中位数17.6 案例3：公交换乘第18章 数据结构2：栈18.1 栈18.2 n个元素有多少种出栈顺序18.3 案例1：括号串匹配18.4 案例2：奇特的火车站18.5 案例3：表达式求值第19章 数据结构3：队列19.1 队列19.2 案例1：约瑟夫环问题19.3 案例2：海港19.4 案例3：等待时间第20章 数据结构4：集合20.1 数学上的集合20.2 STL中的集合20.3 案例1：第N个回文数20.4 案例2：集合的递归定义20.5 案例3：考勤刷卡第21章 数据结构5：用数组模拟链表21.1 数据结构的物理顺序和逻辑顺序21.2 线性数据结构和非线性数据结构21.3 顺序结构和链式结构21.4 线性表：顺序表和链表21.5 案例1：链表结点的物理/逻辑顺序21.6 用数组模拟链表21.7 案例2：好友关系21.8 案例3：队列安排第22章 数据结构6：树的概念及存储22.1 非线性数据结构——树22.2 图结构和树结构22.3 二叉树22.4 树和二叉树的存储22.5 二叉树的遍历22.6 案例1：二叉树深度22.7 案例2：新二叉树22.8 案例3：FBI树第23章 排序及排序函数的使用23.1 排序及排序算法23.2 排序的应用23.3 排序函数sort的用法23.4 案例1：快乐的蠕虫23.5 案例2：英文姓名排序23.6 案例3：图书馆管理员第24章 排序算法原理及应用24.1 归并排序算法24.2 快速排序算法24.3 案例1：求逆序对问题24.4 案例2：Freda的越野跑24.5 案例3：求第k小的数第25章 搜索1：深度优先搜索25.1 深度优先搜索的思想25.2 案例1：油田25.3 案例2：最大的泡泡串25.4 案例3：选数25.5 深度优先搜索技巧第26章 搜索2：广度优先搜索26.1 广度优先搜索的思想26.2 案例1：马走日26.3 案例2：电影系列之《预见未来》26.4 案例3：回家第27章 搜索3：搜索的剪枝优化27.1 搜索的剪枝优化27.2 案例1：骨头的诱惑27.3 案例2：小木棍27.4 案例3：棋盘第28章 DP1：动态规划的基本思路28.1 动态规划算法的引入——从数字网格说起28.2 动态规划算法的思想28.3 动态规划算法的4个要素28.4 案例1：数字网格28.5 动态规划算法的变形——备忘录方法28.6 案例2：单调回文分解28.7 案例3：最大子段和第29章 DP2：一维和二维动态规划29.1 一维和二维动态规划29.2 案例1：积木画29.3 案例2：最大的子矩阵和29.4 案例3：最大正方形的边长第30章 DP3：背包类型动态规划30.1 背包问题及求解算法30.2 案例1：0-1背包问题30.3 案例2：比谁猜得准30.4 案例3：砝码称重第31章 数论1：整除理论及应用31.1 自然数与整数31.2 整除31.3 筛选法求质数31.4 哥德巴赫猜想31.5 案例1：半质数31.6 案例2：筛选法求质数31.7 案例3：哥德巴赫猜想第32章 数论2：最大公约数理论及应用32.1 最大公约数、互质、最小公倍数32.2 带余数除法与辗转相除法32.3 最大公约数理论32.4 案例1：等差数列32.5 案例2：最大公约数和最小公倍数32.6 格点问题32.7 案例3：兔八哥与猎人第33章 数论3：唯一分解定理及应用33.1 唯一分解定理33.2 符号[x]，n!的分解式33.3 案例1：求标准质因数分解式33.4 案例2：正除数个数和正除数的和33.5 案例3：n!的标准质因数分解式第34章 数论4：同余理论及应用34.1 同余34.2 a对模m的逆34.3 同余类（剩余类）34.4 同余方程34.5 中国剩余定理34.6 案例1：各位数字全为1的数34.7 案例2：Niven数34.8 案例3：韩信点兵第35章 组合数学1：加法原理和乘法原理35.1 加法原理和乘法原理35.2 排列和组合公式35.3 全排列及排列的字典序35.4 生成序列全排列的函数35.5 案例1：网格路径35.6 案例2：产生数35.7 案例3：过河卒第36章 组合数学2：用DFS求解排列组合问题36.1 用DFS求解排列组合问题36.2 案例1：质数环问题36.3 案例2：方形硬币36.4 案例3：正方形第37章 图论1：图的基本概念和图的存储37.1 哥尼斯堡七桥问题37.2 小世界理论37.3 图的基本概念37.4 图的存储表示37.5 案例1：求顶点度数37.6 编程解题时灵活地存储图37.7 用向量数组实现邻接表并求顶点度数37.8 案例2：道路网络37.9 案例3：共同好友数第38章 图论2：图的深度优先搜索38.1 图的深度优先搜索38.2 图的深度优先搜索的实现38.3 案例1：红与黑38.4 案例2：七段码数码管38.5 用向量数组实现加权图的邻接表38.6 案例3：道路修建第39章 图论3：图的广度优先搜索39.1 图的广度优先搜索39.2 图的广度优先搜索的实现39.3 案例1：奇怪的电梯39.4 案例2：迷宫39.5 案例3：医院选址问题第40章 图论4：DAG和拓扑排序40.1 AOV网络和拓扑排序40.2 拓扑排序算法40.3 案例1：拓扑排序实现40.4 关于拓扑排序的进一步说明40.5 案例2：将所有元素排序40.6 案例3：最大食物链计数附录A 标识符命名规范与代码规范附录B 课程资源使用说明参考文献