ACM培训教学讲解课件

ACM培训输入输出处理需要掌握的知识参考资料ACM培训1常用术语ICPC(InternationalCollegiateProgrammingContest)国际大学生程序设计竞赛AC(Accepted)程序通过WA(WrongAnswer)错误的答案(读做“哇”)常用术语ICPC(InternationalColleg2PE(PresentationError)输出格式错误RE(RuntimeError)程序执行错误(常见于数组溢出、递归层数太多.)CE(CompileError)编译错误MLE(MemoryLimitExceeded)内存超界(正式比赛没有内存限制，但如果用太多可能RE)PE(PresentationError)输出格式错误3TLE(TimeLimitExceed)程序超时错误(死循环或算法有问题)OLE(OutputLimitExceed)输出超界(一般不太常见，除非你输出了超过1024K.)TLE(TimeLimitExceed)程序超时错误4DP(DynamicProgramming)动态编程，动态规划DFS(DepthFirstSearch)深度优先搜索BFS(BreadthFirstSearch)宽度/广度优先搜索LCS(LongestCommonSubsequence)最长公共子串DP(DynamicProgramming)动态编程，5输入输出C:scanf速度快printf格式容易控制C+:cin使用简单,自动识别类型cout格式控制较麻烦数据规模较大时,推荐(必须)使用scanf以避免超时(TLE)输入输出C:6输入输出cout:带缓冲输出带缓冲输出printf:不带缓冲输出不带缓冲输出C和C+的输入输出混合使用输入输出cout:带缓冲输出7至于cout的缓存问题，五种情况会刷缓冲:n（我试下来是要刷的）endlflush缓冲区满程序结束至于cout的缓存问题，五种情况会刷缓冲:8输入输出#include#include int main()for(int j=0;j5;j+)coutj=;printf(%dn,j);return 0;j=0j=1j=2j=3j=401234j=j=j=j=j=输入输出#includej=009输入输出scanf输入格式%d%lld%c%s%lf对每种格式搞清楚一个重要问题是否自动跳过前导空白？什么是空白：空格，TAB，回车输入输出scanf10输入输出%d%lld%lf自动扫描前导空格比如：读入5个整数到A5输入文件中，数的排布是这个样子35267899206不管它，直接5次%dfor(inti=0;in;for(i=0;in&n!=0).2.输入不说明有多少个InputBlock,但以某个特殊输173.输入不说明有多少个InputBlock,以EOF为结束标志while(scanf(%d%d,&a,&b)!=EOF).while(cinab).3.输入不说明有多少个InputBlock,以EOF为结束184.输入是一整行的字符串的charbuf255;gets(buf);charbuf255;cin.getline(buf,255);4.输入是一整行的字符串的charbuf255;19输出部分：1.一个InputBlock对应一个OutputBlock，OutputBlock之间没有空行.printf(%dn,ans);.coutansendl;.输出部分：1.一个InputBlock对应一个Outpu20 2.一个InputBlock对应一个OutputBlock，OutputBlock之间有空行。intcasenum=0;.if(casenum+)putchar(n);.printf(%dn,ans);intcasenum=0;.if(casenum+)coutendl;.coutansendl;2.一个InputBlock对应一个OutputBlo213.一个InputBlock对应一个OutputBlock，每个OutputBlock之后都有空行。.printf(%dnn,ans);.coutansendlendl;.其他说明：1.EOF是一个标志（常量），不是字符串EOF，用键盘的输入方法是Ctrl+Z2.最好不要把C和C+的输入输出语句混着用，会造成一些莫名其妙的问题3.我个人倾向于使用纯C的输入输出，因为方便且速度快。3.一个InputBlock对应一个OutputBloc22关于重定向操作当程序要输入的内容很多时，从文件读入的操作变得非常重要,特别是需要调试时，这样可以避免你反复的从键盘敲入重复的内容。使用标准输入语句,可以使用重定向命令行输入命令:Test.exeout.dat关于重定向操作23最好不要进行函数声明变量定义在使用之前避免for(inti=0;in)考虑输入intmain()26例子intmain()intn,res;while(cinn)res=1;for(inti=2;i=n;i+)res*=i;coutresendl;Wrong AnswerWrong Answer例子intmain()WrongAnswer27FactorialTimeLimit:1000MSMemoryLimit:65536KDescription Caculaten!.Input Theinputshouldconsistofaseriesofcases.Ineverycasethereshouldbeaninteger,n(nislessthan21).Onelinepercase.Output Foreachcaseyoushouldoutputthethevalueofn!.Sample Input 23Sample Output 2620!=24329000Factorial20!=28Int32位取值范围是-2147483648214748364720!=2432900020-2102132736Int32位20!=2029类似问题:数据范围:决定使用什么类型数据规模:决定开多大的数组#defineMAX10005宜大不宜小类似问题:30注意事项三个方向：Algorithm（算法）Math（数学）Realization（实现）三种能力：EnglishReadingSelf-learningTeamwork注意事项三个方向：31需要哪些知识不完全列表不完全列表排序算法（平方排序算法的应用，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）数论（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余方程，中国剩余定理）指针（链表，搜索判重，邻接表，开散列，二叉树的表示，多叉树的表示）按位运算（and，or，xor，shl，shr，一些应用）图论（图论模型的建立，平面图，欧拉公式与五色定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最小生成树的三种算法，最短路的三种算法，标号法，差分约束系统，验证二分图，Konig定理，匈牙利算法，KM算法，稳定婚姻系统，最大流算法，最小割最大流定理，最小费用最大流算法）计算几何（平面解几及其应用，向量，点积及其应用，叉积及其应用，半平面相交，求点集的凸包，最近点对问题，凸多边形的交，离散化与扫描）数据结构（广度优先搜索，验证括号匹配，表达式计算，递归的编译，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏树，斜堆，二项堆，二叉查找树，AVL，Treap，Splay，静态二叉查找树，2-d树，线段树，二维线段树，矩形树，Trie树，块状链表）组合数学（排列与组合，鸽笼原理，容斥原理，递推，Fibonacci数列，Catalan数列，Stirling数，差分序列，生成函数，置换，Polya原理）概率论（简单概率，条件概率，Bayes定理，期望值）矩阵（矩阵的概念和运算，二分求解线性递推方程，多米诺骨牌棋盘覆盖方案数，高斯消元）字符串处理（KMP，后缀树，有限状态自动机，Huffman编码，简单密码学）动态规划（单调队列，凸完全单调性，树型动规，多叉转二叉，状态压缩类动规，四边形不等式）博奕论（Nim取子游戏，博弈树，Shannon开关游戏）搜索（A*，ID，IDA*，随机调整，遗传算法）微积分初步（极限思想，导数，积分，定积分，立体解析几何）需要哪些知识不完全列表32如何获取知识读书读书算法导论(IntroductiontoAlgorithms)组合数学数据结构计算机算法设计与分析如何获取知识读书33如何获取知识读论文读论文历年国家集训队论文(中学生的论文)读程序读程序用批判+学习的眼光去读别人的程序读论文读论文历年国家集训队论文(中学生的论文)网络资料网络资料聚宝盆(博客)如何获取知识读论文34实践篇写算法写算法看书,读论文等的过程中,自己动手把算法实现做题做题如数学一样,是做出来的,不是想出来的动手无论你是想做好ACM训练还是想学好编程请多动手写程序这是唯一的捷径实践篇写算法35有目的的编程提高比较大现在大家处于初级阶段巩固各种基础算法针对特定的经典算法，做相应的题目练习多编增强熟练度实践篇有目的的编程提高比较大实践篇36提问与解答环节Questions And Answers提问与解答环节37谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal谢谢聆听Learning Is To Achieve A C38ACM培训输入输出处理需要掌握的知识参考资料ACM培训39常用术语ICPC(InternationalCollegiateProgrammingContest)国际大学生程序设计竞赛AC(Accepted)程序通过WA(WrongAnswer)错误的答案(读做“哇”)常用术语ICPC(InternationalColleg40PE(PresentationError)输出格式错误RE(RuntimeError)程序执行错误(常见于数组溢出、递归层数太多.)CE(CompileError)编译错误MLE(MemoryLimitExceeded)内存超界(正式比赛没有内存限制，但如果用太多可能RE)PE(PresentationError)输出格式错误41TLE(TimeLimitExceed)程序超时错误(死循环或算法有问题)OLE(OutputLimitExceed)输出超界(一般不太常见，除非你输出了超过1024K.)TLE(TimeLimitExceed)程序超时错误42DP(DynamicProgramming)动态编程，动态规划DFS(DepthFirstSearch)深度优先搜索BFS(BreadthFirstSearch)宽度/广度优先搜索LCS(LongestCommonSubsequence)最长公共子串DP(DynamicProgramming)动态编程，43输入输出C:scanf速度快printf格式容易控制C+:cin使用简单,自动识别类型cout格式控制较麻烦数据规模较大时,推荐(必须)使用scanf以避免超时(TLE)输入输出C:44输入输出cout:带缓冲输出带缓冲输出printf:不带缓冲输出不带缓冲输出C和C+的输入输出混合使用输入输出cout:带缓冲输出45至于cout的缓存问题，五种情况会刷缓冲:n（我试下来是要刷的）endlflush缓冲区满程序结束至于cout的缓存问题，五种情况会刷缓冲:46输入输出#include#include int main()for(int j=0;j5;j+)coutj=;printf(%dn,j);return 0;j=0j=1j=2j=3j=401234j=j=j=j=j=输入输出#includej=0047输入输出scanf输入格式%d%lld%c%s%lf对每种格式搞清楚一个重要问题是否自动跳过前导空白？什么是空白：空格，TAB，回车输入输出scanf48输入输出%d%lld%lf自动扫描前导空格比如：读入5个整数到A5输入文件中，数的排布是这个样子35267899206不管它，直接5次%dfor(inti=0;in;for(i=0;in&n!=0).2.输入不说明有多少个InputBlock,但以某个特殊输553.输入不说明有多少个InputBlock,以EOF为结束标志while(scanf(%d%d,&a,&b)!=EOF).while(cinab).3.输入不说明有多少个InputBlock,以EOF为结束564.输入是一整行的字符串的charbuf255;gets(buf);charbuf255;cin.getline(buf,255);4.输入是一整行的字符串的charbuf255;57输出部分：1.一个InputBlock对应一个OutputBlock，OutputBlock之间没有空行.printf(%dn,ans);.coutansendl;.输出部分：1.一个InputBlock对应一个Outpu58 2.一个InputBlock对应一个OutputBlock，OutputBlock之间有空行。intcasenum=0;.if(casenum+)putchar(n);.printf(%dn,ans);intcasenum=0;.if(casenum+)coutendl;.coutansendl;2.一个InputBlock对应一个OutputBlo593.一个InputBlock对应一个OutputBlock，每个OutputBlock之后都有空行。.printf(%dnn,ans);.coutansendlendl;.其他说明：1.EOF是一个标志（常量），不是字符串EOF，用键盘的输入方法是Ctrl+Z2.最好不要把C和C+的输入输出语句混着用，会造成一些莫名其妙的问题3.我个人倾向于使用纯C的输入输出，因为方便且速度快。3.一个InputBlock对应一个OutputBloc60关于重定向操作当程序要输入的内容很多时，从文件读入的操作变得非常重要,特别是需要调试时，这样可以避免你反复的从键盘敲入重复的内容。使用标准输入语句,可以使用重定向命令行输入命令:Test.exeout.dat关于重定向操作61最好不要进行函数声明变量定义在使用之前避免for(inti=0;in)考虑输入intmain()64例子intmain()intn,res;while(cinn)res=1;for(inti=2;i=n;i+)res*=i;coutresendl;Wrong AnswerWrong Answer例子intmain()WrongAnswer65FactorialTimeLimit:1000MSMemoryLimit:65536KDescription Caculaten!.Input Theinputshouldconsistofaseriesofcases.Ineverycasethereshouldbeaninteger,n(nislessthan21).Onelinepercase.Output Foreachcaseyoushouldoutputthethevalueofn!.Sample Input 23Sample Output 2620!=24329000Factorial20!=66Int32位取值范围是-2147483648214748364720!=2432900020-2102132736Int32位20!=2067类似问题:数据范围:决定使用什么类型数据规模:决定开多大的数组#defineMAX10005宜大不宜小类似问题:68注意事项三个方向：Algorithm（算法）Math（数学）Realization（实现）三种能力：EnglishReadingSelf-learningTeamwork注意事项三个方向：69需要哪些知识不完全列表不完全列表排序算法（平方排序算法的应用，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）数论（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余方程，中国剩余定理）指针（链表，搜索判重，邻接表，开散列，二叉树的表示，多叉树的表示）按位运算（and，or，xor，shl，shr，一些应用）图论（图论模型的建立，平面图，欧拉公式与五色定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最小生成树的三种算法，最短路的三种算法，标号法，差分约束系统，验证二分图，Konig定理，匈牙利算法，KM算法，稳定婚姻系统，最大流算法，最小割最大流定理，最小费用最大流算法）计算几何（平面解几及其应用，向量，点积及其应用，叉积及其应用，半平面相交，求点集的凸包，最近点对问题，凸多边形的交，离散化与扫描）数据结构（广度优先搜索，验证括号匹配，表达式计算，递归的编译，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏树，斜堆，二项堆，二叉查找树，AVL，Treap，Splay，静态二叉查找树，2-d树，线段树，二维线段树，矩形树，Trie树，块状链表）组合数学（排列与组合，鸽笼原理，容斥原理，递推，Fibonacci数列，Catalan数列，Stirling数，差分序列，生成函数，置换，Polya原理）概率论（简单概率，条件概率，Bayes定理，期望值）矩阵（矩阵的概念和运算，二分求解线性递推方程，多米诺骨牌棋盘覆盖方案数，高斯消元）字符串处理（KMP，后缀树，有限状态自动机，Huffman编码，简单密码学）动态规划（单调队列，凸完全单调性，树型动规，多叉转二叉，状态压缩类动规，四边形不等式）博奕论（Nim取子游戏，博弈树，Shannon开关游戏）搜索（A*，ID，IDA*，随机调整，遗传算法）微积分初步（极限思想，导数，积分，定积分，立体解析几何）需要哪些知识不完全列表70如何获取知识读书读书算法导论(IntroductiontoAlgorithms)组合数学数据结构计算机算法设计与分析如何获取知识读书71如何获取知识读论文读论文历年国家集训队论文(中学生的论文)读程序读程序用批判+学习的眼光去读别人的程序读论文读论文历年国家集训队论文(中学生的论文)网络资料网络资料聚宝盆(博客)如何获取知识读论文72实践篇写算法写算法看书,读论文等的过程中,自己动手把算法实现做题做题如数学一样,是做出来的,不是想出来的动手无论你是想做好ACM训练还是想学好编程请多动手写程序这是唯一的捷径实践篇写算法73有目的的编程提高比较大现在大家处于初级阶段巩固各种基础算法针对特定的经典算法，做相应的题目练习多编增强熟练度实践篇有目的的编程提高比较大实践篇74提问与解答环节Questions And Answers提问与解答环节75谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal谢谢聆听Learning Is To Achieve A C76