###### NOIP复赛简介
全国青少年信息学奥林匹克联赛由中国计算机学会统一组织，是一项面向全国青少年的信息学竞赛和普及活动，旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀的计算机人才。NOIP 在同一时间、不同地点以各省市为单位由特派员组织。全国统一大纲、统一试卷。官网：[http://rg.noi.cn](http://rg.noi.cn) > 本题单中包含了2019年CSP-J2比赛中出现的所有题目供用户练习
###### 2019年CSP-J2真题当中后两题的梳理
* 《纪念品》，动态规划，但是比较套路，是完全背包的变形。 * 《加工零件》，图论最短路-考察建图。也可以用魔改 BFS 求解。
###### 真题分析
从历年真题看，动态规划占的比例是比较大的，而且经常是每年最难想的题目。动态规划只有背包问题是被总结的比较好的套路，其他基本上都是一题一法，所以动规的准备方法只能是刷题。图论和树上问题，很明显是最近几年难度提升的方向。2020 年出现了比较难的树上问题《表达式》，这种问题以前都是在提高组才会出现的。还有 2021 年 CCF-Online 赛出现了非常复杂的考察建图能力的《重力球》。而且，我感觉出题老师还是有点顾忌在普及组出特别难的算法知识点的题目的，所以这几年所有的最短路的题目，都有 DFS 或者 BFS 的巧解。但是，如果选手没有吃透最短路的一些基本思想和原理，这些巧解也是想不出来的。除了动态规划和图论，需要重点练习的，还有搜索题目。练习搜索题目，并不一定是说会直接考搜索的类型题，而是要在想不出正解的情况下，学会用搜索拿部分分。
###### 怎样复习
动态规划的复习，首先可以从真题出发，先把历年 NOIP 普及组真题中的动态规划题目都搞熟。有些难题，一下子想不出来没关系，可以看两眼题解，然后自己再想，逐渐锻炼能力。图论的复习。图论，在教学当中我是一直强调要讲证明、讲原理的。正如前文所述，图论的题目经常需要巧妙建图或者巧解，能想到巧妙的方法，本质上是对经典算法的根本思想，根本原理要吃透。如果只是把算法背下来，是解不出题目的。所以，图论的复习，应该从证明开始。找到最短路算法在《算法导论》的严格证明，每个细节都要看懂。吃透之后，一定会对开拓思路大有裨益。
###### 强调复习方法
一定要自己觉得完全没问题了再提交。写完之后，自己拿测试点反复测试，反复用眼睛看代码查，确保一次提交的正确性。很多同学思路是有的，整体上代码也没啥问题，但是不得分。就是太粗糙了，平时过度依赖 OJ 多次提交，这个习惯一定得调整。
###### 最后福利近期有道小图灵信息学教研团队正在迭代CSPIP复赛集训课程，后续将把课程链接更新到此处供大家查看，敬请期待！

有道小图灵 信息学

2019年CSP入门级第二轮认证

有道小图灵信息学