CSP-J/S初赛将于9月21日举行，同学们准备得咋样啦？

众所周知，初赛是CSP-J/S通过率最低的环节，如果初赛通过不了，那就只能无缘复赛了。

所以各位同学一定要足够重视初赛的准备与冲刺~ ~

目前正处于初赛冲刺的关键节点，特地为大家准备了一份​实用的初赛拿分实战经验帖​，大家在考前一定要仔细阅读！

关于拿分

拿分就是在代码能力不变的基础上，通过做题技巧尽量多拿分，或者说，尽量提升拿分的概率。

本来不会做时，四选一随机选的正确率是25%，有了下面这些技巧，我们就可以将正确率提升至33%，甚至是50%*。也就是说假设有100分，在相同条件下，大家都不会做，别人只能拿25分，你却能凭借这些技巧拿到33分或者50分。

对于咱们信奥选手来说，​会做的题要坚决不丢分​，不会做的题要学会尽量多拿分，这样你的竞赛之路才能一路亨通！

怎样拿分 ？

在初赛卷子上，分为 ​普通单选题和长篇代码单选题、阅读程序和完善程序题​，不同题型，考察的角度不同，所以拿分技巧也存在着一定的差异，下面我们就分这两种题型来具体看看拿分技巧的差异。

普通单选题拿分技巧

首先来看普通单选题。普通单选题就是一个题面一道题四个选项，主要是从五个方面来考察，分别是：计算机基础常识、C++语法、基本算法理论、数据结构、数学基础。 本文主要详述一下这些题适用的拿分技巧，包括：排除法、特殊值代入法、极值法等，除此之外在一些代码题中也可以用​模拟法​，模拟法会在下文详述。

i.排除法与极值法： 本题是一个抽象的规律题，理论上对于任何符合条件的数，这个规律都能成立，故而我们可以代入一些极为特殊的数，从而能直接简化整个题目的难度等级，比如代入n为1，则数组被简化为1*1的数组，只有1个元素a[0][0]。

此时，这个元素的前面没有任何元素，即，有0个元素。然后把i为0和j为0代入四个选项，能够快速得到A为-1、D为1都是不符合题意的选项，均可以快速排除。至于B和C选项，我们只需要再代入一个稍复杂的矩阵（如3*4）的就能轻松解决问题~

在上述实操中，我们使用了一个特殊极值，将题目化简为了一个极为简单的情况（从二维变成了一维），从而快速排除掉一半的选项，将随机选择的正确率从25%一下就提高到了50%，这道题的原意本来是想考察我们对二维数组存储的理解深度，但是如果你对二维数组的了解不深，通过这种极值简化和排除的办法，也能极大提高得分概率。

再如： 这道题当年很多同学不敢肯定A是对的，但是呢，由于BCD错得离谱，所以就算你再不确定A是不是对的，由于其他选项都被排除了，也就只好选A了。

i​i.​特殊值代入法： 我们可以代入一些特殊的数据，来猜测什么样的数组合并时，比较次数最多，并算出最多的比较次数。

比如，如果是a数组[1, 2, 3]和b数组[4, 5, 6]两个数组，我们发现首先1、2、3分别需要和4比较一次后放入结果数组，然后由于a数组已经没有了可比较元素了，b数组就直接按顺序放入结果数组即可，所以比较次数只需要3次，即n次即可。

这样显然太顺利了，而题目问的是至多多少次，所以我们可以构造一个运气不太好的数组，如a为[1, 3, 5]，b为[2, 4, 6]，这样1需要和2比较，然后放入结果数组，2需要和3比较、3需要和4比较等等。

以此类推，合并这两个数组需要比较5次，咱们可以随意增大数组长度找规律，可知需要比较2n – 1次。而且由于除了最后一个元素外，每个元素进数组前都要比较一次，比较得很充分，没有其他情况能比这种情况比的次数更多了，故而得到本题答案选D。这样代入具体例子肯定比同学们在理论层面推要快，要直观，更不容易错，对吧？

长篇代码客观题拿分技巧

接下来咱们再来看长篇代码题。所谓长篇代码题就是给一段代码，然后需要回答若干道与之相关的客观题，给出的代码可以是完好的（阅读程序题），也可以是残缺的（完善程序题）。对于这些题，我们能用的技巧有：模拟法、模仿相似代码法、相关变量法、经典算法实现、参考文字提示、特殊数据带入法、排除法、反例法等。

