Everybody in this country should learn how to program a computer… because it teaches you how to think.

---Steve Jobs

人都应该学习编程,因为它教人如何思考---乔布斯
deepstudy.net
深学汇
    
    
献给各位初次参加noip的新生们——个人经验分享
来源:百度贴吧 | 作者:深学君 | 发布时间: 2017-04-15 | 2184 次浏览 | 分享到:

 




    前 言


    本文是我对去年那次失败的noip之旅的一个总结,主要针对初次参加noip的普及组新生。总结了去年的教训,也参考了一部分神犇的资料,希望能给各位新生们一个参考。如果有什么遗漏或者错误,请在楼中楼中指出,感激不尽!


    目前距离noip2017还有不到半年的时间,这半年可以干很多事,这也就是我接下来要说的。送给大家一个公式: 


    竞赛成绩=实力x经验


    给大家解释一下这个公式。我有一个同学,可以算是神犇级别的了吧。他的竞赛实力相当牛b,单源、DP什么的伪代码能轻松默下来,红黑树、博弈论甚至FFT都能讲得头头是道,而且仅仅是一名初二学生!


    去年他参加了noip普及组的比赛,结果出人意料——只有第一题分解质数(好像叫这个名吧...)得了10分,其他题全部爆0。事实上,他所有题都做了,但是他是抱着AK的心来的,所有的题他都是只过了样例就去做下一道了。你们也知道的,CCF的样例向来都很弱,尤其是去年...他竞赛实力弱吗?一点不弱,他是我们那个考场唯一一个文化之旅写了SPFA这个正确算法的人,但是,很可惜,由于某变量忘记置0导致爆0,考试结束的时候甚至连样例都没试。


    第一题,一个逻辑错误;第二题,某情况下变量加不+1但是没考虑;第三题,强行按照自然数拆分的办法写的DFS;这些错误很小,但是这千里之堤就毁于小小的蚁穴了!他的竞赛实力很强,但是做题经验几乎为0,他几乎所有的时间都用在了研究算法上,很少做题。


    我相信看我这篇文章的同学里也有类似,一段代码出来,大的框架没有问题,就是WA(1),后来抓耳挠腮找了几个小时才发现就是诸如变量初值,变量置零,递归形参、局部全局变量用错这样的小问题。实不相瞒,我直到现在依然如此。为什么?答案很简单,做题少了!做的题多了,错误出得多了,也就有经验了,熟能生巧吗!
    拿到一道题,有经验的人会先按照人类处理该问题的思维去构造一个数学模型,然后去掉不必要的模拟,找可行优化,选用合适的数据结构和算法去实现,整个过程10多分钟就好了,绝对比你边写边想算法犯了逻辑错误去查几个小时要划算!


    呵呵,说的偏了,但都是大实话。前言的最后送给大家几句话:


   
   不要好高骛远,即使是大神的第一次也不会顺风顺水;
    不要掉以轻心,即使是NOI也有忘记删调试输出、变量打反、没用文件这样错误的人;
    不要垂头丧气,CLJ也是高三才拿到IOI冠军!我们还年轻...


 
    考场瞬息万变,有不会做的题很正常。平心静气,先做简单的题,如果一道你有正确算法的题答案却不对,很可能是小错误,不要轻易放弃做别的题,那样可能会让你直到考试结束一道题也没做出来。
    多做题,多思考,心要静!


    
  注释:(1)oj上的测试结果。
    WA
wrong answer 错误的答案
    AC
Accepted答案正确;通过
    TLE
Time Limit Exceed 超时
    OLE
Output Limit Exceed超过输出限制
    MLE
Memory Limit Exceed超内存
    RE
Runtime Error运行时错误
    PE
Presentation Error格式错误
    CE
Compile Error无法编译

 

    初 赛


    初赛的考察内容的一部分是计算机的基础知识,比如进制转换,工作原理,算法原理、历史事件名人等。这些对于大部分第一次参加noip的同学来说应该比较陌生,这样的知识只能通过平时的积累,从现在就开始搜索资料,有意识的去记忆。


    另一部分是数学内容,包括排列、组合等大概高中的数学知识,需要下载资料去研习,背公式。
    最后一部分是程序完成。如果说前面2部分还有补习的希望,最后这一部分完全是靠你的做题基础,没有捷径,只能靠你平时多做题,对部分简单算法有些了解。
    
    初试形式为笔试,描述语言为C/C++Pascal。各省市初试成绩在本赛区前百分之十五的学生进入复赛,其分数不计入复赛的成绩。初赛时间为10月的第三个星期六下午2:30 - 4:30举行。


      1
、选择题:共20题,每题1.5分,共30分。每题有4个备选答案。试题内容包括计算机基本组成与原理、计算机基本操作、信息科技与人类社会发展的关系等等。(普及组为20道单选题,提高组为10道单选题和10道不定项选择题,不定项选择题与答案完全一致才得分,多选或少选均不得分)


      2
