预计难度： 签到：ABDH 简单：CE 中等：JF 困难：IG

实际难度： 签到：AB 简单：CDH 中等：EFI 困难：JG

低估了D/E/J的难度，高估了I的难度，其余题目通过情况符合预期。大概原因是D/E相对更偏思维，J看起来非常诈骗，如果做题经验不够丰富则不一定能想到dp的正解。

下面给出的难度预估，括号内的数字为考前的出题人预测难度，括号中的数字为考出来的实际难度。

A 小红的kmp

难度：100

知识点：语法

思路：签到题。需要注意应该用整行读入，c++不要直接用cin。

B 小红的大蘑菇（easy）

难度：300

知识点：模拟

思路：开一个标记数组，对于每个小蘑菇和大蘑菇将其影响的格子全部标记上，然后统计未被标记的数量即可。

C 小红的大蘑菇（hard）

难度：1000

知识点：最短路

思路：根据easy版本的思路，先标记上不能走的位置，然后跑bfs即可求出最短路。

D 小红的bfs（easy）

难度：1000（800）

知识点：分类讨论

思路：如果第一个元素和最后一个元素的最大公约数等于1，则需要1次；否则2次一定足够：可以先从到1，然后再从1到。

E 小红的bfs（hard）

难度：1400（1200）

知识点：分类讨论，数学

思路：本题最坏情况只需要走3步：当和都是素数时，若无法通过2步到达，则可以通过以下方式3步到达：从到到再到。

证明如下：只需要证3步无法到达时无解即可。首先假设和中包含合数的情况，不妨设，那么如果到可以3步到达，那么到也可以三步到达。因此我们只需要证明和均为素数的情况。

若或者，那么显然最终的答案是无解，因为此时中所有元素均与之gcd等于1，该点成为孤立点。而且时，则必有的路径。因此，最短路径长度的最大值是3。

对于路径长度等于2的情况，直接枚举中点即可。然后特判一下是否可以1步到达。

F 小红的dfs

难度：1900（1800）

知识点：并查集

思路：我们首先将所有询问离线。通过倒序处理，我们可以知道“小紫什么时候将该位置最后一棵地雷移除”，这样这道题就转变为使用并查集查询连通性的问题。

G 小红的2-sat

难度：2200

知识点：构造，数学

思路：我们可以先找到对元素，例如，时，我们找到3对这样的对子：。我们首先将其两两组合，显然有等等，以此类推。在最后还剩1对或者2对时停下来，我们最终使用或者进行最终的修正，即可完成构造。

H 小红的lca

难度：900

知识点：树

思路：显然只有菊花树不包含长度等于3的路径，因此我们只需要判断是否有2个或以上的点度数大于1即可。

当然本题也可以用树的直径来做，但码量较大，并不建议。

I 小红的期望题

难度：1800（2000）

知识点：位运算，容斥原理

思路：我们需要求出的值。这一部分直接求会比较困难，我们不妨定义，那么根据容斥，最终的答案即为。

关于的求法，我们可以分别讨论每一个二进制位的情况。那么问题就转化成了求区间中某二进制位有几个0和几个1的问题了。这部分可以用数学取模的方式轻松求出（例如，二进制百位是1，等价于模8的余数在区间内）。

J 小红的贪心

难度：2000（1600）

知识点：动态规划

思路：我们可以先预处理出每个数进行若干次操作后得到的数包含多少2的因子，那么这道题就直接转化为一个背包问题了：设代表前个数操作恰好次得到的2因子数量的最大值，我们通过枚举每个元素操作的次数即可转移到下个状态。由于每个元素的操作次数不会超过64次，因此复杂度