​i.模拟法：​模拟法是最为常用的技巧，用好模拟法不仅可以帮我们快速找到规律做对题，还可以进一步帮我们加深对题目代码的理解，从而做对更多的题。

方法概要： 所谓模拟法，就是利用你的脑、你的纸笔模拟程序的具体执行运算过程，不断跟踪目标变量的变化过程，从而得到答案的办法，此时，答案就是目标变量最终的变化结果。显然最好是题目让你求哪个变量，你就模拟那个变量，若它的变化过程中，依赖了若干个其他变量，则其他变量也需要一起跟踪模拟。

若变量个数过多，或程序变化过于复杂，随手写的过程中容易稍不留神就出错时，则可以考虑设计表格来展示所有数据。模拟时，遇到常见的变量名和算法结构时，可以大胆地根据变量名、算法结构猜测其作用，再根据模拟的结果小心验证，这样能够提高做对的概率，并且极大减少我们模拟时的工作量~ 常见的变量名如下： 对于常见的算法结构，大家可以重点关注一些算法的典型结构：二分、计数排序、连续字符判断（字符转数字）、链表、分治、二叉树等。此处限于篇幅就不详细列出每种结构了，请大家一定要对照代码，仔细总结。

方法举例： 下面咱们拿一道题目来演示模拟法的具体操作过程： 第一小题的输入4、3非常小，非常适合通过模拟法来得答案。除了程序输出的x、y需要模拟跟踪之外，dx、dy、cnt也都是会影响输出结果的关键变量，所以也都需要模拟跟踪。因为需要跟踪的变量较多，所以可以设计一个表格来展示，如下所示： 由此表易知，最终答案为最后一行的x、y值：1、3。

算出第一小题后，正好也可以顺便找到规律（图中的画圈处），从而解决掉第二小题。

虽然模拟法非常有用，但是比较依赖各位同学扎实的代码能力，对于非常复杂的题，代码能力弱的同学可能会模拟得非常吃力，还容易出错，​所以下述技巧其实才是咱们“骗分”的主力​！

ii.​模仿相似代码法：

• 方法概要：在我们编写程序的时候，常常会出现相似度很高的代码，它们通常是对不同的对象做相同或者相似的处理。这种现象常常出现在枚举、分治或者树结构相关的程序上。当我们需要补全语句时，参考与它相似的段落往往会给我们带来很多提示和启发。
• 方法举例：下面咱们拿一道题目来演示模仿相似代码法的具体操作过程： 通过题目可知，本题代码考察的是二叉树结构。在代码里，你能发现相似的地方不？16行和17行的代码是比较相似的吧？从17行的a[root].rch来看，我们不难猜出，这里应该是要遍历它的右子树，那么16行应该是要遍历什么呢？自然是左子树，所以标号为②这个空的答案呼之欲出：自然是a[root].lch。

通过16行可知，左子树的范围是lower_bound到cur，那么③④空右子树的范围是啥呢？肯定从cur左右开始，到upper_bound。为啥是upper_bound呢？因为一查字典就知道，lower_bound是下界（下限/最小值），所以与之对应的词，习惯上一般称为upper_bound（上界）。经过此番严谨而大胆的猜测后，下面的几题你会选了么？

当然，你要是觉得用技巧的猜测过于大胆了，不放心的话，在时间富裕的情况下，可以再用模拟法代入具体数值小心验证一下~

iii.相关变量法：

• ​方法概要：​对于大部分程序员来说，一个变量的使用场景常常是相同的，在多变量之间进行分辨的时候，如果能明确每个变量的意义，就能更快地排除错误选项，快速完成题目~

• 方法举例： 通过题目阅读，我们可知变量z表示旋转的方向，z为0表示顺时针，z为1表示逆时针，顺时针和逆时针旋转的规律显然是有很强的关系的，甚至是可以互推的。而题目已经给出了顺时针旋转规律的代码（15到19行），现在要让我们填的空③④正好是属于逆时针旋转的功能，我们就可以根据18行f数组里的行列变化规律来推空③④，如下：

  iv.经典算法实现：

• ​方法概要：​很多题目，特别是完善程序题的题目都会涉及到一个或多个具体的算法，而很多算法是有明显的经典代码特色的。因此，咱们可以利用算法本身约定俗成的写法就能快速解题！

