YL 24-CSPS 模拟赛有哪些亮点和不足？

说明 原文是写在 notion.so 的，现在 notion 和洛谷和 cnblogs 三向更新。为什么呢？也说不上来。 好吧，该说一下阅读指南了。里面都是我模拟赛的一些总结，主要总结自己，没有想写题解一样的描述，最多写一点解法。前面的 2024xxxx 是日期，后面的 YLOI-R? 是第几场。祝阅读愉快。 以下是 notion.so 上的原说明： 此系列比赛由鸭梨官方举办，最终解释权为鸭梨恶臭公司。 说明：题目大部分为牛客 OI 赛前训练营的题。 20240923 YLOI-R1 依依寺（yiyi） 期望得分：\([40, 50]\)，实际得分：\(0\)。 博弈论，个人觉得比较难，评个黄~绿。 一开始题目直接读错，以为是一个人可以取多个数，多个数的总和 \(\bmod\ 3\) 要 \(\neq 0\)，然后写了两个 If ，然后就是大小样例双双寄掉。 后来，终于读对了，但是情况太多了，然后就漏了一些情况，还是没有分。在比赛中，我就往 \(\bmod\ 3\) 的方面去想，然后就没想成。然后，我就在想：要不要用大样例找规律？最后，确实是找出来一些不知道是真是假的规律。但是，还是不对。 正确的背包与我的背包只相差两步之遥，虽然这道题的暴力已经拿到，但对于 dp 的掌握及粗心的改正还有待加强。 武义寺（wuyi） 期望得分：\(30\)，实际得分：\(30\)。 这种推式子数学题我接触较少。 一开始，我看到期望。吼，还好，我还学过一点点。答案不就是 \(\cfrac{\sum \text{val}(p)}{n!}\) 吗，那么 \(n!\) 能 \(O(n)\) 解决。但是 \(\sum \text{val}(p)\) 需要找规律，如果暴力的话时间复杂度是 \(O(n!)\) 的。然后打出了 \(n\) 为 \(1\) 至 \(6\) 的 \(\sum \text{val}(p)\)。但是还是没有找到规律。 正解是让人呕吐的推式子： 暴力可行方案为 \(k((k + 1)^{n - k} - k^{n - k})\)。 那么 \(\sum \text{val}(p)\) 为： \(\sum_{k = 1}^n (n - k + 1) \cdot k((k + 1)^{n - k} - k^{n - k}) \cdot (k - 1)!\) \(=\sum_{k = 1}^n (n - k + 1) \cdot (k + 1)^{n - k} - k^{n - k}) \cdot k!\) 像这种组合排列的题，我大抵都接触的较少了。所以，我略需强化我的数学 whk 实力。 依久依久（yijiu） 期望得分：\(10\)，实际得分：\(10\)。 送出题人两个字：恶心。 第一眼看到题目，感觉眼花缭乱，所以就跳过了。后来，才读懂题意。赛事想打个暴力，把一个数从 \(f_{86}\) 开始分解，也就是从 \(\ge 10^{18}\) 的最小斐波那契数开始分解。然后最后异或起来即可。然后，便开始想优化了。一开始想的是用 upper_bound 来缩小范围。可是，这没什么用。 这道题的考点是递归+前缀和，我们可以处理前缀异或和 \(S(n) = \bigoplus_{i = 1}^n \text{val}(i)\)，询问时计算 \(S(r) \oplus S(l)\) 即可。像这种题我已接触较多了，可我的脑子里这种思维含量较少。我需要较多的做这种题，多加训练。 补幺梨（pear） 期望得分：\([40, 50]\)，实际得分：\(45\)。 dp 转换图论，难。 看到这么板的题目，感觉很简单。然后，就是一眼丁真数据范围，寄掉。如果是 dp 的话，很简单，直接转移 \(f_j = f_j | f_{j - a_i}\) 然后去最大值即可，便打了 dp。然后看着数据范围的突破点，\(m\) 比较大，但又不是很大。想了很久还是没想出来，然后暴力大草 \(45\) 分。 真的没有想到正解是 \(\texttt{Dijkstra}\)，要把本来的 dp 思维转化为图论思维，离大谱。对于思维转化，还是比较弱的。 20240924 YLOI-R2 集合（set） 期望得分：\([70, 80]\)，实际得分：\(60\)。原因：打表没打全。 考试时在想，居然 \(1 \le n \le 200\)，那么就是 \(O(n^3)\)，可不可以把每一次相乘的数拆成 \(3\) 个数相加呢？然后，就是没有做出来。然后，又有一个思路，统计每个数字出现了多少遍，结尾全乘起来。所以，就写了一个 dp 来统计。可是，dp 写挂了。出现了两个小错误，赛后才发现。