2017年NOIP初赛已经落下帷幕,祝愿大家都能如愿进入NOIP复赛.由于初赛分数不计入复赛,所以复赛的上机测试才是真正决胜的环节,那么如何利用好这最后一个月的时间呢?此时做什么是最有效的?
了解命题趋势和必得分数（以北京为例）
NOIP逐步淡化对算法的考察,更侧重考察思维.已经不是说学习的算法越多,成绩就会越好.最近2年考察的模板算法很少,只有LCA有背的价值,像二分,dfs原理都非常简单,理解即可.信息竞赛中最适合考察思维的莫过于动规与贪心,由于贪心要么太显然大家都看得出来,要么太难只有极少数人能发现,所以贪心的区分度较低,因此动态规划理所当然的成为了NOIP复赛的宠儿,基本每年都会有1道动态规划的题目,甚至一年2道.最近动规题目的考察也不再是最基本的背包问题,像16年与期望相结合与状态压缩相结合,都进一步加大了思考的难度.
一般来说,在北京拿到320分,就能获得一等奖.如果1,2题难度高,分数线会有小幅下降.我们来简单算一下得分,两天的第1题拿满分,第2题第3题各拿30分,总共得分320分,一般是可以压线一等奖的.也就是说2道第一题拿稳,再保证其他题暴力的分数都拿到手就是一等奖.而如果第1题丢了40分,这就需要有道题得分从30分变到70分,而2,3题得70分的难度远远高于第1题拿满分的难度.因此比赛中没有失误比什么都重要.
这些问题你存在吗?
1.题目编程量少
算法学习了很多,但不熟练,甚至学习过后都没有亲自写过.看似学了不少知识,但只知道大概,所以限时编程就各种出错,短时间内也调试不出来.如果想获得一等奖,一般有价值的题目需要刷过200道左右,如果想进省队,有价值的题目至少刷过500道.不少金牌选手的刷题数量都不低于2000道.
2.一些基本函数不会使用甚至没听说过
上课期间还有人在手写快速排序,完全是在浪费时间,还增大出错风险.了解常用函数会让编程更加简洁并减少出错率.至少以下函数希望同学能了解会用: sort, min, max, swap, abs, fabs, memset, make_heap, pop_heap, push_heap, sort heap.再简单举个例子,去年day2第2题蚯蚓,加个堆维护最大值,时间复杂度O((m+n)log(m+n)),都不需要思考轻松拿到85分.而堆在STL中是可以直接调用的,一共写完不过40行.
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# define FOR(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;
const int NR = 7100000;
int n, m, q, u, v, t;
int a[7101010];
void solve()
{
make_heap(a, a + n);
FOR(i, 1, m){
const int tmp1 = a[0] + q * (i - 1);
const int tmp2 = (long long)tmp1 * u / v;
pop_heap(a, a + n + i - 1);
a[n + i - 2] = tmp2 - q * i;
a[n + i - 1] = tmp1 - tmp2 - q * i;
push_heap(a, a + n + i - 1);
push_heap(a, a + n + i);
if(i % t == 0) printf("%d ", tmp1);
}
puts("");
sort_heap(a, a + n + m);
for(int i = n + m - t; i >= 0; i -= t) printf("%d ", a[i] + q * m);
puts("");}int main(){
freopen ("earthworm.in", "r", stdin);
freopen ("earthworm.out", "w", stdout);
scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
FOR(i, 0, n-1) scanf("%d", &a[i]);
solve();
return 0;}
3.不了解STL容器瞎用
可能是之前看过某些题中这些结构用起来很厉害,就老想使用这些结构,比如vector, deque, list, stack, queue, priority queue, set, map.建议还未完全了解这些容器性质和成员函数前先不要使用,否则往往不如手写数组运行速度快.先把数组学好,数组更好操控,也完全能实现这些功能.
4.模板化算法
套路性优化掌握不熟练.20分钟写不出来二分答案是非常有问题的.写一个成形的算法模块,应该不需要思考,纯粹是敲代码的时间,比如 二分, dfs, bfs, Floyd等都是最基本最基本的算法,考试时闭着眼睛都得敲出来.套路性处理比如, 最大值最小或最小值最大应该考虑二分答案, 多次求区间值考虑差分前缀和, 需要logn可以尝试加个堆优化,或者倍增等等.
5.细节考虑不周
比如某个数组大小开小了,多次输入时数组没清零,判断条件是否有等号,多个判断是否需要else if,题目输入n,m,v,e,编程时是否记清每个含义不用混,3个小于10亿的数相加取余时是否在算完2个的和时取余了.这些都是细节,但如果有一点没注意可能就少了30分,甚至这道题一分没有.
减少出错,树立自信
在这最后的一个月,没必要花时间再看自己不会的算法,只有非常小的几率正好考中你学的算法,收益极低.如果还没做过近3年NOIP真题,优先把真题做一遍,真题的难度把控和算法要求远比模拟题好,一定要限时完成,最好就在周六日上午8:30-12:00,感受考试时间,只有在限时的环境下才能得出最适合自己的时间分配策略.本站也会持续更新NOIP复赛历年试题和复习知识点总结,欢迎大家关注.如果已经做过近3年真题,可以选择图论或动态规划之一重点刷题,一个月的时间是可以做20题以上的.不要看题解,独立思考,编完检查完毕再提交,尽量一次性AC,不要反复提交通过评测网站查找错误,毕竟考试只有一次机会.最后的最后,上考场前一定要相信自己,题目万变不离其宗,丰富的做题经验会让你考试中游刃有余.
支付宝扫一扫