、问题求解题:共2题,每题5分,共10分。试题给出一个叙述较为简单的问题,要求学生对问题进行分析,找到一个合适的算法,并推算出问题的解。答案以字符串方式给出,考生给出的答案与标准答案的字符串相同,则得分;否则不得分。


      3
、程序阅读理解题:共4题,每题8分,共32分。题目给出一段程序(没有关于程序功能的说明),有时也会给出程序的输入,要求考生通过阅读理解该段程序给出程序的输出。输出以字符串的形式给出,如果与标准答案一致,则得分;否则不得分。


      4
、程序完善题:共2题,第一题10分,共4空,每空2.5分;第二题18分,共6空,每空3分。两题共28分。题目给出一段关于程序功能的文字说明,然后给出一段程序代码,在代码中略去了若干个语句并在这些位置给出空格,要求考生根据程序的功能说明和代码的上下文,填出被略去的语句。填对的,则得分;否则不得分。

    复 赛


 
    考前准备:


    草稿纸考试一般会发放,比较大,需要你带一、两支笔。应该可以带水,但是别喝多了,貌似上厕所比较麻烦。考试这几天就不要再学习新的东西了,时间不够,学也学不精,反而是浪费时间。建议自主复习一下旧的知识,比如字符串处理、快速排序这样的知识。头天晚上不要嗨到太晚(熬夜打DOTA、窜宿舍泡妹纸什么的...),早点睡。第二天大概6点左右就起床吧,剩下的时间根据需要调配,早饭、午饭大概8成饱就足够了,考试前记得上个大号- -哦对了,参赛证千万别丢了!建议快考试的时候再挂到脖子上(我们这有个仁兄把准考证弄丢了- -最后怎么解决的不知道),平时别拿出来显摆。还有就是一般住宿的学校会给你学校的平面图,考场在哪、食堂在哪、宿舍在哪一定研究明白了,别找不到地方就蛋疼了...


    比赛提前30分钟进场,熟悉考场环境,找到自己座位及厕所位置,更改软件、系统为自己所喜欢的设置,如:取消桌面背景、更改屏幕分辨率、更改虚拟内存等。利用熟悉考场时间写下重要且易错内容,如:快速排序(Qsort)、文件操作命令等。试题解压密码会影响一个人的心情,一定要一次输对,注意大小写,不要边输入边检查,要对自己有自信。


    禁止携带U 盘、MP3、计算器、手机等任何与存储、计算、通信有关的电子设备;禁止携带一切书籍和其他无关物品;一经发现按作弊处理。


    还有,考前一定要看《骗分导论》!!!


    就这些吧... 

 

    常见问题解答


    Q1
:普及组的题目难度分配是怎样的?
    A1
:第一题是相对简单的题,但是一般会有操作起来较麻烦,考虑情况很多,数据类型很大这样的特点来考你。
第二题是模拟,需要你抽象化问题,把问题的人工解决方法模拟出来,建立一个合适的数学模型,再用代码动手实验它。模拟的题一般比较麻烦,出错多很正常,甚至3个小时你不一定能解决一道模拟。
    (对于建立数学模型,我要说说。比如,在一个n米长的马路上种以m为间距种树,问能种几棵,建立数学模型后实际就是在一个长度为n的线段上间距为m的点有多少。把路抽象为线段,把树抽象为点,这就是建立数学模型。很多问题都要转化成数学语言才能被计算机所模拟。)
第三题是一个跳板,一般是考不难的DP 图论 搜索,需要有足够的算法知识和做题经验。
第四题相对比较难吧,会考一些像单源最短路“SPFA”这样的比较高级的算法,所用到的数据结构也会比较高级,对于技巧、经验和心理都是一个考验。
对于各位新生来说,不妨放弃34两道题,第一题和第二题AC了也能有200分,骗骗分,拿一等问题不大了。


    Q2
:拿到试卷后该做些什么?
    A2
:不要着急下手做题,先浏览一下试题,对题目的难易有个把握,哪些题目自己能做出来心里要有数。先做相对简单的题,做题之前先在纸上写写画画,优化可不可行什么的都要试一下。
    然后,看看哪些题目可以简单的骗分(比如没有答案就输出-1这样的),先把骗分程序写一个拷贝到对应文件夹下,等到考试最后你忙着做题就没时间写骗分程序了。可以骗分程序一般都是难题,所以...
    再有,有时候你看到一个题后脑子里蹦出另外一个相似的题。这个时候切记生拉硬套把那道题的算法搬过来。因为那样的话会把你引导入一个误区,很多人进入误区就出不来了,最后导致写出的代码总是WA,那时候再改就来不及了。
    不要一上来就抱着全部AC的心,那样会给你添加压力。摩天大厦也是一砖一瓦盖起来的,一步一步来!


    Q3
:写出来的程序总是WA,怎么办?
    A3
:这是我去年犯的一个错误。就此给大家几点忠告:
 


      1
