算法竞赛入门经典课件.pptx

算法竞赛入门经典,演讲人,2025-11-11,算法竞赛入门经典演讲人2025-11-11,01.,第1部分语言篇,02.,03.,目录,第2部分算法篇,第3部分竞赛篇,01.第1部分语言篇02.03.目录第2部分算法篇第3部,第1部分语言篇,01,Part One,第1部分语言篇01Part One,1程序设计入门,D,C,B,A,1.1算术表达式,1.2变量及其输入,1.3顺序结构程序设计,1.4分支结构程序设计,E,1.5小结与习题,1程序设计入门DCBA1.1算术表达式1.2变量及其输,1程序设计入门,1.5小结与习题,1.5.1数据类型实验1.5.2scanf输入格式实验1.5.3printf语句输出实验1.5.4测测你的实践能力1.5.5小结1.5.6上机练习,1程序设计入门1.5小结与习题1.5.1数据类型实验,2循环结构程序设计,2.2循环结构程序设计,2.4小结与习题,2.4.1输出技巧2.4.2浮点数陷阱2.4.364位整数2.4.4C+中的输入输出2.4.5小结2.4.6上机练习,56%Option 2,47%Option 4,2.1for循环,2.3文件操作,30%Option 3,23%Option 1,2循环结构程序设计2.2循环结构程序设计 2.4小结与,3数组和字符串,3.2字符数组,02,3.3最长回文子串,03,3.4小结与习题,04,3.1数组,01,3数组和字符串3.2字符数组023.3最长回文子串03,3数组和字符串,3.4小结与习题,3.4.1必要的存储量3.4.2用ASCII编码表示字符3.4.3补码表示法3.4.4重新实现库函数3.4.5字符串处理的常见问题,3数组和字符串3.4小结与习题3.4.1必要的存储量,3数组和字符串,3.4小结与习题,3.4.6关于输入输出3.4.7I/O的效率3.4.8小结3.4.9上机练习,3数组和字符串3.4小结与习题3.4.6关于输入输出,4函数和递归,01,4.1数学函数,4.2地址和指针,02,4.3递归,03,4.4本章小结,04,4函数和递归014.1数学函数4.2地址和指针024.,4函数和递归,4.1数学函数,4.1.1简单函数的编写4.1.2使用结构体的函数4.1.3应用举例,4函数和递归4.1数学函数4.1.1简单函数的编写,4函数和递归,4.2地址和指针,4.2.1变量交换4.2.2调用栈4.2.3用指针实现变量交换4.2.4初学者易犯的错误,4函数和递归4.2地址和指针4.2.1变量交换,4函数和递归,4.3递归,4.3.1递归定义4.3.2递归函数4.3.3C语言对递归的支持4.3.4段错误与栈溢出,4函数和递归4.3递归4.3.1递归定义,4函数和递归,4.4本章小结,4.4.1小问题集锦4.4.2小结,4函数和递归4.4本章小结4.4.1小问题集锦,第2部分算法篇,02,Part One,第2部分算法篇02Part One,5基础题目选解,5.1字符串,5.2高精度运算,5.5训练参考,5.4数学基础,5.3排序与检索,5基础题目选解5.1字符串5.2高精度运算5.5训练,5基础题目选解,5.1字符串,5.1.1WERTYU5.1.2TeX括号5.1.3周期串,5基础题目选解5.1字符串5.1.1WERTYU,5基础题目选解,5.2高精度运算,5.2.1小学生算术5.2.2阶乘的精确值5.2.3高精度运算类bign5.2.4重载bign的常用运算符,5基础题目选解5.2高精度运算5.2.1小学生算术,5基础题目选解,5.3排序与检索,5.3.16174问题5.3.2字母重排,5基础题目选解5.3排序与检索5.3.16174问题,5基础题目选解,5.4数学基础,5.4.1Cantor的数表5.4.2因子和阶乘5.4.3果园里的树5.4.4多少块土地,5基础题目选解5.4数学基础5.4.1Cantor的数,5基础题目选解,5.5训练参考,5.5.1黑盒测试5.5.2在线评测系统5.5.3推荐题目,5基础题目选解5.5训练参考5.5.1黑盒测试,6数据结构基础,D,6.4图,E,6.5训练参考,A,6.1栈和队列,B,6.2链表,C,6.3二叉树,6数据结构基础D6.4图E6.5训练参考A6.1栈和,6数据结构基础,6.1栈和队列,6.1.1卡片游戏6.1.2铁轨,6数据结构基础6.1栈和队列6.1.1卡片游戏,6数据结构基础,6.2链表,6.2.1初步分析6.2.2链式结构6.2.3对比测试6.2.4随机数发生器,6数据结构基础6.2链表6.2.1初步分析,6数据结构基础,6.3二叉树,6.3.1小球下落6.3.2层次遍历6.3.3二叉树重建,6数据结构基础6.3二叉树6.3.1小球下落,6数据结构基础,6.4图,6.4.1黑白图像6.4.2走迷宫6.4.3拓扑排序6.4.4欧拉回路,6数据结构基础6.4图6.4.1黑白图像,7暴力求解法,7.1简单枚举,A,7.2枚举排列,B,7.3子集生成,C,7.4回溯法,D,7.5隐式图搜索,E,7.6训练参考,F,7暴力求解法7.1简单枚举A7.2枚举排列B7.3子,7暴力求解法,7.1简单枚举,7.1.1除法7.1.2最大乘积7.1.3分数拆分7.1.4双基回文数,7暴力求解法7.1简单枚举7.1.1除法,7暴力求解法,7.2枚举排列,7.2.1生成1n的排列7.2.2生成可重集的排列7.2.3解答树7.2.4下一个排列,7暴力求解法7.2枚举排列7.2.1生成1n的排列,7暴力求解法,7.3子集生成,7.3.1增量构造法7.3.2位向量法7.3.3二进制法,7暴力求解法7.3子集生成7.3.1增量构造法,7暴力求解法,7.4回溯法,7.4.1八皇后问题7.4.2素数环7.4.3困难的串7.4.4带宽,7暴力求解法7.4回溯法7.4.1八皇后问题,7暴力求解法,7.5隐式图搜索,7.5.1隐式树的遍历7.5.2一般隐式图的遍历7.5.3八数码问题7.5.4结点查找表,7暴力求解法7.5隐式图搜索7.5.1隐式树的遍历,8高效算法设计,8.1算法分析初步,8.2再谈排序与检索,8.5训练参考,8.4贪心法,8.3递归与分治,8高效算法设计8.1算法分析初步8.2再谈排序与检索8,8高效算法设计,8.1算法分析初步,8.1.1渐进时间复杂度8.1.2上界分析8.1.3分治法8.1.4正确对待算法分析结果,8高效算法设计8.1算法分析初步8.1.1渐进时间复杂,8高效算法设计,8.2再谈排序与检索,8.2.1归并排序8.2.2快速排序8.2.3二分查找,8高效算法设计8.2再谈排序与检索8.2.1归并排序,8高效算法设计,8.3递归与分治,8.3.1棋盘覆盖问题8.3.2循环日程表问题8.3.3巨人与鬼8.3.4非线性方程求根8.3.5最大值最小化,8高效算法设计8.3递归与分治8.3.1棋盘覆盖问题,8高效算法设计,8.4贪心法,8.4.1最优装载问题8.4.2部分背包问题8.4.3乘船问题8.4.4选择不相交区间8.4.5区间选点问题8.4.6区间覆盖问题8.4.7Huffman编码,8高效算法设计8.4贪心法8.4.1最优装载问题,第3部分竞赛篇,03,Part One,第3部分竞赛篇03Part One,9动态规划初步,01,9.1数字三角形,02,9.2DAG上的动态规划,03,9.30-1背包问题,04,9.4递归结构中的动态规划,05,9.5集合上的动态规划,06,9.6训练参考,9动态规划初步019.1数字三角形029.2DAG上的,9动态规划初步,9.1数字三角形,9.1.1问题描述与状态定义9.1.2记忆化搜索与递推,9动态规划初步9.1数字三角形9.1.1问题描述与状态,9动态规划初步,9.2DAG上的动态规划,9.2.1DAG模型9.2.2最长路及其字典序9.2.3固定终点的最长路和最短路,9动态规划初步9.2DAG上的动态规划9.2.1DAG,9动态规划初步,9.30-1背包问题,9.3.1多阶段决策问题9.3.2规划方向9.3.3滚动数组,9动态规划初步9.30-1背包问题9.3.1多阶段决策,9动态规划初步,9.4递归结构中的动态规划,9.4.1表达式上的动态规划9.4.2凸多边形上的动态规划9.4.3树上的动态规划,9动态规划初步9.4递归结构中的动态规划9.4.1表达,9动态规划初步,9.5集合上的动态规划,9.5.1状态及其转移9.5.2隐含的阶段,9动态规划初步9.5集合上的动态规划9.5.1状态及其,10数学概念与方法,10.1数论初步,10.2排列与组合,10.4训练参考,10.3递推关系,10数学概念与方法10.1数论初步10.2排列与组合1,10数学概念与方法,10.1数论初步,10.1.1除法表达式10.1.2无平方因子的数10.1.3直线上的点10.1.4同余与模算术,10数学概念与方法10.1数论初步10.1.1除法表达,10数学概念与方法,10.2排列与组合,10.2.1杨辉三角与二项式定理10.2.2数论中的计数问题10.2.3编码与解码10.2.4离散概率初步,10数学概念与方法10.2排列与组合10.2.1杨辉三,10数学概念与方法,10.3递推关系,10.3.1汉诺塔10.3.2Fibonacci数列10.3.3Catalan数10.3.4危险的组合10.3.5统计n-k特殊集的数目,10数学概念与方法10.3递推关系10.3.1汉诺塔,11图论模型与算法,D,C,B,A,11.1再谈树,11.2最短路问题,11.3网络流初步,11.4进一步学习的参考,E,11.5训练参考,11图论模型与算法DCBA11.1再谈树11.2最短路,11图论模型与算法,11.1再谈树,11.1.1无根树转有根树11.1.2表达式树11.1.3最小生成树11.1.4并查集,11图论模型与算法11.1再谈树11.1.1无根树转有,11图论模型与算法,11.2最短路问题,11.2.1Dijkstra算法11.2.2稀疏图的邻接表11.2.3使用优先队列的Dijkstra算法11.2.4Bellman-Ford算法11.2.5Floyd算法,11图论模型与算法11.2最短路问题11.2.1Dij,11图论模型与算法,11.3网络流初步,11.3.1最大流问题11.3.2增广路算法11.3.3最小割最大流定理11.3.4最小费用最大流问题,11图论模型与算法11.3网络流初步11.3.1最大流,11图论模型与算法,11.4进一步学习的参考,11.4.1编程语言11.4.2数据结构11.4.3算法设计11.4.4数学11.4.5参赛指南,11图论模型与算法11.4进一步学习的参考11.4.1,附录A开发环境与方法,A.1命令行,A.2操作系统脚本编程入门,A.3编译器和调试器,A.4浅谈IDE,D,C,A,B,附录A开发环境与方法A.1命令行A.2操作系统脚本编程,附录A开发环境与方法,A.1命令行,A.1.1文件系统A.1.2进程A.1.3程序的执行A.1.4重定向和管道A.1.5常见命令,附录A开发环境与方法A.1命令行A.1.1文件系统,附录A开发环境与方法,A.2操作系统脚本编程入门,A.2.1Windows下的批处理A.2.2Linux下的Bash脚本A.2.3再谈随机数,附录A开发环境与方法A.2操作系统脚本编程入门A.2.1,附录A开发环境与方法,A.3编译器和调试器,A.3.1gcc的安装和测试A.3.2常见编译选项A.3.3gdb简介A.3.4gdb的高级功能,附录A开发环境与方法A.3编译器和调试器A.3.1gc,感谢聆听,2020,感谢聆听2020,