搜索
2009UESTCACM/ICPC校内赛讲座一些初学者必须要知道的问题罗象宏lxhgwwlxhimo@163.com1.如何用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下$./proginputoutput$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),getchar•scanf–输入格式•%d%lld%c%s%lf–对每种格式搞清楚一个重要问题•是否自动跳过前导空白？–什么是空白：空格，TAB，回车•%d%lld%lf自动扫描前导空格•比如：读入5个整数到A[5]–输入文件中，数的排布是这个样子35267899206–不管它，直接5次%d•for(inti=0;i5;i++)scanf(“%d”,A+i);•%lld用于输入和输出长整数(longlong,64位)•%lf用于输入输出double•%s读一个字符串，自动扫描前导空白，读到空白结束–如：abcdefgh，将读出”abcd”•%c读一个字符，但是不扫描前导空白–如何读一个非空白字符呢？–比如，读取某人的信息，其性别用M/F表示•NathanMFlying•ClaireFSelf-healing–名字和能力用%s读，性别怎么办，自己扫描空格？麻烦！•读一个非空白字符，方法一charstr[2];scanf(“%1s”,str);//%s扫描前导空白，并且只读一个字符charc=str[0];•方法二–强制扫描空白–在%前面加上一个空格表示“强制扫描前导空白”–scanf(“%c”,&ch);–前面那个读人物信息的完整scanf语句：•scanf(“%s%c%s”,name,&gender,ability);•同理，格式后面加一空格表示“读完这个变量后扫描空白”，注意空白是包括回车的•读一行：gets,fgets–gets会导致很讨厌的warningmessage，所以可改用fgets–fgets(str,sizeofstr,stdin)=gets(str)–注意应使“下一个字符”处于这一行开头•有n个整数在一行上，但是n不知，只知道整数是空格分开的，怎么读？–拿getchar+ungetc扫描？麻烦！–介绍一个函数：strtok•strtok示例•538293828588258charstr[100];char*input=str,*token;gets(str);while((token=strtok(input,““))!=NULL){input=NULL;intnumber=atoi(token);//处理number}•也可用istringstream处理istringstreamin(str);while(ink){//处理k}如果数据不多，不失为一个好办法•学习C函数输入输出,尤其是各种格式串，最好查阅相关手册–Linux$man3printf2.复杂度和程序优化•复杂度计算出来后有什么用？–估计程序能否在规定时间内处理题目指定规模的数据•“规模”的举例–给N个数排序•规模：N–判断字符串P是否是字符串T的子串•规模：串的长度|P|和|T|–判断一个整数是否属于整数集合S•|S|•要判断多少次（查询次数）–图中某两个点的最短路径/求连通图的最小生成树•顶点数•边数–给一个整数集合S，问是否存在S的一个非空子集T，满足T中所有元素的和为零•|S|•重要的事实：当代计算机1s内可做10^7左右次计算–配置好的机器可到k*10^7~10^8•在这个限制下时间复杂度一定的算法存在能处理的规模上限–复杂度数量级最大规模–O(logN)10^20很大–O(N^1/2)10^1210^14–O(N)10^610^7–O(NlogN)10^510^6–O(N^2)10002500–O(N^3)100500–O(N^4)5050–O(2^N)2020–O(N!)910•几点说明–以上只是大概数据，具体的情况还和实际问题中的其他因素有关•算法的常数因子–2N和16N•测试机的配置•复杂度是上界还是上确界•程序中使用的剪枝和数据的关系•应用–抛弃无希望的算法•举例：如果规模是2000，你设计出来的算法是O(N^3)，应该想办法把它改进到O(N^2)•2006UESTC校内赛题目：SimpleTaskII–X^2=1(modn)的解的个数(n2^31≈2*10^9)–枚举x[1,n)复杂度是O(n)–标程的复杂度O(n^1/2)可算到n=10^12•无需过度优化–ICPC不是比谁的复杂度更低，谁的程序更快，而是比谁能够在给定的时间内把答案正确的计算出来–复杂度足够好即可–给N个整数，求他们的一个排列，使得相邻元素的差的绝对值之和最小•N=8枚举所有可能的排列！–给一个整数集合S，问是否存在S的一个非空子集T，满足T中所有元素的和为零•|S|=20枚举所有可能的子集O(2^|S|)•事实上，这是一个NP完全问题，目前没有比O(2^|S|)更快的算法，你去想复杂度更好的算法可能根本就是在浪费时间•无需过度优化–反例–上述原则并不是绝对的，如果你有兴趣，完全可以去思考一下复杂度更好的算法，如果你发现了一个很好的算法，不妨去出道题，考考别人！给北大OJ()出题是有奖金的哦!•空间复杂度–当代32位PC上空间最大限制一般是10^7Byte≈10MB，比如你可以开几个大小为10^6的整型数组:intA[10^6];开更大的数组，比如A[10^7]一般会遇到MemoryLimitExceed;即使不超内存根据前面的运算次数限制可知时间复杂度也不会好–有一些缩减空间的技巧，但是卡空间ACM/ICPC一般不推荐•空间复杂度（两种常见空间溢出错误）–栈溢出（递归程序）•递归程序很常见•大多数情况下你不必担心栈溢出的问题–在函数里面开很大的数组•解决方案开成全局数组•代码优化–少做或不做代码级优化•“给使用低效算法的程序进行代码优化就好比给一头猪喷香水”--USACO–ACM/ICPC很少卡常数因子•只要复杂度相同，一般都能过–即使做，也要选择正确的地方下手•循环密集，执行次数多的地方•使用profiler工具，找出程序中执行次数最多的地方，进行优化（包括算法优化）–Linux–$g++-pg–g–oprogprog.cpp–$./proginputoutput–$gprofprog|vim-•使用STL–STL包含一些复杂度很好的标准算法和数据结构(container)–算法•sortO(NlogN)•push_heappop_heapO(logN)•nth_elementO(N)–容器•set相当于集合，插入、删除、查询一个元素是否存在都是O(logN)的•mapO(logN)把一种类型对应到另一种类型，比如字符串对应到整数•multisetmultimap多值•vector•list•queue•stack•priority_queue优先队列，不过有push_heap和pop_heap这个没有什么太大的用武之地–一定要清楚各种算法和容器操作的复杂度，不要想当然的乱用–––有了STL仍然要学习基本算法和数据结构，即使不实现也要知道原理3.初学者如何进行修炼•推荐两个网站–ace.delos.com/usacogate(USACO)•基本功训练•基本算法讲解、训练•每个题做出后有讲解、代码•闯关模式•初学者推荐Chapter1-4,Chapter5-6挑战性较强–•AlgorithmCompetition-SingleRoundMatch(SRM)•一个月4次左右，有rating•分两个版(DivI,DivII)•参加人数众多•每次比赛后有详细的解题报告、代码•比赛结束后有PracticeRoom可以继续做•可以查看每一个人的代码•Forum很热闹，外国人非常乐于助人•有$哦，Room前三•国内题库–北京大学–浙江大学–天津大学–哈工大–武汉大学•国外题库–数学题较多，OI选手必做–国外最大题库，人很多，Forum也很热闹–题较难•建议–初学时做一定量的题目打基础–针对特定的经典算法，做相应的题目练习–过题数并不重要，做题数的排名也不重要•参考书–算法导论英文版•入门级读物–初读时，前面的数学部分建立基本概念即可，无需深究–算法的正确性证明、复杂度分析一定要扎实掌握(MasterTheorem要会用，摊还分析了解)–数据结构部分理解是关键，一些过于复杂的数据结构对于初学者并不一定要求实现(红黑树、二项堆、Fibbonacci堆），但基本的数据结构一定要熟练掌握，要能熟练实现–图论经典算法要熟练掌握–动态规划要熟练掌握–高级部分只用选学一些•参考书–算法艺术与信息学竞赛刘汝佳、黄亮•较难适合有一定基础的同学•对于初学者仍然推荐第一章和第三章•BBS–acm.pku.edu.cn的WebBoard–各大高校BBS的算法版(分类讨论区-电脑技术-Algorithm(或ACM、ICPC)，精华区往往有很多资料和指南•推荐–bbs.whu.edu.cn(武大）