1、ACM 培训输入输出处理需要掌握的知识参考资料常用术语ICPC (International Collegiate Programming Contest) 国际大学生程序设计竞赛 AC (Accepted) 程序通过 WA (Wrong Answer) 错误的答案 (读做“哇”)PE (Presentation Error) 输出格式错误RE (Runtime Error) 程序执行错误 (常见于数组溢出、递归层数太多 .) CE (Compile Error) 编译错误 MLE (Memory Limit Exceeded) 内存超界 (正式比赛没有内存限制，但如果用太多可能 RE)TLE
2、 (Time Limit Exceed) 程序超时错误 (死循环或算法有问题) OLE (Output Limit Exceed) 输出超界 (一般不太常见，除非你输出了超过 1024K .) DP (Dynamic Programming) 动态编程，动态规划DFS (Depth First Search) 深度优先搜索BFS (Breadth First Search) 宽度/广度优先搜索 LCS (Longest Common Subsequence) 最长公共子串输入输出C:scanf速度快 printf 格式容易控制C+: cin使用简单, 自动识别类型 cout格式控制较麻烦数据规
3、模较大时, 推荐(必须)使用scanf 以避免超时(TLE)输入输出C和C+的输入输出混合使用至于cout的缓存问题，五种情况会刷缓冲:n（我试下来是要刷的）endlflush缓冲区满程序结束输入输出#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=输入输出scanf输入格式%d %lld %c %s %lf对每种格式搞清楚一个重要问题是否自动跳过前导空白？什么是空白：空格，TAB，回车输入输出%d %lld %lf自动扫描前导
4、空格比如：读入5个整数到A5输入文件中，数的排布是这个样子35 26 78 99206不管它，直接5次%dfor ( int i = 0; i n; for(i=0; i n & n != 0) . 3.输入不说明有多少个Input Block,以EOF为结束标志while(scanf(%d %d, &a, &b) != EOF) . while(cin a b) . 4.输入是一整行的字符串的char buf255; gets(buf); char buf255; cin.getline(buf, 255); 输出部分： 1.一个Input Block对应一个Output Block，Out
5、put Block之间没有空行 . printf(%dn, ans); . . cout ans endl; . 2.一个Input Block对应一个Output Block，Output Block之间有空行。int casenum = 0; . if (casenum+) putchar(n); . printf(%dn, ans); int casenum = 0; . if (casenum+) cout endl; . cout ans endl; 3.一个Input Block对应一个Output Block，每个Output Block之后都有空行。 . printf(%dnn
6、, ans); . . cout ans endl endl; . 其他说明：1.EOF 是一个标志（常量），不是字符串EOF，用键盘的输入方法是 Ctrl+Z2.最好不要把C和C+的输入输出语句混着用，会造成一些莫名其妙的问题3.我个人倾向于使用纯C的输入输出，因为方便且速度快。 关于重定向操作当程序要输入的内容很多时，从文件读入的操作变得非常重要,特别是需要调试时，这样可以避免你反复的从键盘敲入重复的内容。 使用标准输入语句,可以使用重定向命令行输入命令: Test.exe out.dat最好不要进行函数声明变量定义在使用之前 避免for(int i = 0;i n) 例子int main
7、() int n, res; while(cinn) res=1;for(int i=2; i=n; i+) res*=i; coutresendl; Factorial Time Limit:1000MS Memory Limit:65536KDescription Caculate n!.Input The input should consist of a series of cases.In every case there should be an integer,n(n is less than 21).One line per case.Output For each case
8、you should output the the value of n!.Sample Input 2 3 Sample Output 2 6 Int 32位取值范围是 -2147483648 2147483647 20-2102132736类似问题:数据范围: 决定使用什么类型数据规模: 决定开多大的数组#define MAX 10005宜大不宜小注意事项三个方向： Algorithm（算法） Math（数学） Realization（实现）三种能力： English Reading Self-learning Team work需要哪些知识不完全列表不完全列表排序算法（平方排序算法的应用
9、，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）数论（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余方程，中国剩余定理）指针（链表，搜索判重，邻接表，开散列，二叉树的表示，多叉树的表示）按位运算（and，or，xor，shl，shr，一些应用）图论（图论模型的建立，平面图，欧拉公式与五色定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最小生成树的三种算法，最短路 的三种算法，标号法，差分约束系统，验证二分图，Konig定理，匈牙利算法，KM算法，稳定婚姻系统，最大流算法，最小割最大流定理，最小费用最大流算 法
10、）计算几何（平面解几及其应用，向量，点积及其应用，叉积及其应用，半平面相交，求点集的凸包，最近点对问题，凸多边形的交，离散化与扫描）数据结构（广度优先搜索，验证括号匹配，表达式计算，递归的编译，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏树，斜堆，二 项堆，二叉查找树，AVL，Treap，Splay，静态二叉查找树，2-d树，线段树，二维线段树，矩形树，Trie树，块状链表）组合数学（排列与组合，鸽笼原理，容斥原理，递推，Fibonacci数列，Catalan数列，Stirling数，差分序列，生成函数，置换，Polya原理）概率论（简单概率，条件概率，Bayes定理，期望
11、值）矩阵（矩阵的概念和运算，二分求解线性递推方程，多米诺骨牌棋盘覆盖方案数，高斯消元）字符串处理（KMP，后缀树，有限状态自动机，Huffman编码，简单密码学）动态规划（单调队列，凸完全单调性，树型动规，多叉转二叉，状态压缩类动规，四边形不等式）博奕论（Nim取子游戏，博弈树，Shannon开关游戏）搜索（A*，ID，IDA*，随机调整，遗传算法）微积分初步（极限思想，导数，积分，定积分，立体解析几何）如何获取知识读书读书算法导论(Introduction to Algorithms)组合数学数据结构计算机算法设计与分析如何获取知识读论文读论文历年国家集训队论文(中学生的论文)读程序读程序用
12、批判+学习的眼光去读别人的程序读论文读论文历年国家集训队论文(中学生的论文)网络资料网络资料聚宝盆(博客)实践篇写算法写算法看书, 读论文等的过程中, 自己动手把算法实现做题做题如数学一样, 是做出来的, 不是想出来的动手无论你是想做好ACM训练还是想学好编程请多动手写程序这是唯一的捷径有目的的编程 提高比较大现在大家处于初级阶段巩固各种基础算法 针对特定的经典算法，做相应的题目练习多编增强熟练度实践篇提问与解答环节Questions And Answers谢谢聆听 学习就是为了达到一定目的而努力去干, 是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard, Is A Process To Overcome Various Difficulties For A Goal
