- chjshen 的博客
2020-2022年CSP-S / NOIP考查知识点汇总
-
chjshen LV 5 @ 2023-11-3 8:33:34
2020~2023 NOIP分数线
| 年 | 1= | 2= | 3= |
|---|---|---|---|
| 2020 | 130 | 60 | / |
| 2021 | 120 | 50 | |
| 2022 | 108 | 51 | 31 |
| 2023 | 153 | 120 | 100 |
1999年～2020年CSP/NOIP提高级试题分析(网上资料)
| 序号 | 知识点 | 题目数量 | 备注 |
|---|---|---|---|
| 1 | 动态规划 | 18 | 其中11题较困难 |
| 2 | 搜索 | 16 | 大部分难题也需要用到搜索 |
| 3 | 贪心 | 12 | |
| 4 | 模拟 | 15 | |
| 5 | 二分 | 8 | |
| 6 | 最短路 | 5 | |
| 7 | 高精度 | 4 | |
| 8 | 拓扑排序 | ||
| 9 | 数论 | ||
| 10 | 倍增LCA | ||
| 11 | 并查集 | 3 | 难题特别偏爱树这类数据结构，可以多花时间学习。 |
2020年～2022年CSP-S/NOIP提高级试题分析
1.CSP-J2020～2023
| 题目 | 考查知识点 | 备注 |
|---|---|---|
| [CSP-J2020] 优秀的拆分 | 模拟 | 入门 |
| [CSP-J2020] 直播获奖 | 模拟普及− | |
| [CSP-J2020] 表达式 | 树形数据结构 | 普及+/提高 |
| [CSP-J2020] 方格取数 | 动态规划,dp | 普及/提高− |
| [CSP-J 2021] 分糖果 | 数学 | 普及− |
| [CSP-J 2021] 插入排序 | 枚举 排序 | 普及/提高− |
| [CSP-J 2021] 网络连接 | 模拟枚举 | |
| [CSP-J 2021] 小熊的果篮 | 枚举 | 普及+/提高 |
| [CSP-J 2022] 乘方 | 模拟 基础算法 | 入门 |
| [CSP-J 2022] 解密 | 普及− | |
| [CSP-J 2022] 逻辑表达式 | 模拟栈 | 普及+/提高 |
| [CSP-J 2022] 上升点列 | DP | 普及/提高− |
| [CSP-J 2023] 小苹果 | 枚举数学 | 普及− |
| [CSP-J 2023] 公路 | 枚举，贪心 | |
| [CSP-J 2023] 一元二次方程 | 模拟 | 普及/提高− |
| [CSP-J 2023] 旅游巴士 | 图论 | 普及+/提高 |
2.CSP-S2020~2023
| 题目 | 考查知识点 | 备注 |
|---|---|---|
| [CSP-S2020] 儒略日 | [模拟],[数学][二分] | [普及+/提高] |
| [CSP-S2020] 动物园 | [数学][贪心],[进制][位运算] | [普及/提高−] |
| [CSP-S2020] 函数调用 | [动态规划,dp][数学],[拓扑排序], | [提高+/省选−] |
| [CSP-S2020] 贪吃蛇 | [贪心],[堆],[队列] | [NOI/NOI+/CTSC] |
| [CSP-S 2021] 廊桥分配 | [贪心],[set][堆] | [普及+/提高] |
| [CSP-S 2021] 括号序列 | [区间 DP],[组合计数] | [提高+/省选−] |
| [CSP-S 2021] 回文 | [贪心],[拓扑排序][枚举] | [普及+/提高] |
| [CSP-S 2021] 交通规划 | [二分图匹配][区间 DP][平面图][最小割][最短路] | [省选/NOI−] |
| [CSP-S 2022] 假期计划 | [广度优先搜索,BFS] | [普及+/提高] |
| [CSP-S 2022] 策略游戏 | [贪心],[线段树],[st表] | |
| [CSP-S 2022] 星战 | [哈希, hash] | [省选/NOI−] |
| [CSP-S 2022] 数据传输 | [动态规划,dp][树链剖分][矩阵乘法] | |
| [CSP-S 2023] 密码锁 | 枚举 | [普及−] |
| [CSP-S 2023] 消消乐 | DP，栈 | [提高+/省选−] |
| [CSP-S 2023] 结构体 | 模拟 | |
| [CSP-S 2023] 种树 | 二分，树结构 | |
3.NOIP2020～2022
| 题目 | 考查知识点 | 备注 |
|---|---|---|
| [NOIP2020] 排水系统 | 图论 高精度 拓扑排序 | 普及+/提高 |
| [NOIP2020] 字符串匹配 | 字符串 倍增 哈希, hash | 提高+/省选− |
| [NOIP2020] 移球游戏 | 构造、分治 | 省选/NOI− |
| [NOIP2020] 微信步数 | 多项式 | |
| [NOIP2021] 报数 | 质数筛原理 | 普及/提高− |
| [NOIP2021] 数列 | DP | 提高+/省选− |
| [NOIP2021] 方差 | 搜索，DP | 省选/NOI− |
| [NOIP2021] 棋局 | 并查集，线段树 | NOI/NOI+/CTSC |
| [NOIP2022] 种花 | 枚举前缀和 | 普及+/提高 |
| [NOIP2022] 喵了个喵 | 贪心构造Ad-hoc | 省选/NOI− |
| [NOIP2022] 建造军营 | 树形 dp 强连通分量 Tarjan 容斥 | 提高+/省选− |
| [NOIP2022] 比赛 | 线段树 | 省选/NOI− |
某金牌选手备战NOIP经验
备战NOIP的同学们注意啦！今天给大家带来了国际冠军的备赛攻略~
一般NOIP级别的题目代码都比较短，没有那么复杂。如果同学们想要在NOIP比赛中不因代码能力吃亏的话，可以着重考虑提高以下几点。
一.掌握基础算法
NOIP最基础的一些算法有最短路算法、基本的线段树树状数组、图论的BFS、DFS等。虽然对于初学者来说，它们的代码可能有点长，但其实理解后还是非常容易记住的。
熟练掌握后，大家在比赛中如果遇到这类型的题目，就可以快速地用基本算法的模板去写正确。
掌握算法思维及常见套路
基本算法难度较低，大部分选手基本都能掌握。区分选手的关键在于是否掌握算法思维及常见套路。
同学们可以在日常训练中多做总结，比如常见的套路、算法思维有哪些，常见的应用是什么。若想完全掌握，做完总结后仍需进行反复的刷题训练。
二.充分掌握STL
一般学生参加NOIP选择的都是C++语言，C++有一些STL，就是内置的已经实现好的数据结构，比如set、map及其他相关数据结构。
这些数据结构如果不用STL，在考场上手写会比较耽误时间，而且大部分情况下，一般题目也不需要特别复杂的一些数据结构的功能，所以STL基本能够胜任比赛的要求，尤其是对于NOIP级别的题目。
充分掌握STL能够帮助大家在NOIP级别的比赛中提升写代码的速度及准确性。
三.总结常见错误
在平时训练过程中，大家需要总结一些常见的错误。
比如大家在平时刷题时经常会出现交到OJ上，它返回Wrong Answer或者TLE的问题。有时这些错误是一些比较低级的错误，比如数组大小开小了或者函数忘记return了。
所以大家如果要提高代码能力，很重要的一点就是减少这类低级错误的发生频率，这样可以大大减少调试的时间，从而省出更多的时间来攻克更难的题。
四.提高调试能力
- 调试能力是指怎么从一个错误的代码里快速得找出错误的点。
调试一般有两种策略，一是使用一些调试器，比如GDB；二是用输出调试的方法，就是把程序中间的这些数组，还有一些变量的值全都打印出来，然后用手算的结果去对比。
这里面其实有很多的技巧，比如可以用类似二分查找的方法去定位程序中的错误所在，这样的能力需要在平时去不断地培养。
- 学习规范的编程技巧
基本功是解题的基石，同学们一定要注意学习相对规范的编程技巧。规范对后期代码的调试及后续对题目的复习都有极大的帮助。
比如清晰得写下函数或变量名。如果在写代码的时候，只是一拍脑袋随意命名，很容易造成在后面检查代码或调试代码时浪费过多的时间。
五.提高分类讨论及分析边界情况的能力
分类讨论是指能够有清晰的思路把一道题的多种情况都分析清楚，尤其是对一些比较复杂的题目。
分析边界情况的能力是是如何能写出可以覆盖到所有边界情况且完全正确的代码。
费曼学习法
https://baike.baidu.com/item/费曼学习法/50895393?fr=ge_ala
历年NOIP中的搜索题