NOIP经验介绍

NOIP经验介绍•编程风格•编译命令•巧用#语句•头文件•巧用语言特性•比赛技巧•对拍•做题•合作•自学编程风格对于NOIP来说，也许编程风格没那么重要，但是，一个好的编程风格，有助于在编写程序之后的调试以及赛后分析，有时，甚至可以影响到比赛结果。•1.有一个规则的变量命名法。•Q：你的变量名有3个字母以上的吗？•有的人的变量命名很随意，直接就是a,b,c,d……在变量较少的情况下，还不会有什么问题，但一旦变量较多，还能很快的反应过来哪个变量到底代表什么含义吗？显然不能。•所以，推荐在命名变量时使用英文单词（缩写）或者汉语拼音（缩写），能在定义时加上注释就更好了。编程风格•2.有一定的缩进习惯•保持良好的缩进习惯能有效的区分开各个层次之间的关系。无论是2空格，4空格，还是6空格，只要能保持就很好。编程风格•简单的对比：编程风格•3.将不同功能部分分函数编写•这是比较重要的一点。为什么要分函数编写呢？•第一，有的功能要重复使用，开个函数就可以直接调用函数而不用复制代码，并且修改方便。•第二，查错调试时可以分函数模块查错，分别检查每个函数是否达到预期功能即可，比整体查错更简单。•第三，可以巧用函数返回值来实现某些功能。•Ps.熟悉我的同学知道，对于较为复杂的题目，我的main()通常只有两个函数，input()和work()以及一个输出答案部分（有时输出我还会写个output()）。编程风格•4.函数先声明再编写•什么意思呢？•就是说先在main()前以typenamefunname(argulist);的形式声明函数，然后再在main()后写代码。•这样做的好处是，不用担心在fun1()中调用fun2()时fun2()还未定义以至于CE。•实例：qyz某次写了两个函数find1()和find2()，在find1()中调用了find2()，又在find2()中调用了find1()，这时如果直接在main前编写而不先声明的话，无论以怎样的顺序放两个函数的代码都是会CE的，这时就必须要先声明再编写了。•事实上，用术语应该叫做先定义，再实现。编程风格编译命令•编译命令是个很好的东西，可以在很大程度上帮助你修正程序的语法错误。•1.-Wall-Wextra，这两个命令可以使编译器显示更多的警告，例如变量未初始化就使用，有命名冲突，main未return0;等等。还可以加上-Werror以使警告转换成错误。•2.跑暴力打表程序可以开-O2。-O2使得编译器对于程序进行优化，降低常数，提高速度。•注意，如果想卡时可不要开-O2，有很大影响的。另外，-O2会影响浮点数的精度，以及可能带来一些无法预料的问题。编译命令•如何加编译命令？•在左下图中勾选选项，并依次填写即可。注意加空格。或是直接在右图所示位置选择即可。编译命令•来看个实例。•请大家找出下面这个程序中不符合规范以及可能会导致错误的地方。•毛病有不少，不是嘛？•来看看编译器的反应。编译命令•不加-Wall-Wextra来编译看看。•看，编译通过了，编译器并没有返回任何错误信息。•现在把-Wall-Wextra加上再看看。•看，编译器给出了很多警告。下面来分析一下这些警告。编译命令•returntypedefaultsto'int'[-Wreturn-type]——main没有标明返回int。•format'%d'expectsargumentoftype'int*',butargument2hastype'int'[-Wformat]——scanf中的%d没有以int*与之对应，也就是说没加取地址符号。•unusedvariable'x'[-Wunused-variable]——x变量没有使用。•controlreachesendofnon-voidfunction[-Wreturn-type]——控制流程到达了非void函数的尾部，即有返回值的函数（main）没有返回值。•'n'isuseduninitializedinthisfunction[-Wuninitialized]——变量n在没有初始化的情况下就使用了。看看，-Wall-Wextra的作用是不是很大呢？不过，自己小心不要犯错才是王道。巧用#语句•例如，喜欢屏幕I/O，但题目又要文件I/O，抑或相反，可以在stdio.h中#define一个自己的标记，例如我喜欢#definezaxs。之后再程序中利用#ifdef#ifndef以及#endif来将freopen语句屏蔽。例如：•#ifndefzaxs//#ifdefzaxs•freopen(...);freopen(...);•#endif•这样就可以确定提交程序后使用的是要求的I/O方式，因为评测系统不可能有你自己定义的标记。•另外，max,abs也可以用#来写•#definemax(a,b)((a)(b)?(a):(b))•#defineabs(x)((x)0?(x):-(x))•for也可以用#来缩短哦•#definerep(i,m,n)for(i=m;i=n;++i)头文件•每年的NOIP总会有人因为头文件的问题导致CE而爆0。这是很可悲的一件事。•Dev4.9.9.2.带的gcc是3.*.*版本的，对头文件检查不严格。事实上，它会自动链接某些头文件，以至于在不加某些头文件的时候依旧可以使用该头文件中的函数。•如果比赛时gcc换成了4.*.*会好很多，但是还是要自己注意。以防万一的话，可以把所有常用头文件都加上。•下面列一些常用头文件：•C:stdio.hmath.hstdlib.htime.hstring.hlimlts.h•C++:iostreamfstreamalgorithmstringqueuestacklistmapset以及上面C的头文件去.h加c的版本。注意不是所有C的头文件都有对应的C++的版本，非ansic的头文件（例如memory.h)就没有。巧用语言特性•语言特性是个比较宽泛的东西，简而言之就是这个语言的一些特殊写法。•例如，C++中可以在for的第一个语句中定义循环变量，而C中就不能。又例如，C++中可以使用“引用变量”来避免不必要的赋值。•example:int&t=g[i][j];•这里的&不是取地址，而是标明了这是一个引用，也就是说，t和g[i][j]是一回事。•将一个数组全部赋值为INT_MAX怎么写？•for(inti=0;i=n;a[i++]=INT_MAX);•判断一个数的奇偶？•x&1etc...•例子还有很多，需要同学们自己学习。比赛技巧•1、学会骗分•骗分是一门很高深的学问，也许骗得好了1=就能松松到手。•①打表•严格的说打表并不算骗分，但也是个拿分的好方法。•适用范围：数据范围不太大且输入数据较少，而朴素算法运算量又很大的题目，通常为数论题或博弈论题。•方法：使用朴素算法，将所有可能的数据对应的答案全部算出，存到数组中，直接在程序中读入数据然后对应输出既可。或者有时不是答案，而是计算中所常用的一些值，比如素数表。•注意：noip中所交源代码大小上限为100kb。比赛技巧•②卡时•卡时的要求比较高，因为clock()函数的效率比较低。•适用范围：只会打朴素算法，又无法保证AC，并且题目中有对于某类情况的特殊输出的。•方法：•若是在循环中，用循环变量判断，预估一个最大的范围，到范围就输出特殊输出。•不能准确预估范围，就用循环变量每若干次（通常为500或1000次）判断下时间，clock()/CLOCKS_PER_SEC=0.98就停止。•若是DFS，则以层数判断，方法同上。•例如：noip2012day2T2借教室可以卡时输出0•注意#includetime.h/ctime•另外，卡时不慎有可能导致丢分！比赛技巧•③分数据写算法，保证小数据得分•适用范围：在数据较小的范围内能确定某个算法是正确的并且不会超时，而对于大数据该算法又会超时，同时有一个不确定正确性的算法不会超时的情况下使用。•方法：根据不同数据写不同算法，这里不再详细说明。•不过对于这种情况，推荐使用对拍来确定算法是否正确。比赛技巧•④优化常数•在以现有知识无法继续优化算法的时候，优化程序常数也许能带来额外的若干分数。•优化方法：•自加用++i而不是i++•循环中in换为i!=n•函数参数改为typename&argu（上文中讲到过的引用，注意必须使用C++，而且不能传入表达式）•将链表换为数组（在可行的情况下）•尽量合并if语句•if语句中为true/false的可能性最大的表达式放在最前面（利用&&或||的短路性）•常用到的小函数加inline修饰（C++用法）•……比赛技巧•example1:比赛技巧•example2:比赛技巧•example3:比赛技巧•2、冷静•拿到题目后，先把所有题目读一遍，然后选择最拿手的一个先下手。•无论什么题，读题后思考3分钟再动手编程。•仔细考虑算法，必要时在草稿纸上写写画画以确保正确性。•自己构造极限数据与特殊数据对算法进行测试。•时间较充足时进行对拍（写出随机数据生成器，以朴素算法与优化算法进行比较）•仔细检查输入输出文件名对拍•在不确定优化算法的正确性时，对拍是个很好的检验手段。方法如下：•利用stdlib.h中rand()的写一个随机数据生成器data.exe，按照题目要求出数据.•写好保证正确的算法程序work1.exe，输出文件为file1.out。•写好优化的算法程序work2.exe，输出文件为file2.out。•利用windows的bat批处理文件进行对拍，代码如下：对拍•@echooff（关闭不必要回显，可删去）•:loop（跳回的位置）•data.exe•work1.exe•work2.exe（程序中已设好输入输出文件就无需管道）•fcfile1.outfile2.out•ififnoterrorlevel1gotoloop•pause（如果文件相同就继续，否则暂停）•gotoloop•另建议将读入数据中的某个数与time(0)相加作为随机数种子以保证每次的数据都不同，因为time(0)一秒更新一次，而一次对拍可能不到一秒。做题•无论对于哪一科竞赛，做题都是十分重要的，没有充足的练习不可能有好的成绩。•下面推荐几个oj：•，访问速度较慢，题目较基础•同老牌，题目数量较多，功能较好•ch.vijos.org一个专为比赛搭设的平台，是最近新开的，主要特点是任何人都可以开设比赛，并且以往的比赛可以随时开启个人模拟赛进行练习。•一个面向省选和noi的oj，题目难度较高，题目质量好，以历届题目最多著称。•，面对新手的内容较多合作•竞赛不是一个人的事情，很多时候要靠大家合作、讨论来学习。不要抱有自私的心态，认为别人会占你的名额之类的。•同学之间要互帮互助，形成良好的学习氛围和学习兴趣，对于提高成绩会有较大帮助。自学•学习信息学竞赛，自学是很重要的。•DP、Prim、Kruskal、dij、spfa、dinic、堆、C++的STL……这些东西徐老师都还没讲，而我都已经自学完了，这或许是我取得了一等的一个很重要的原因。•OI不像其他竞赛，很多时候仅靠上课的学习是远远不够的，这就需要有很好的自学能力了。•另外，做到随时随地学习也是很重要的。比如在手机中存上算法的资料，闲暇时打开来看。又比如安卓机可以装上c4droid和gccforc4droid，随时可以编程。•最后，将我所有的OI资料共享出来（由于用百度云保持了同步，还会不断更新）。•=477189&uk=505248986ThankYou!