《ACM学习前的忠告》PPT课件.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中基本上都是要求从键盘输入，屏幕输出是人工评测？否，测试前程序被做了重定向，就向上面一样，只不过重定向是外部的比如，LinuxShell下$./progoutput$diffoutputanswer所以，严格按照题目描述来进行输入输出，不要打印任何题目未做要求的信息,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输入文件中，数的排布是这个样子35267899206不管它，直接5次%dfor(inti=0;ik)/处理k如果数据不多，不失为一个好办法学习C函数输入输出,尤其是各种格式串，最好查阅相关手册Linux$man3printf,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)2006UESTC校内赛题目：SimpleTaskIIX2=1(modn)的解的个数(n2312*109)枚举x1,n)复杂度是O(n)标程的复杂度O(n1/2)可算到n=1012,无需过度优化ICPC不是比谁的复杂度更低，谁的程序更快，而是比谁能够在给定的时间内把答案正确的计算出来复杂度足够好即可给N