二级结论

• 本文主要内容为CSP-J二级考点的总结，包括数学类、数论类、基础算法技巧类等。不属于考试大纲所概括的内容，但是在考试中存在较大可能考到。 数学类：

贡献类问题：

求若干个区间之间的求和\一个数学式中含有若干次加法乘法运算等问题时。如果需要优化时间复杂度，一般是利用数学知识求解每个点参与了多少次运算。对应题目：琉克与学生 卡牌游戏

值域问题：常考如下两种问题

• 1.值域大，数据量小，即离散型数据，一般考虑数据的离散化。
• 2.值域小，数据量大，即稠密型数据，往往需要标记出每个数字出现了多少次，将计算时间复杂度降低。对应题目：拯救银河 因式分解问题，一般涉及到乘法的，一眼数学的题目都会用到因式分解，常考点公式如下：

常见的优化技巧有：

• 1.剪枝：在搜索中，根据题目条件，及时排除一些不必要的搜索路径，减少搜索量。
• 2.记忆化搜索：在动态规划中，将已经计算过的状态保存下来，避免重复计算。
• 3.贪心：根据题目条件，每次选择最优的策略，最终得到最优解。
• 平面图/图论进行深搜/广搜 常见的是考深搜和广搜，深搜一般用于求路径，广搜一般用于求最短路径。 考法一般比较多变，大概率会选择以下变形： 求满足一定规律的最短路径：先从终点开始搜索，求终点到每个点的最短路径，最后从起点开始搜索，每次选择离终点距离比自己少1步的点移动，此时走题目安排的优先级最高的路。对应题目：鲁星救援 求走一个方向必须撞墙才能停下的路径：先从起点开始搜索，每一步离自己最近的一个方向移动，直到撞到墙为止。对应题目：冰上滑行 图论考点核心：一般考图论的深搜广搜，需要注意的是，深搜一般用于求路径，广搜一般用于求最短路径。