CSP应试策略.md

CSP考试策略

零、总纲：

明确题型，合理安排

考试时长：4个小时

• 有人说：csp上拿一个将近400分甚至高于400分的分数或者pat上拿一个90+的分数，是不需要什么编程天赋的，任何一个普通人只要付出足够的努力都是可以做到的。它和数学差不多，都需要大量重复的不厌其烦的练习练习再练习，没有什么捷径，只要肯付出沉下心来去做，一两个月的时间我觉得是足够让一个在数据结构和算法上基础一般的人脱胎换骨的

一、简单题（第1-2题）

1、能用“暴力”，不用打表

2、能用“打表“，不用数据结构

3、能用栈和队列，不用更复杂数据结构

• 第1和2题，不要想得太复杂，一般难题会用较小的数据范围减低难度，可以用暴力
• 第1和2题，主要自己要控制好“边界数据”的拿捏，能拿到分的，绝对不能丢分！！！

二、CCF：第3题

CCF：第4题套路

• 4.题图论。

思路：

（1）审题，理清题意，选好存储结构，一般图论题用多维vector数组配合结构体存储。

（2）想清楚题目的考点，一般的考点有：

最小生成树、迪杰斯特拉算符，并查集，DFS，BFS暴力搜图等。理清考点后，才比较容易下手。

（3）注意多维数组的使用，一维不行用二维，二维不行用三维，特别是涉及到的元素比较多的时候，思路应该多往这边靠。

知识点讲解

最小生产树：
最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。
在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得
的 w(T) 最小，则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称。
Kruskal算法简述
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。 [1]
Prime算法简介：
最小生成树和最短路径一样，都是在实际中非常常见的图算法问题。
同样也有专门的算法来构造图的最小生成树。
Prime算法是求解最小生成树问题最常用的算法，思想和上次讲解的 最短路径Dijkstra算法 有些接近。
1 把所有节点分成两类，一类是已经加入到了 当前的生成树中（集合 Y） ，一类是还没有加入当前的生成树中（集合N）。
PS: 显然，这种分类可以用flag来设置。
2 最终的生成树是一步一步构造的，所以说是 “当前的”生成树。
从 Y 中取得一个节点 Vy, 从 N 中取得一个节点 Vn. 使其满足 Vy和Vn之间边的权值最小。
3、 找到满足上述条件的节点后，把Vn结点从 N 移入 Y中。
Ps： 具体代码实现是，flag值修改即可。 （最原始的做法，后续会有改进方式）
重复上述 2. 3. 两步，直到所有节点全部加入Y中。

三、应试经验

• 1、第1和2题**（尽量40min-60min完成），是属于简单模拟和程序设计基本能力的考察，这块分数一定**要拿满！

  • 注意，控制前2道题的原因是：后面3个题目会比这2题难得多！

• 2、第3题：大模拟题型**（时间上分配2小时左右）**，不需要多少算法知识，但是代码的实现细节会比价繁琐，这也是想要拿高分的一个难点！

  • 如果你是希望得到300分的程度，这题请不要放弃

• 如果你希望得到400分的程度，那么第3题的100分也是必须要全部拿下的！

  • Tips：代码实现细节只能靠练习，这个速成不了。可以在考前这几天去官网的题库上加强一下第3题这个题型的练习！
  • 一般掌握，STL中的string会让你更加有底气，可以在CF上看别人代码，用STL的很多

• 3、第4题：一般来说是比较正常难度的算法题，考察点基本是搜索/图论的相关基本算法！

  • 但是一般不会是直接的所谓“套个板子”就能得分的题目，需要结合题目要求做优化和调整。
  • 方法：现会员

• 4、第5题：属于高难度的题目，一般来说拿到20%-30%的分数就很满意了，不用花费太多的时间在这。

  • 如果自身能力是无法AC掉第4题的，建议先去把第5题的简单数据（10%或者20%的数据）过掉，然后去检查前3题。

• 一般的：不用过分相信在考场上学会以前没熟悉过的算法，当然还是可能的。

四、CSP的趋势

2019年，一个17级的同学说的：

• 最近几年CSP认证（甚至包括CCF办的其他赛事）有个趋势：
  • 1、就是把问题分成几个子任务，子任务会比原问题简单，每个子任务占一定的分数。
  • 2、子任务大部分情况具有限制数据范围，弱化条件！以及容易构造特定解法的特征。
  • 3、由上面特征：可以抓住比较容易实现的几个子任务去实现一个“不完全”的代码，这样就能拿下这部分潜在的分数（骗分技巧！）