CSP 2022 提高组第一轮初赛讲解

CSP 2022 提高组第一轮初赛讲解，by @rgw2010

这里待补。

16：

首先阅读代码，容易发现有：

j =0;
while(j < m && s[i +j] == t[j]) j++;
if (j == m) return i;

这样的 code，就可以想到是一个字符串匹配的算法，返回值就是第一个满足区间子串等于的。

故手摸一下，可以得到第一问正确，第二问错误。

发现第三问和第六问都是询问 j++ 的执行次数，也是手动模拟计算即可，毕竟数据很小，故第三问正确，第六问的执行次数是。

现在我们来分析一下最坏时间复杂度，这是一个假的 kmp，因为 j 每次都是从开始跑。

当然也可以逆推法：这个算法的思维和代码都比 kmp 算法简单，若两者真的时间复杂度相同，为什么不普遍用这个算法而用 kmp 呢？故时间复杂度应该不是。

而代码中并没有出现有关的地方，故第四问的最坏时间复杂度只能是。

第五问应该是 a.find(b)，这是 C++ 的一个内置函数~~名称都提示的那么明显了~~。

故答案为：ABADAB。

17：

阅读代码容易发现，当时，的值为，此时就会变为计数排序，这是一个稳定的排序算法（若排序前后两个相等的数相对位置不变，则该排序算法是稳定的）。

那么第一问应该是错误的，第六问应该选计数排序。

然后来分析时间复杂度，容易发现是，有，故第三问是正确的。

对于第二问，有 cnt[val[j] / base % k]++;，即对于一个范围的位置增加，这就与有关了，故是错误的。

第四问手动自己模拟一下即可，应该是 91 37 46 98 26。

第五问注意到，故最优应该是，即普通的计数排序时间复杂度是；但是选项中没有，故应该选不确定。

故答案为：BBADDC。

18：

阅读程序，容易发现 ans[m++] = (n % (-k) + k) % k; 和 n = (ans[m - 1] - n) / k;。

那么可以得到。

则就等于一个范围的数减去再除以（即之后最大为）。

那么时间复杂度就是，故第一问是正确的。

对于第二问，去掉强制转化后输出的就是数字而不是字符，故是错误的。

对于第三问，随便找几个试一下即可，例如当时，输出是个字符而不是个，故也是错误的。

后面三个问运算量不算大，手动计算一下即可，使用排除法即可。

故答案为：ABBABB。

19：

首先我们要弄懂算法在干什么，容易发现是二分。

即肯定在的或的之间。

令。

那么若，则需要增大或的范围，故第一问填 m1 + m2，然后分类讨论一下：

若，则都是的，故不可能是第小；则令。
否则若，同理令。

若，则需要减少的贡献，和上面道理是一样的，就不多说了。

故第二问应该填 a1[m1] <= a2[m2]。

然后后面的程序是一个分类讨论，我们注意到有 while (left1 <= right1 && left2 <= right2)，故肯定是至少有一个条件没有满足。

则分类讨论应该是看是还是：

若，故只能取的：
- 则若：那么就只能取了；
- 否则的话。
若也是差不多的，这里不多说。

故第三问填 left1 > right1，第四问填 y = a2[k - left1 - 1]，第五问填 y = a1[k - left2 - 1]。

故答案为：CBCCA。

20：

这题比 19 题都简单qwq。

容易发现题目使用记忆化搜索的形式进行 dp 的，同时还有回溯。

看 code：

f[x][y] = min(f[x][y], dfs(a, y) + 1);
f[x][y] = min(f[x][y], dfs(x, b) + 1);
f[x][y] = min(f[x][y], dfs(0, y) + 1);
f[x][y] = min(f[x][y], dfs(x, 0) + 1);

分别是：

将第一个桶倒满。
将第二个桶倒满。
将第一个桶倒空。
将第二个桶倒空。

那么还有两种情况：

将第一个桶中的水倒入第二个桶。
将第二个桶中的水倒入第个个桶。

代码中第一个，即倒入第一个桶的水量，则此时状态会由原来的更新为，故第一问填 dfs(x + t, y - t) + 1。

后面情况基本一致，故第二问填 dfs(x - t, y + t) + 1。

然后看回溯过程，首先有一个终止条件，显然只有当两个桶中任意一个桶有升水时就达到了要求，故第三问填 x == c || y == c。

然后后面的第四/五问和第一/二问是本质相同的。

故答案为：ACAAC。