ACM学习前的忠告.ppt

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