《ACM学习前的忠告》由会员分享，可在线阅读，更多相关《ACM学习前的忠告（29页珍藏版）》请在金锄头文库上搜索。
1、一些初学者必须要知道的问题1.如何用C/C+处理输入输出2.复杂度和程序优化3.初学者如何进行修炼1.如何用C/C+进行输入输出 相对次要的问题，但成为很多初学者的拦 路虎 C/C+（尤其是C）输入输出方法较复杂， 需要一定时间实践才能精通 我的任务：通过实例提供处理各种输入输 出任务的方法，并讲解一些原则性的问题 ，同学们可以举一反三 首先，几个基本概念 什么是标准输入、标准输出？ 标准输入(stdin)：键盘(scanf, cin) 标准输出(stdout)：屏幕(printf, cout) 建议程序中只使用stdin和stdout 要打开文件怎么办？ freopen(“input.txt
2、”, “r”, stdin); freopen(“output.txt”, “w”, stdout); ACM/ICPC中基本上都是要求从键盘输入， 屏幕输出 是人工评测？ 否，测试前程序被做了重定向，就向上面一样，只 不过重定向是外部的 比如，Linux Shell下 $ ./prog output $ diff output answer 所以，严格按照题目描述来进行输入输出，不 要打印任何题目未做要求的信息 ACM/ICPC的输入输出特点：流式、ASCII 顺序输入、输出，避免使用文件定位函数（如 ：fseek) 不需要把所有的输出放在一处进行，随时都可 以输出，只要顺序是对的，因为只有
3、当你的程 序终止了，与正确答案的比较才会开始 字符格式，12345是5个字符1,2,3,4,5构成 所以，C中只能使用处理ACSII文件的输入输出函数 (getchar,putchar,scanf,printf,gets,fgets,puts) 使用C+进行输入输出 cin,cout 优点 数据类型自识别，使用简单 缺点 速度慢！ ACM/ICPC的测试数据规模非常大，cin/cout在这种情况下 会成为性能瓶颈，引发超时 除非输入规模小，否则不推荐使用cin! 输出规模相对较小，在某些情况下使用cout会很方 便，但是cout控制输出格式不如printf灵活 一个重要的误区 不要在一个程序中
4、同时使用cin和C输入函数（ 如：scanf) 也不要同时使用cout和C输出函数（如：printf) 但是，可以C输入函数和cout搭配使用，反之 亦然 违反以上原则可能导致输入/输出结果错误（会 发生乱序）！ 推荐使用C函数进行输入输出 输出：printf(putchar,puts)，其用法请查阅 相关书籍，比较简单，不做重点讲解 每一行输出完后要打印回车n，包括最后一行 输入：scanf, fgets(gets), getchar scanf 输入格式 %d %lld %c %s %lf 对每种格式搞清楚一个重要问题 是否自动跳过前导空白？ 什么是空白：空格，TAB，回车 %d %lld
5、 %lf自动扫描前导空格 比如：读入5个整数到A5 输入文件中，数的排布是这个样子 35 26 7899206 不管它，直接5次%d for ( int i = 0; i k ) / 处理k 如果数据不多，不失为一个好办法 学习C函数输入输出,尤其是各种格式串， 最好查阅相关手册 Linux $ man 3 printf2.复杂度和程序优化 复杂度计算出来后有什么用？ 估计程序能否在规定时间内处理题目指定规模的数据 “规模”的举例 给N个数排序 规模：N 判断字符串P是否是字符串T的子串 规模：串的长度|P|和|T| 判断一个整数是否属于整数集合S |S| 要判断多少次（查询次数） 图中某两个
6、点的最短路径/求连通图的最小生成树 顶点数 边数 给一个整数集合S，问是否存在S的一个非空子集T，满 足T中所有元素的和为零 |S| 重要的事实：当代计算机1s内可做107左右次计算 配置好的机器可到k*107108 在这个限制下时间复杂度一定的算法存在能处理的规模上 限 复杂度数量级最大规模 O(logN)1020很大 O(N1/2)10121014 O(N)106107 O(NlogN)105106 O(N2)10002500 O(N3)100500 O(N4)5050 O(2N)2020 O(N!)910 几点说明 以上只是大概数据，具体的情况还和实际问题中的其 他因素有关 算法的常数因
7、子 2N和16N 测试机的配置 复杂度是上界还是上确界 程序中使用的剪枝和数据的关系 应用 抛弃无希望的算法 举例：如果规模是2000，你设计出来的算法是O(N3)，应该 想办法把它改进到O(N2) 2006 UESTC校内赛题目：Simple Task II X2=1(mod n)的解的个数(n output $ gprof prog | vim -使用STL STL包含一些复杂度很好的标准算法和数据结构(container) 算法 sort O(NlogN) push_heap pop_heap O(logN) nth_element O(N) 容器 set 相当于集合，插入、删除、查询一
8、个元素是否存在都是O(logN)的 map O(logN)把一种类型对应到另一种类型，比如字符串对应到整数 multiset multimap多值 vector list queue stack priority_queue 优先队列，不过有push_heap和pop_heap这个没有什么太大 的用武之地 一定要清楚各种算法和容器操作的复杂度，不要想当然的乱用 http:/ http:/ 有了STL仍然要学习基本算法和数据结构，即使不实现也要知道原理3.初学者如何进行修炼 推荐两个网站 基本功训练 基本算法讲解、训练 每个题做出后有讲解、代码 闯关模式 初学者推荐Chapter1-4,Cha
9、pter5-6挑战性较强 Algorithm Competition - Single Round Match(SRM) 一个月4次左右，有rating 分两个版(Div I, Div II) 参加人数众多 每次比赛后有详细的解题报告、代码 比赛结束后有Practice Room可以继续做 可以查看每一个人的代码 Forum很热闹，外国人非常乐于助人 有$哦，Room前三 国内题库 http:/北京大学 http:/浙江大学 http:/天津大学 http:/哈工大 http:/武汉大学 国外题库 http:/acm.timus.ru 数学题较多，OI选手必做 http:/acm.uva.e
10、s 国外最大题库，人很多， Forum也很热闹 http:/acm.sgu.ru 题较难 建议 初学时做一定量的题目打基础 针对特定的经典算法，做相应的题目练习 过题数并不重要，做题数的排名也不重要 参考书 算法导论英文版 入门级读物 初读时，前面的数学部分建立基本概念即可，无需深究 算法的正确性证明、复杂度分析一定要扎实掌握(Master Theorem要会用，摊还分析了解) 数据结构部分理解是关键，一些过于复杂的数据结构对于初学者 并不一定要求实现(红黑树、二项堆、Fibbonacci 堆），但基本 的数据结构一定要熟练掌握，要能熟练实现 图论经典算法要熟练掌握 动态规划要熟练掌握 高级部分只用选学一些 参考书 算法艺术与信息学竞赛刘汝佳、黄亮 较难 适合有一定基础的同学 对于初学者仍然推荐第一章和第三章 BBS 的Web Board(现在已经龙蛇混杂，最好只作为了 解新信息和讨论题目的渠道) 各大高校BBS的算法版(分类讨论区-电脑技术-Algorithm(或 ACM、ICPC)，精华区往往有很多资料和指南 推荐 (武大） (中山） (浙大) (上交） (哈工大） (天大） (南大) (川大)
