作者：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++
最后来看个视频呗~