洛谷普及组模拟赛 题解报告
\[\bf{Prepared\ by \ InoueTakina.} \]前言：
- 祝大家身体健康。
- 本场比赛较为良心，经过了多次难度平衡，应该严格低于 NOIP 2018 提高组，相信大家都能享受到良好的做题体验。
- 对于题目的评分分为 stupid / easy / medium / hard，这个评分体系和洛谷没有任何关系，且
不完全基本不按难度评分，更多的结合了有趣程度，并忽略了代码和模板的难度。大概是存在可以量化的标准的。 - 本套题的题目算法分布应该比较均匀，涉及了模拟，简单数论，小学数学，图论，枚举，二分等算法。
A. 小狗哥哥
命题思路：
- 审题人说要有一个签到题。
- 最开始准备的签到涉及了位运算，被毙掉了。
- 考虑不要太毒瘤，决定出一个模拟题。
- idea 来源 hollow knight，非常优秀的游戏。
- 每次强化完骨钉原来三刀的小怪还是三刀。
- 本来放这个题想让大家都开心开心，但是看结果好像大家都不开心。
- 应该是给足了部分分，大样例的强度也不会很低。
- 模拟 / stupid-。
题解报告：
算法 0
-
我不会这题！
-
期望得分 \(0\) 分。
算法 0.5
-
我不会这题！但我会观察！
-
注意到随机数据下给出的数据大概率不合法！
-
输出 \(0\)，期望得分 \(45\) 分。
-
时间复杂度 \(\mathcal{O}(1)\)。
算法 1
- 我会枚举！
- 枚举 \(p\)，并代回矩阵模拟，统计合法 \(p\) 的个数。
- 注意到 \(p\) 的大小不超过 \(\max\{a_i\}\)。
- 综合时间复杂度 \(\mathcal{O}(\max\{a_i\}\times n\times k)\)。
- 期望得分 \(70\) 分，结合之前的部分分期望得分 \(60\) 分。
算法 2
- 我会观察性质！
- 不难发现并证明，合法的 \(p\) 的取值是一个区间。
- 因此我们由序列逆推得出合法的区间。
- 首先由不等式 \((a_i-1)\times i\times p < m\le a_i\times i\times p\) 可以得出 \(p\) 的一个取值范围。
- 注意到这里有个 corner case，要解 \(p\) 肯定要移向，\(a_i=1\) 要略过，还有就是上取整和下取整要弄清楚，以及有一段点是 \(<\) 而不是 \(\leq\)，出题人为此拍了 \(3000\) 组数据，应该卡全了。
- 然后取 \(n\) 个区间的交即可。
- 综合时间复杂度 \(\mathcal{O}(n)\)。
- 期望得分 \(100\) 分。
B.简易钨丝
题解报告
算法 1
- 我会枚举全排列！但是出题人似乎没有给我 \(n\leq 10\)。
- 我会观察性质！注意到相同的数一定放在一起，所以相同的数可以看作一个，因此我们只关心某个数有或者没有，然后就可以愉快的枚举啦！
- 综合时间复杂度 \(\mathcal{O}(q\times w!)\)。期望得分 \(40\)。
算法 2
- 我会猜结论！所有数升序排列时答案最小，这个结论不难证明是正确的。
- 整理一下柿子，发现答案是 \(2\times (\max-\min)\)。
- 维护 \(\max,\min\)，可以用
std::set实现。 - 综合时间复杂度 \(\mathcal{O}((n+q)\log n)\)，期望得分 \(100\) 分。
C. 不见故人
命题思路：
- 本题整体解法应该比较自然。
- 命题人先想题再想做法的。
- 然后本来也想让大家乐呵乐呵，但是好像大家还是没乐呵起来。
- 简单数论 / 动态规划 / 最优化 / easy。
题解报告：
算法 1
- 注意到当所有数都相等的时候，我们不需要操作。
- 期望得分 \(10\) 分。
算法 2
- 我会搜索！
- \(n\leq 4\) 应该随便搜索都能过去（心虚。
- 结合算法 1 期望得分 \(15\) 分。
算法 3
-
我会观察性质！注意到最后的答案一定是全局 \(\gcd\)。证明平凡，略。
-
观察性质：每个数最多被一次操作覆盖。
-
证明同样平凡，分几种 corner case 证明重复操作可以合并就好了。
-
然后设计 \(\rm dp\)，记 \(f_i\) 表示把 \(1\sim i\) 都变成相同的数的最小代价。记全局 \(\gcd\) 为 \(G\)。
-
有转移 \(f_i=\min\{f_{j-1}+i-j+1+k+[\gcd(a_j,a_{j+1},\dots,a_i)\neq G]\}\)。
-
直接转移是 \(\mathcal{O}(n^3)\) 的，期望得分 \(45\) 分。
算法 4
- 我会优化上面的 \(\rm dp\)！
- 我们考虑动态维护 \(\gcd(a_j,a_{j+1},\dots,a_i)\)。
当然了，强上数据结构也可以。- 综合时间复杂度 \(\mathcal{O}(n^2\log n)\) 的，期望得分 \(65\) 分。
算法 5
- 我们把原序列满足 \(a_i=G\) 的位置染红，其他染黑，则原序列形成若干黑色段。
- 记 \(L_i,R_i\) 表示从左到右第 \(i\) 黑色段的左右端点位置。
- 我会继续观察性质！注意到只有每段的右端点为有效转移点。因此我们改记 \(f_i\) 表示把 \(1\sim R_i\) 都变成相同的数的最小代价。
- 考虑分情况转移！如果从本段转移过来，则有 \(f_i=f_{i-1}+R_i-L_i+1+k+[\gcd(a_{L_i},a_{L_i+1},\dots,a_{R_i})\neq G]\)。
- 否则转移时选择的区间一定包含红色位置，那么可以直接把选择的区间变成 \(G\)。
- 则有 \(f_i=\min\limits_{j<i-1}\{f_{j} + R_i-L_{j+1}+1+k\}\)。
- 考虑第二种转移如何快速实现，不难发现，动态维护 \(f_j-L_{j+1}\) 的最小值即可。
- 每次转移时上述两种情况取 \(\min\) 即可。
D. Goodbye 2022
解题报告
算法 1
- 检验读题成果，暴力枚举计算即可。
- 时间复杂度 \(\mathcal{O}(n^p)\)。
算法 2
- 当 \(p = 3\) 时，不难想到我们可以先对每一个 \(i\) 预处理出所有满足条件的 \(j\) 的个数，记为 \(f_i\)。然后对于那个三元组，枚举中间的那个数，不难发现每一个 \(i\) 做为中间的那个数的贡献为 \(f_i * (f_i - 1)\)，且没有重复的情况，所以最终答案即为 \(\sum^n_{i=1}{f_i * (f_i - 1)}\)。
- 时间复杂度 \(\mathcal{O}(n ^2)\)。
算法 3
- 受算法 \(2\) 启发，当 \(p=4\) 时，我们也可以枚举 \(2, 3\) 位置上的数，同时通过 \(f\) 数组计算答案。
- 但由于题目要求 \(p\) 元组的元素互异，所以 \(1\) 位置与 \(4\) 位置相同的情况会被多算一次。
- 记 \(a, b, c\) 分别为 \(2, 3, (1/4)\) 位置上的数，如果我们将 \(i\) 向所有满足 \(\operatorname{popcount}(i \oplus j) = k\) 的 \(j\) 连边，多算的情况的个数其实就是这个有向图上三元环的个数。
- 由于 \(n\) 只有 \(1000\)，不难想到直接用
bitset优化暴力枚举的过程，枚举 \(1, 3\) 两个点，然后通过bitset进行与操作得出 \(2\) 点的个数，即可计算出三元环的个数。 - 时间复杂度 \(\mathcal{O}(\dfrac{n^3}{\omega})\)。
算法 4
- 受到算法 \(2,3\) 的启发，当 \(p=5\) 时，我们可以故技重施，枚举 \(2,4\) 两个位置的值，然后通过
bitset优化可以轻松求出位置 \(3\) 满足的数的个数，同时 \(1,5\) 位置的答案我们也可以通过容斥算出。 - 考虑一下哪几种情况我们需要容斥，记我们枚举的 \(2,4\) 位置的数分别为 \(a,b\)，中间位置满足的数的个数为 \(mid\)。
- \(1,3,5\) 位置均无限制，这种情况的个数为 \(f_{a} \times f_b \times mid\)。
- \(1, 3\) 位置相等，\(5\) 位置无限制，这种情况个数是 \(mid \times f_b\)。
- \(3,5\) 位置相等，\(1\) 位置无限制，这种情况的个数是 \(mid \times f_a\)。
- \(1,5\) 位置相等，\(3\) 位置无限制，这种情况的个数是 \(mid \times mid\)。
- \(1,3,5\) 位置相等，这种情况的个数是 \(mid\)。
-
不难发现情况 \(2,3,4\) 其实是包含情况 \(5\) 的，由于情况 \(5\) 应该只能被算一次，所以我们只要将情况 \(1\) 的个数减去情况 \(2,3,4\) 的个数再加上两倍情况 \(5\) 的个数就是 \(p=5\) 时的答案了。
-
时间复杂度 \(\mathcal{O}(\dfrac{n^3}{\omega })\)。
-
综合算法 \(1,2,3,4\) 即可获得本题的全部分数。
全文转载！！！
标签：普及,洛谷,题解,复杂度,个数,枚举,times,算法,mathcal From： https://www.cnblogs.com/messiljk/p/17058595.html