hello

Menu

关于noip

应邀写点noip注意事项:
1. 考前一年,认真学习各种算法,所谓技多不压身,你学的知识越多,视野就越开阔,在考试时一道题目的完成情况不取决于你能不能用正解AC,只取决于你拿了多少分,学得越多,你能想到的东西越多,就越有可能拿更高的分数。有时候一个题目没有思路,就骗分吧,用一些旁门左道取得最优的分数即可。
骗分讲究技巧,有些骗分的东西其实上也是一个算法。其中包括:

2.随机化贪心我只写过一遍,但是能感受到那种微妙,可以自己去找一题裸题练练就懂。模拟退火推荐知乎专栏(https://zhuanlan.zhihu.com/p/23968011),模拟退火是一个高逼格的玄学操作,看似不可能,实际上用相同的时间可以解决大多数情况【意思就是不论n=1还是n=100000,用的都是一样的时间得出最优解】,听起来很难,但做法非常划水,写一遍大概就能懂了。

3.贪心暴力这种老生常谈的东西,考试的时候实在没办法就暴力出奇迹了,有阶梯数据的时候请把代码写成

4.另外,请不要嘲笑打表,这可能会在考试的时候成为关键的节点,许多斐波那契数列的题目都是采用打表【或者区间打表】,打表的题目适用于一个输入有且只对应一个输出的情况,而且最好只有一个输入【有时候两个输入也还受得住,可以开二维数组】。比如斐波那契数列就可以用f[1]=1,f[2]=1,f[3]=2……。而像noip2017的第一题,也可以用二维数组获得一部分分数。区间打表适用于当你有办法算出一小部分,却没办法在规定时间内算出一大部分的时候,比如要找第10000100个斐波那契值,那么你可以存f[1],f[2],f[1000000],f[1000001],f[2000001],f[2000002],f[3000001],f[3000002]……,这样就把前面1kw个的计算时间留在考场,评测的时候只需要从第f[10000001]和f[10000002]开始加出来就行。

5.考前半年,如果你对你的算法能力有一定信心,那就少打游戏多撸题【毕竟现在信息学省一越来越不值钱,尽早拿才是唯一的出路,估计以后至少要铜牌高校才有优惠了】。

6.有些算法并不是学会那么简单,它的思想更为重要,比如快排中的二分操作,堆排、归排的玄学应用【差分,归并树之类吧(身为蒟蒻没有用过】,用三分来计算函数的极值,DFS、BFS这种每场考试都要用的东西更是不用说

7.算法除了以上这些加粗的,大概需要:前缀和拓扑排序拓展欧几里得欧拉函数辗转相除法快速幂矩阵乘法克鲁斯卡primdijkstrafloydSPFA分层图tarjan(割点、割边、LCA、强连通分量)、二分图2-SAT线段树(推荐zkw线段树)、树链剖分(似乎近几年很喜欢这个算法)、倍增(st)、分块(单调栈)、队列(双端队列优先队列)、(priority_queuemake_heap)、DFS序字典树KMP欧拉回路马拉车算法尺取法hashhash线段树Miller_Rabbin算法并查集(带权并查集)、树状数组高精度字符串hash匈牙利算法筛法树的重心DP(状压dp,邮局dp,LCS,LIS,LCIS,数学期望类,区间dp,线性dp,背包类)、主席树

8.如果有兴趣还可以学习一些省队级别的算法,以上只是我个人学习过的一些算法,不表示任何范围。

9.一定要熟练各种STL的神操作,毕竟set,map里面的红黑树不是你考试想写就写出来的 (

10.考前一个月,放松放松,做点初赛题压压惊,初赛题考的都是一些计算机基础知识,代码部分有时候不会做联系上下文都能猜得到答案,所以不要慌张,慢慢做完就行。考试前把历届题库写几遍,错题挑出来重做几遍,一个月里每天花个一两个小时做应该就够了,考场尽量高分【要是不小心满分还可以回学校和学弟装个逼

11.考试前一天,这天应该会到场熟悉,这个熟悉环节不能当作娱乐,一定要认真对待,进入考场首先要了解厕所位置要找到那几台linux的机子位置(如果你是win选手那就看下一条吧),因为八九不离十你考试也就这几个位置坐着了,毕竟每年福建不足十台的linux选手机子都是我们学校预定了七八台,这也是有好处的,万一你程序在win过了,在linux没过不就很尴尬。坐下来把自己的开发环境调到自己满意的状态,然后尝试写个程序,比如输出“老子今年要AK”,比如写一段sum的程序用于计算a+b,用文件读入,建立子文件夹等操作跟随考试须知走一遍流程。

12.考试该注意的点,根据以往的惨痛经历得来的经验,大致有以下这些内容:

13.考完第一场千万不要刷各种论坛,知乎贴吧什么的千万不要打开!无知者无畏。

最后希望一中的各位学弟(应该没有学妹我记得)屠场noip2018

及时当勉励,岁月不待人。

— 于 共写了2198个字
— 文内使用到的标签:

2条回应:“关于noip”

  1. Lin-qlpnil说道:

    大佬什么时候列出常用STL。

发表评论

电子邮件地址不会被公开。 必填项已用*标注