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

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

这里待补。

首先题目意思是求出：

unsigned short f(unsigned short x) {
    x ^= x << 6;
    x ^= x >> 8;
    return x;
}

注意有 unsigned short，那么都需要对取模，那么第二问肯定是错误的。

对于第一问，手推一下方程即可，发现应该是无解的，故正确。

对于第三问、第四问、第五问、第六问，手动模拟即可。

故答案为：ABABBD。

对于第一问，因为有，故删掉后不一定一致的，故错误。

手摸一下小数据，发现 solve1 和 solve2 的值都是一样的，那么直接大胆猜测是相同的；于是第二问错误，第三问正确。

第四问是求 solve1 的时间复杂度，发现有和这种的嵌套循环，于是应该是。

第五问很明显，只有一重循环，于是是。

题目求的是：

第六问 时很容易计算，答案是。

故答案为：BBADBB。

通过瞪眼法逆推我们可以得到题目：

第一问显然是正确的。

第二问可以推出，所以也是正确。

第三问手算一下即可，也是正确的。

第四问这里有点小坑，首先排序是，然后二分是，总的话就是。

第五问将区间的限制改为，这样同样的下，区间数量肯定是少于之前的，则满足就更难了，于是肯定要比之前大或相等。

第六问也是手算一下即可。

故答案为：AAACBB。

首先通过提示可以得到程序是先求出以每个点开始的路径数量，即。

那么状态转移方程显然是：

注意因为是DAG，要按照拓扑排序的方式转移。

故第二问应该是 deg[v] == 1，第三问是 std::min(f[u] + f[v], LIM)。

首先要确定起点，若以为起点，则需要满足：

就是 next 函数的部分，则第一问应该填 k <= f[u]。

第四问应该是 k>1，即当时应该停止，因为当前我们求出的路径是之前我们减掉的路径的字典序第小的路径，是符合的。

因为每次找下一个点时当前路径也需要舍去，则第五问是 --k。

故答案为：BAADC。

对于第一问，要注意 std::vector<int> pre(a + mid, a + r);，即将赋值为中内的值；且 pre 这个名字已经提醒了是前缀了，于是应该填 pre[i] = std::max(pre[i], pre[i - 1])。

第二问这里有一个坑，它的 max = std::max(max, a[i]); 是在 while (j < r && ②) ++j; 后面的。

不然如果放在前面的话应该是可以选 pre[j - mid] < max 的，即找到第一个，满足的最大值。

那我们现在看一下在没有先取的情况应该填什么能达到上面相同的目的，容易发现是 a[j] < a[i]。

这样在每次走指针前是肯定大于等于范围内的值的，即 code 里的 max。

那么显然只有当是大于 max 时才可以使得继续向右移，找到第一个大于等于的；否则不变；那么这样也是达到相同目的的。

那么此时考虑计算左端点为的贡献，有两种：

观察代码可以发现 solve(l,r) 计算的是的贡献，故第五问填 solve(0，n)。

故答案为：DBACA。