不要写自己没有把握的算法。说起这个让我想起了丽洁姐写强联通分量的事...还是我那个同学吧,SPFA这个算法他不久前才学的,根本就没有学精,看到题以后也不想就开始写SPFA,然后各种调试调到比赛结束,交了一个连样例都时间过的程序上去了。其实他想过写一个搜索,但是他担心那样拿不到多少分(事实证明他想多了...shit 我永远的痛),就放弃搜索。一个不熟悉的算法,很多问题是你还没有发现到的,因为你不常写。所以现场出了问题是很麻烦的。


     2
调试。 第一种调试是编译器自带的监视变量,这里我就不一一说了。第一种有个缺点,有些数据你监视后会发现监视窗口的值和变量实际值一点也不搭边,各种奇怪的值...比如我的fpc2.4.0……第一种调试一般会伴随着单步运行,看看程序卡在哪里什么的。
第二种调试是调试输出,比如你发现答案不对,怀疑是某个在循环中值会发生改变的变量的问题,那你就在循环中加一个输出语句,用一个相对简单的测试数据,看看输出的该变量值和你人工模拟的值对不对。多加几个调试输出,可以清楚的发现问题发生在哪里。不过,等要交程序的时候一定要把调试输出等和程序无关的语句删掉或者注释掉,接着运行,看看答案对不对,然后保存(很重要),把源程序移动到题目文件夹下。


     3
小问题解决。看一下你的程序中,变量置0了吗?变量置零语句的位置对不对?DFS的循环变量应该用局部变量你是不是用的全局变量?(我被这个坑过...调试了1个多小时)是不是有的极限情况没想到?是不是当达成某一个条件时就不用使计数变量+1或者-1了?是不是你的某个优化取余数mod错了?……等等,这些小问题最好的避免方法就是比赛前多做题!
4
样例是会骗人的!我会告诉你某同学的3个程序样例都过了但是都爆0了吗...样例有时候也是会骗人的,一定要自己多出几组数据测试!

 

    Q4:经常听他们说对拍,对拍是什么?
    A4
:对拍是一种对照调试程序,用于比较2个程序对于相同测试数据的结果是否相同。比如你写了个高效的算法,但是不知道对不对;你又写了个效率很低但是不会出错的算法,你就可以使用对拍比较,看看2者答案相同与否。对拍可以检验出程序的正确性,但是一定要保证对拍的2个程序中有一个是绝对正确程序!


 
    下面说说对拍怎么用。对拍是用批处理命令(.bat)来完成的,需要你在任意地方建立一个文件夹,文件夹下面要有这几个个东西:


      1
你的对拍.bat命令
      2
数据生成器 用你的编译器写一个可以生成一组格式正确的测试数据的程序,编译成exe文件(生成的数据要保存在一个文件中,如 xxx.in 你的2个题目程序就用xxx.in作为输入源)
      3
你的2个程序,要用文件输入输出
      4 xxx.in
作为被调试的2个程序的输入文件(事先需要自己手动建立一个,否则报错)
      5
算法1.out和算法2.out 2个程序的输出文件(也要自己手动建立 否则对拍会报错)

    接下来,我写一个相对简单的对拍批处理命令,把它写进记事本里,然后保存把文件后缀改成.bat就可以。
     
@echo off
   :loop //
定义一个可被goto的标签loop(好像是这样的吧...
   数据生成器.exe //先运行数据生成器生成数据,否则xxx.in为空
   算法1.exe
   算法2.exe //你的2个程序,顺序不重要。运行后自动读取xxx.in中的测试数据
   fc
算法1.out 算法2.out //要比对的2个输出文件
   if not errorlevel 1 goto loop
   pause
   goto loop

    本对拍程序是不断循环执行以上语句,直到二者答案不相符就停止运行。这时选手可以查看xxx.in内的数据,并对此作出修改。其实就是一个自动比对答案的东西。
    以下是一个完整的对拍文件夹内的文件:


 



     编者赠给大家的话


         CLJ
大神第一次参加noip的时候,貌似只拿了省三等,140


  
    我第一次参加noip的时候,只拿了100分,压线省一等 - -


 
    这告诉我们,强省和弱省的差距...咳咳...不对...


 
    每个人都会有失败,那些神犇也是在失败中成长起来的。他们也会做不出题,也会犯低级错误,也会爆0,也会打反变量名...不过,他们没有因此而放弃,而是继续坚持。OJ上遍布着他们的足迹,信念与梦想支撑着他们翱翔。天赋不代表什么,后期的努力永远要比天赋重要!(王强松?方浩强?...


  
    假如失败侵袭了你,不要悲伤,不要心急!失败的日子里需要镇静;相信吧,成功的日子将会来临!


  
    心儿永远向往着远方,现在却常是忧郁。一切都是瞬息,一切都将会过去。而那过去了的,就会成为亲切的怀恋!

     祝愿各位能在noip2017中取得好成绩!