• 方法举例： 本题的（1）、（2）空一看就是在求所有的约数，结合题目要求复杂度为O(√n)，我们根据过往求解因数个数等的模板可知，（1）空为 i * i （因为约数是成双成对的，找到√n就行了），（2）空为n / i，这是为了避免完全平方数有一个无法成对的约数情况（如，36的约数6没有与之配对的不同的约数了）。

本题的（3）、（4）空根据函数名和题目描述可知，其作用是求最大公约数的函数，结合题目要求复杂度为O(log max(a,b))，不难发现，这是考辗转相除法的递归版本，所以（3）为return a、（4）为a % b。

**注意：**本题为2018年的真题，当时完善程序题还是填空题，但是19年之后，全部改成选择题形式了，所以大家不用担心加不加空格会不会导致扣分这些细节了，只需要关注算法核心逻辑，能选出正确代码就行。

​v.​参考文字提示法：

• 方法概要：由于完善程序题的整体难度很高，阅读陌生代码对考生综合素质要求很高，而且很多题目写法不止一种。出题人为了保证考生能顺利理解代码，往往会在说明部分解释算法，或者在代码关键位置添加注释。而这些关键的文字信息，可以成为我们做出题目的重要助力。
• 方法举例：这个方法其实我们上面已经反复用到了，如：上题的题目描述及其中对算法复杂度的约束，限于篇幅，这里就不再赘述举例了。当然同学们也能发现，实际上很多题是需要综合使用多种技巧的。

​vi.​特殊数据带入法：

• 方法概要：有时候我们观察选项，会发现一些选项相似度过高，如果选择特殊数据，很多选项都会得到一样的结果，那么就能同时排除多个错误选项。对于两个高度相似的选项，也可以设计一个特殊数据，使两者结果不同，然后通过模拟找出正确的结果，就可以锁定正确答案了。
• 方法举例： 空①和空④应该填啥呢？

选项如下：

由于①处是在给res[x][y]赋值，并且是全篇唯一一处给res[x][y]赋值的代码，而最终输出的内容是由res[x][y]决定的，所以res[x][y]的值应该有0有1，0、1的分布规律应如题目举例的矩阵所示，所以本题可以快速排除B、D选项，因为这两个选项会让res数组变为全0或全1。那是A还是C呢？

我们可以简单代入一个数据进入就知道答案啦~ 假如选A，则res[x][y] = n % 2，由于这个代码是在n为0的时候才执行，所以把n为0代入可得res[x][y] = 0 % 2 => res[x][y] = 0，这样res数组的值就全为0了，与题意不符，故而根据排除法本题只能选C。（是的！你数学上的排除法在这里仍然可以有用！）

当然，如果你注意看第14到17行对参数t的变化的话，正好暗合题目0、1变化的规律，也可知①处选C。这样就是大胆猜测和小心求证对应上~ 双重保证~ double kill~

同理空④也可以用类似的办法求出，这里限于篇幅就不展开说了，这是2019年的真题，同学们可以直接拿来做。

另外，上面例题2的那道二叉查找树的题，第五空也是可以代入特殊数据的，因为如果代入root为0，会发现整个is_bst()函数一开始执行时，遇到if (root == 0)就结束了，完全无法递归起来，所以这肯定是不行的，毕竟根据题意代码涉及树的遍历，这肯定得递归起来是吧？故而A是万万不能选的。假设哪怕你完全不会这道题，那么根据这个小技巧至少能让你“猜”正确的概率直接从25%提高到了33%。

也就是说假设有100分，在相同条件下，你们都不会做，别人只能拿25分，你却能凭借这个技巧拿到33分。如果你还能进一步排除一个错误选项，则正确的概率能提升至50%，甚至像我们刚刚第一空那样，直接就做对了！整个过程只需要认真看题和使用上述的解题技巧，并没有用到多高深的知识对吧？ vii.反例法：

• ​方法概述：​此方法通常用在判断题里，根据题目给的条件，只要能举出一个反例，那么题目所描述的内容就会不成立。
• ​方法举例：​比如，题目说：数组a[i]必须全为正整数，否则程序将选入死循环。那我们就可以将0或者负整数代入a数组，看看会不会死循环，只要能找到一个反例，那么这道题的描述的情况就不成立。当然，由于只需要找到一个反例，所以我们可以代入尽可能简单的数，比如0或-1，这样就能快速算出答案~