初赛速通指南 | Sevenki's Blog

写一篇《初赛速通指南》，希望对后人有用。

如果能灵活运用本文，您应该可以通过 CSP-S 初赛。

总体分析

前十五题一般是概念大作战。
阅读理解考察细节理解以及猜测能力。
完形填空考察【适应原文逻辑】的能力。

其中一般情况下前十五题和完形填空相对阅读理解比较容易，因此常被视为【下限】分数。稳拿大部分这些分是过初赛的关键。

普通选择题

其中，前十五题对于了解概念较多，训练有素的选手基本是可做的，也是整张试卷最可做的部分之一。

综合往年初赛，这里给出若干重点知识点：

Linux 指令
哈夫曼树
哈希
位运算、逻辑运算
基础算法理论与复杂度分析
语法与 C++ 代码分析
组合数学
二叉树
各种图论概念

初赛中的概率问题一般都可以转成计数问题。

还有一些计算机相关常识，不过近两年考得似乎比较少？初中信息技术课普及的那些应该够用。

阅读理解

这部分作为一张初赛试卷的难度中心，决定了你的分数的上限。

当你其它两部分考得并不是很好时，这一部分充当【容错】。

阅读理解一般会出一道简单题，一道中等题，一道困难题。根据往年经验，这三道题的难度并不排序。因此需要自行斟探难度。

简单题一般是简单算法如素数筛、位运算等。这道题理论上是可以获得所有分数的。尽量打满。

中等题一般是更高级一点的算法。但是一般也能看得懂。尽量先理解。

困难题一般是难以理解其逻辑的目的的题目（如某种动态规划）。

在每道题后面一般都会跟一两道给定输入求输出的题目。一般可以模拟直接模拟，然后就是找程序的本质。如果你不能得出程序的本质（也就是找不到规律），这时候如果模拟的工作量较大，就要考虑把这道题弃掉。

对于“越界问题”，直接带进去仔细观察即可。“修改代码”问题也是差不多的。

有的时候会给你两个函数，这两个函数有可能在某个细节方面有差别，也有可能看起来完全不一样实则本质相同，要注意分析。

完形填空

这一部分的难度普遍低于阅读理解。最难的也就是现场发明四毛子算法了，我觉得这个可能还没有阅读最难的题难。因此这也是下限分数的一部分。

做完形填空要观察上下文，适应原文的代码风格。（比如 0-index 还是 1-index）

然后完形填空可能会出现一些你没看过或者不熟悉的写法，这时候你要先尝试理解。

对于一个选项如果你不理解，可以尝试代入数据模拟一下。

当然，完形填空大部分都是考经典算法或者简单问题，这就要求你熟练掌握经典算法了，对简单问题也应该有独立解决的能力，这方面能力比较偏复赛一点。

考场策略

整体按照前十五题->完形填空->阅读理解的顺序去写。

前十五题如果遇到比较麻烦并且自己不太会的计数问题，抑或是不知道的概念，先跳过。
当然初赛计数题大部分都是可做的。还是要试一下，但是不能卡太久。
前十五题里面肯定有一些题是纯模拟，这个就没办法了，只能硬模拟了。

然后写完形填空。为什么不先写阅读理解？阅读理解拿分少、效率低、性价比极低，还会压缩完形填空的时间。

完形填空大部分分都是可拿的，所以一定要认真做。仔细推敲上下文。

然后阅读理解的话，这个就看个人了。一般建议是直接跳过复杂输入数据模拟题，然后优先保简单题中等题的分数，最后再去分析难题。

如果你有检查的习惯的话，可能得牺牲一点思考困难题的时间，不过问题不大。

接下来分析一下分数：

前十五题和完形填空总分一共六十分，如果这六十分能稳拿的话，阅读理解甚至都不用怎么写。

我们假设您拿了 40 分。那么按照去年的分数线，您只需要在阅读理解拿不超过 10 分。

当然是玩笑话，要求稳的话，我们阅读理解得拿一半分。

所以综上所述，如果完形填空和选择都做得很不错，那么后面阅读理解的压力就少很多，不用担心阅读理解难。如果阅读理解真的难了的话，还能卡掉一些做题顺序不当的选手。

各种题型

这里挑几种题来分析一下。

神秘位运算

1
2
3

int logic(int x, int y) {
    return (x & y) ^ ((x ^ y) | (~x & y));
}

直接打出一个真值表（即 $(x, y) \in {(0, 0), (1, 0), (1, 1), (0, 1)}$ 时的情况），然后由于只有基本位运算，没有左右移，每一位独立，所以根据真值表你就可以瞪出它的规律了。

复杂度理论

这个，首先你需要掌握各种算法的复杂度情况，还要熟悉各种写法的复杂度，最后就要分析程序。

主定理是对递归函数复杂度的分析好工具，一定要掌握。

当然也有一种逃课方式，并且更无脑，不用记忆，适用范围更广，强烈建议学一下：主定理狗都不学。

下面列举几种常见的东西：

没有记忆化的直接递归斐波那契： $O ({Fib}_{n})$ 。也可以写成一个指数函数。
调和级数枚举： $O (n \log n)$ 。
埃氏筛： $O (n \log \log n)$ 。
$1 \sim n$ 所有数的因数个数： $O (n \log n)$ 。
某个数的因子个数： $O (\sqrt{n})$ 。
哈希表的最坏复杂度： $O (n)$ 。
对于一个长度为 $n$ 的序列，设 $c_{k}$ 为 $k$ 在序列中的出现次数，那么 $c_{k}$ 只有 $O (\sqrt{n})$ 种本质不同的值。
快速排序单侧递归，定位 kth： $O (n)$ 。
对于像线段树一样的分治结构，要看每个分治区间的复杂度是不是只和区间长度有关。
- 以下均假设维护复杂度为 $O (1)$ ，也就是不用其他的非常数算法、数据结构辅助维护。
- 如果只和区间长度有关，那么总复杂度 $O (n \log n)$ 。
- 如果和值域有关，那么复杂度 $O (n a)$ 。如果和总长度有关，那就是 $O (n^{2})$ 。

暂时只能想出来这么多。最主要还是要见多识广吧。

就写到这里，有人想看再补充。