作者:xzqiaochu
原文地址:https://www.xzzhangqiaochu.top/?p=142 (转载请注明出处)
最后修改时间:2019/11/15
目录(点击可跳转)
1. 近两年试题详细分析
NOIP2018
Day1
序号 | 名称 | 类型 | 算法 | 难度 | 部分分 | 备注 |
---|---|---|---|---|---|---|
A | 铺设道路(road) | 模拟 | 模拟、贪心 | 普及- | —— | —— |
B | 货币系统(money) | DP | 背包DP | 普及+/提高 | DFS(80分) | —— |
C | 赛道修建(track) | 树 | 二分答案、贪心 | 省选/NOI- | 树的直径+一条链+菊花图(55分) | 菊花图可能会把DFS卡掉,要求出树的直径优化二分上界 |
Day2
序号 | 名称 | 类型 | 算法 | 难度 | 部分分 | 备注 |
---|---|---|---|---|---|---|
A | 旅行(travel) | 树/基环树、DP | 树形DP、暴力删边 | 提高+/省选- | 不做基环树的情况(60分) | 要先跑DFS求出环 |
B | 填数游戏(game) | 找规律 | 打表找规律 | 省选/NOI- | 小数据打表(20分)、再推推稍容易的式子(65分) | —— |
C | 保卫王国(defense) | 树、DDP | DDP | 省选/NOI- | 每次都重新DP(44分) | 44分的做法即使再优化(比如LCA、只更新修改的子树),还是44分 |
题目类型统计(如果一道题涉及多个方面,会有重复统计):
- 模拟/贪心:1题
- DP:3题
- 树/图:3题
- 数据结构:0题
- 技巧/数学:1题
可以拿到的分数:100+100+55+60+20+44=379(简单题不粗心、难题暴力)
一等奖分数线(江苏省):310 分
NOIP2017
Day1
序号 | 名称 | 类型 | 算法 | 难度 | 部分分 | 备注 |
---|---|---|---|---|---|---|
A | 小凯的疑惑(math) | 数学 | 推公式、打表找规律 | 普及/提高- | 完全背包DP(60分) | —— |
B | 时间复杂度(complexity) | 大模拟 | 大模拟 | 提高+/省选- | —— | 这题要调试好久~ |
C | 逛公园(park) | 图论、DP | 最短路、DP | 省选/NOI- | $k=0$ 时答案为最短路方案数(30分)、不考虑 $0$ 边(60分) | —— |
Day2
序号 | 名称 | 类型 | 算法 | 难度 | 部分分 | 备注 |
---|---|---|---|---|---|---|
A | 奶酪(cheese) | 数据结构 | 并查集 | 普及/提高- | 完全背包DP(60分) | —— |
B | 宝藏(treasure) | 图论、DP | 状压DP | 省选/NOI- | —— | —— |
C | 列队(phalanx) | 数据结构 | splay | 省选/NOI- | 暴力(30分) | —— |
题目类型统计:
- 模拟/贪心:1题(大模拟)
- DP:2题
- 树/图:2题
- 数据结构:2题
- 技巧/数学:1题(简单题)
可以拿到的分数:80+100+30+100+20+30=360
一等奖分数线:290 分
2. 近五年题目统计
年份 | 模拟/贪心 | DP | 树/图 | 数据结构 | 技巧/数学 |
---|---|---|---|---|---|
2014 | 2 | 1 | 2 | 0 | 1 |
2015 | 1 | 1 | 1 | 1 | 0 |
2016 | 1 | 2 | 1 | 0 | 1 |
2017 | 1 | 2 | 2 | 2 | 1 |
2018 | 1 | 3 | 3 | 0 | 1 |
趋势预测 | 1 | 2 | 2 | 1 | 1 |
(注:“趋势预测”仅供参考)
没考过的算法:tarjan/二分图/快速幂/网络流/字符串…
3. 应试技巧
(以下为个人总结,仅供参考)
各种类型题目的要求
- 贪心:快速/准确
- 大模拟/搜索:查错能力
- 智力题:RP/心态
考试流程
- 到达考场后,先设置好dev c++,并建立所需目录
- 浏览一下考试要求文件
- 有空的话可以先默写一些模板
- 下发试题后,浏览一下试题文档首页的相关信息
开始做题:
- 先做第 1 题
- 大致看看第 3 题,考虑一下写正解还是暴力,并估算一下所需时间
- 开始做第 2 题,要为第 3 题预留足够的时间
- 全部完成后,对每题的程序进行查错/优化,并造一些数据进行测试(最后半小时)
笔者做题的目录结构
注:一定要看清楚哪些分区是关机不会还原的
- dev目录:第一遍写程序的目录
- 最终提交目录:dev完成后,要先通过读写文件测试才可放入
- debug目录:二次查错/优化目录
4. 其他
开无限栈
编译命令如下
g++ testcpp -o test.exe -Wl,–stack=536870912
(后面跟字节数Bytes)
英文单词拼写
- algorithm:sort等头文件
- priority_queue:优先级队列
- utility:pair头文件
- next_permutation:下一个排序
- stable_sort:稳定的排序
- operator:运算符重载
一些资料
预祝各位RP++
最后来看个视频呗~