• 1. 一些初学者必须要知道的问题
  • 2. 1.如何用C/C++处理输入输出 2.复杂度和程序优化 3.初学者如何进行修炼
  • 3. 1.如何用C/C++进行输入输出
  • 4. 相对次要的问题,但成为很多初学者的拦路虎 C/C++(尤其是C)输入输出方法较复杂,需要一定时间实践才能精通 我的任务:通过实例提供处理各种输入输出任务的方法,并讲解一些原则性的问题,同学们可以举一反三 首先,几个基本概念
  • 5. 什么是标准输入、标准输出? 标准输入(stdin):键盘(scanf, cin) 标准输出(stdout):屏幕(printf, cout) 建议程序中只使用stdin和stdout 要打开文件怎么办? freopen(“input.txt”, “r”, stdin); freopen(“output.txt”, “w”, stdout);
  • 6. ACM/ICPC中基本上都是要求从键盘输入,屏幕输出 是人工评测? 否,测试前程序被做了重定向,就向上面一样,只不过重定向是外部的 比如,Linux Shell下 $ ./prog < input > output $ diff output answer 所以,严格按照题目描述来进行输入输出,不要打印任何题目未做要求的信息
  • 7. ACM/ICPC的输入输出特点:流式、ASCII 顺序输入、输出,避免使用文件定位函数(如:fseek) 不需要把所有的输出放在一处进行,随时都可以输出,只要顺序是对的,因为只有当你的程序终止了,与正确答案的比较才会开始 字符格式,12345是5个字符‘1’,’2’,’3’,’4’,’5’构成 所以,C中只能使用处理ACSII文件的输入输出函数(getchar,putchar,scanf,printf,gets,fgets,puts)
  • 8. 使用C++进行输入输出 cin,cout 优点 数据类型自识别,使用简单 缺点 速度慢! ACM/ICPC的测试数据规模非常大,cin/cout在这种情况下会成为性能瓶颈,引发超时 除非输入规模小,否则不推荐使用cin! 输出规模相对较小,在某些情况下使用cout会很方便,但是cout控制输出格式不如printf灵活
  • 9. 一个重要的误区 不要在一个程序中同时使用cin和C输入函数(如:scanf) 也不要同时使用cout和C输出函数(如:printf) 但是,可以C输入函数和cout搭配使用,反之亦然 违反以上原则可能导致输入/输出结果错误(会发生乱序)!
  • 10. 推荐使用C函数进行输入输出 输出:printf(putchar,puts),其用法请查阅相关书籍,比较简单,不做重点讲解 每一行输出完后要打印回车’\n’,包括最后一行 输入:scanf, fgets(gets), getchar scanf 输入格式 %d %lld %c %s %lf 对每种格式搞清楚一个重要问题 是否自动跳过前导空白? 什么是空白:空格,TAB,回车
  • 11. %d %lld %lf自动扫描前导空格 比如:读入5个整数到A[5] 输入文件中,数的排布是这个样子 35 26 78 99 206 不管它,直接5次%d for ( int i = 0; i < 5; i++ ) scanf(“%d”, A + i); %lld用于输入和输出长整数(long long,64位) %lf用于输入输出double
  • 12. %s 读一个字符串,自动扫描前导空白,读到空白结束 如: abcd efgh,将读出”abcd” %c读一个字符,但是不扫描前导空白 如何读一个非空白字符呢? 比如,读取某人的信息,其性别用M/F表示 Nathan M Flying Claire F Self-healing 名字和能力用%s读,性别怎么办,自己扫描空格?麻烦!
  • 13. 读一个非空白字符,方法一 char str[2]; scanf(“%1s”, str); // %s扫描前导空白,并且只读一个字符 char c = str[0]; 方法二 强制扫描空白 在%前面加上一个空格表示“强制扫描前导空白” scanf(“ %c”, &ch); 前面那个读人物信息的完整scanf语句: scanf(“%s %c %s”, name, &gender, ability);
  • 14. 同理,格式后面加一空格表示“读完这个变量后扫描空白”,注意空白是包括回车的 读一行:gets, fgets gets会导致很讨厌的warning message,所以可改用fgets fgets(str, sizeof str, stdin) = gets(str) 注意应使“下一个字符”处于这一行开头 有n个整数在一行上,但是n不知,只知道整数是空格分开的,怎么读? 拿getchar+ungetc扫描?麻烦! 介绍一个函数:strtok
  • 15. strtok示例 5 38 29 38 28 58 82 58 char str[100]; char *input = str, *token; gets(str); while ( (token = strtok(input, “ “)) != NULL ) { input = NULL; int number = atoi(token); // 处理number }
  • 16. 也可用istringstream处理 istringstream in(str); while ( in >> k ) { // 处理k } 如果数据不多,不失为一个好办法 学习C函数输入输出,尤其是各种格式串,最好查阅相关手册 Linux $ man 3 printf
  • 17. 2.复杂度和程序优化
  • 18. 复杂度计算出来后有什么用? 估计程序能否在规定时间内处理题目指定规模的数据 “规模”的举例 给N个数排序 规模:N 判断字符串P是否是字符串T的子串 规模:串的长度|P|和|T| 判断一个整数是否属于整数集合S |S| 要判断多少次(查询次数) 图中某两个点的最短路径/求连通图的最小生成树 顶点数 边数 给一个整数集合S,问是否存在S的一个非空子集T,满足T中所有元素的和为零 |S|
  • 19. 重要的事实:当代计算机1s内可做10^7左右次计算 配置好的机器可到k*10^7~10^8 在这个限制下时间复杂度一定的算法存在能处理的规模上限 复杂度 数量级 最大规模 O(logN) >>10^20 很大 O(N^1/2) 10^12 10^14 O(N) 10^6 10^7 O(NlogN) 10^5 10^6 O(N^2) 1000 2500 O(N^3) 100 500 O(N^4) 50 50 O(2^N) 20 20 O(N!) 9 10
  • 20. 几点说明 以上只是大概数据,具体的情况还和实际问题中的其他因素有关 算法的常数因子 2N和16N 测试机的配置 复杂度是上界还是上确界 程序中使用的剪枝和数据的关系 应用 抛弃无希望的算法 举例:如果规模是2000,你设计出来的算法是O(N^3),应该想办法把它改进到O(N^2) 2006 UESTC校内赛题目:Simple Task II X^2=1(mod n)的解的个数(n<2^31≈2*10^9) 枚举x [1,n) 复杂度是O(n) 标程的复杂度O(n^1/2) 可算到n<=10^12
  • 21. 无需过度优化 ICPC不是比谁的复杂度更低,谁的程序更快,而是比谁能够在给定的时间内把答案正确的计算出来 复杂度足够好即可 给N个整数,求他们的一个排列,使得相邻元素的差的绝对值之和最小 N<=8 枚举所有可能的排列! 给一个整数集合S,问是否存在S的一个非空子集T ,满足T中所有元素的和为零 |S|<=20 枚举所有可能的子集 O(2^|S|) 事实上,这是一个NP完全问题,目前没有比O(2^|S|)更快的算法,你去想复杂度更好的算法可能根本就是在浪费时间
  • 22. 无需过度优化 – 反例 上述原则并不是绝对的,如果你有兴趣,完全可以去思考一下复杂度更好的算法,如果你发现了一个很好的算法,不妨去出道题,考考别人!给北大OJ(http://acm.pku.edu.cn)出题是有奖金的哦! 空间复杂度 当代32位PC上空间最大限制一般是10^7Byte≈10MB,比如你可以开几个大小为10^6的整型数组: int A[10^6]; 开更大的数组,比如A[10^7]一般会遇到Memory Limit Exceed; 即使不超内存根据前面的运算次数限制可知时间复杂度也不会好 有一些缩减空间的技巧,但是卡空间ACM/ICPC一般不推荐
  • 23. 空间复杂度(两种常见空间溢出错误) 栈溢出(递归程序) 递归程序很常见 大多数情况下你不必担心栈溢出的问题 在函数里面开很大的数组 解决方案 开成全局数组 代码优化 少做或不做代码级优化 “给使用低效算法的程序进行代码优化就好比给一头猪喷香水” --USACO ACM/ICPC很少卡常数因子 只要复杂度相同,一般都能过 即使做,也要选择正确的地方下手 循环密集,执行次数多的地方 使用profiler工具,找出程序中执行次数最多的地方,进行优化(包括算法优化) Linux $ g++ -pg –g –o prog prog.cpp $ ./prog < input > output $ gprof prog | vim -
  • 24. 使用STL STL包含一些复杂度很好的标准算法和数据结构(container) 算法 sort O(NlogN) push_heap pop_heap O(logN) nth_element O(N) 容器 set 相当于集合,插入、删除、查询一个元素是否存在都是O(logN)的 map O(logN)把一种类型对应到另一种类型,比如字符串对应到整数 multiset multimap多值 vector list queue stack priority_queue 优先队列,不过有push_heap和pop_heap这个没有什么太大的用武之地 一定要清楚各种算法和容器操作的复杂度,不要想当然的乱用 http://www.cppreference.com/ http://www.sgi.com/tech/stl/ 有了STL仍然要学习基本算法和数据结构,即使不实现也要知道原理
  • 25. 3.初学者如何进行修炼
  • 26. 推荐两个网站 ace.delos.com/usacogate(USACO) 基本功训练 基本算法讲解、训练 每个题做出后有讲解、代码 闯关模式 初学者推荐Chapter1-4,Chapter5-6挑战性较强 www.topcoder.com/tc Algorithm Competition - Single Round Match(SRM) 一个月4次左右,有rating 分两个版(Div I, Div II) 参加人数众多 每次比赛后有详细的解题报告、代码 比赛结束后有Practice Room可以继续做 可以查看每一个人的代码 Forum很热闹,外国人非常乐于助人 有$哦,Room前三
  • 27. 国内题库 http://acm.pku.edu.cn 北京大学 http://acm.zju.edu.cn 浙江大学 http://acm.tju.edu.cn 天津大学 http://acm.hit.edu.cn 哈工大 http://acm.whu.edu.cn 武汉大学 国外题库 http://acm.timus.ru 数学题较多,OI选手必做 http://acm.uva.es 国外最大题库,人很多,Forum也很热闹 http://acm.sgu.ru 题较难
  • 28. 建议 初学时做一定量的题目打基础 针对特定的经典算法,做相应的题目练习 过题数并不重要,做题数的排名也不重要 参考书 算法导论英文版 入门级读物 初读时,前面的数学部分建立基本概念即可,无需深究 算法的正确性证明、复杂度分析一定要扎实掌握(Master Theorem要会用,摊还分析了解) 数据结构部分理解是关键,一些过于复杂的数据结构对于初学者并不一定要求实现(红黑树、二项堆、Fibbonacci 堆),但基本的数据结构一定要熟练掌握,要能熟练实现 图论经典算法要熟练掌握 动态规划要熟练掌握 高级部分只用选学一些
  • 29. 参考书 算法艺术与信息学竞赛 刘汝佳、黄亮 较难 适合有一定基础的同学 对于初学者仍然推荐第一章和第三章 BBS acm.pku.edu.cn的Web Board(现在已经龙蛇混杂,最好只作为了解新信息和讨论题目的渠道) 各大高校BBS的算法版(分类讨论区->电脑技术->Algorithm(或ACM、ICPC),精华区往往有很多资料和指南 推荐 bbs.whu.edu.cn(武大) bbs.zsu.edu.cn(中山) bbs.freecity.cn(浙大) bbs.sjtu.edu.cn(上交) bbs.hit.edu.cn(哈工大) bbs.tju.edu.cn(天大) bbs.nju.edu.cn(南大) bbs.scu.edu.cn(川大)