自选题单题解

liuzhongrui · 2025-08-18 14:24:24 · 题解

前言

前四题是梦熊模拟赛题，原题为 pdf 形式，不是很方便，作者将这四题以你谷团队题目的形式呈现，其中第二题游走作者找不到原数据了，于是用标程自己造了一份，强度不保证，希望别出锅，~~锅了 ygc 全责~~。后三题为你谷原题，同时也是作者集训题单中精选出来的三题，难度不大，~~也就蓝蓝紫~~，主要目的是借这些题讲点东西，然后，嗯，对，差不多了，就开始了。

统计(count)

传送门

考虑 x=a^b 的情况，其中 a 为质数。容易发现，如果 b \bmod p=0，y 可以取 a^{\frac{b}{p}} 和 a^{bp}，否则只能取 a^{bp}。

对于一般情况，对 x,y 做只因数分解变为 p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}。分开考虑所有只因数，条件等价于 p \times \min\{c_{x,i},c_{y,i} \}=\max\{c_{x,i},c_{y,i} \}。在一个质因数上，y 有两种取法当且仅当 c_{x,i} \bmod p=0。答案为所有质因数分开计算后的乘法。

注意特判 p=1 的情况，此时 (x,y)=[x,y]，又因为 [x,y]=\frac{x\times y}{(x,y)}，即 (x,y)^2=x \times y，当且仅当 x=y 时成立。

时间复杂度 O(\sqrt x)。

游走(walk)

传送门

首先，我们只需要考虑整个矩形的最小值 L 和最大值 R 在同一侧的情况，因为当 L 和 R 在不同侧时，答案为 R-L，而任意一条路径的答案都 \le R-L。

不失一般性的，令 L 和 R 共同位于 A 侧，则代价可以写成

所以，从 $B$ 中移除元素一定不会变的更劣，而因为 $B$ 集合必然包含左下角，所以 $B$ 集合仅包含左下角时最优。综上所述，只需考虑两种情况：$A$ 只包含右上角、$B$ 只包含左下角。两种情况取最优即可。时间复杂度 $O(n^2)$。 ## 叉欧二(xor) [传送门](https://www.luogu.com.cn/problem/T654590) 考虑一个转化，我们令 $a_0=\sum \limits_{i=1} \limits^{n} a_i$，其中 $\sum$ 表示异或。考虑操作 $i$ 在我们这个建模下会发生什么，注意到 $\sum \limits_{i=1} \limits^{n} a_i = 0$，也就是说在数学形式上，$a_0$ 和别的 $a_i$ 没有地位上的差别，于是令 $a_i=a_0$ 后自然 $a_0$ 就会变成 $a_i$，这点同样可以自行计算发现。首先对于 $a_{1\sim n}$ 中满足 $a_i=b_i$ 的位置可以直接删掉，显然这个操作是优的。于是问题变成了给定两个数组 $\{a_i \}$ 和 $\{b_i \}$，每次可以选中一个 $1\le p \le n$ 交换 $a_0$ 和 $a_p$，求最少多少步把 $\{a_i \}$ 变成 $\{b_i \}$。不妨考虑一个弱一点的问题：如果 $\{a_i \}$ 互不相同要怎么做。此时 $\{a_i \}$ 要进行的置换是固定已知的，我们考察每个置换环，一个大小为 $sz$ 的置换环通常来说需要 $sz+1$ 才能还原，特殊情况是这个置换环里面有 $0$ 的时候，我们只要 $sz-1$ 步。直接把每一个置换环的答案加起来显然是可以构造出方案的，但是这是最优的吗？我们使用势能法证明，设这个步数作为一个局面的势能，我们分讨即可发现，势能最多且可以降低 $1$，于是这个就是对的。考虑原问题。我们如果把置换提前确定下来，那就变成我们会做的问题了。我们考虑如何确定这个位移最优，$\sum sz$ 是肯定无法改变的了，我们能改变的只有置换环数量。考虑如果两个置换环里面有一个相同元素 $x$ 那么可以把这两个元素低位交换一下，这两个置换环就在没有任何实质性改变的情况下合并成了一个。于是对于一种元素 $x$ 一定全在同一个置换环中。所以我们值相同的元素看成一个数连通块就是最优的置换环数量。复杂度 $O(n)$。 ## 色(color) [传送门](https://www.luogu.com.cn/problem/T654692) 涉及到树上最远点对，我们直接把原树的直径拉出来观察一下。注意到如果直径两端同色那答案一定是直径长度。考虑异色，由于黑白地位相同，不妨钦定一端为黑，另一端为白。考察现在一个集合里面的最远点对，我们发现最远点对的一段一定是包含直径端点的。如果没有，根据点集直径具有可合并性的结论，是矛盾的。那么每一个点选择黑白信息就被压缩成了两个数 $(dis_0,dis_1)$，不妨设 $dis_0 \le dis_1$，由于是计数，考虑拆贡献，我们把 $\max$ 拆掉，考虑 $x=n- \sum \limits_{i=1} \limits^{n} [x \lt i]$，通过这个转化我们把统计 $max$ 的期望转化成统计每个变量都 $\lt a$ 的方案数的和。我们枚举一个 $a$，如有 $dis_1 \lt a$ 那么 $0,1$ 两种颜色就可以任选，如果有 $dis_0 \ge a$，那么概率为 $0$。否则这个恰有一种方法。开数组统计即可。复杂度 $O(n)$。 ## [HNOI2009] 梦幻布丁 [传送门](https://www.luogu.com.cn/problem/P3201) 观察到把 $x$ 颜色改为 $y$ 颜色实质上就是合并 $x$ 和 $y$ 的过程，所以我们采用启发式合并。 - 每个颜色维护一个数组 `G[c]`，里面存放当前所有颜色为 $c$ 的位置。 - 全局维护一个答案 $ans$ —— 当前有多少段。 - 每次要把颜色 $x$ 改为 $y$，就把所有 `G[x]` 中的下标位置颜色改为 $y$。 - 在修改颜色前，如果相邻位置原本已经是 $y$，那么这一段会被“连起来”，所以答案 `ans--`。由于每次操作可能把很多位置移动到另一个颜色，如果我们总是把“大集合”并到“小集合”，复杂度会变得很大，几乎是 $O(n^2)$。所以采用始终把较小的那个集合并到较大的集合的策略，这种策略我们叫它启发式合并，时间复杂度是 $O(n\log n)$，因为每次移动集合大小至少翻倍，所以每个位置最多被移动 $\log$ 次。时间复杂度 $O(n \log n)$。 ## P10953 逃不掉的路 [传送门](https://www.luogu.com.cn/problem/P10953) ~~这题比较板。~~ 转化一下问题，其实就是边双缩点，再利用最近公共祖先求所谓“必经之路”。 Tarjan 算法主要为记录两个数组 $dfn_i$ 和 $low_i$。 $dfn_i$ 表示将图进行 dfs 遍历的时间戳，即遍历到的顺序。 $low_i$ 表示当前点及其子树通过非父边能回到的最小的 $dfn$，简单的说就是“我能通过某些回边向上回溯到的最早祖先”。 Tarjan 算法的主要流程就是利用 dfs 的方式在标记每个遍历到的点的 $dfn_i$ 的同时，对 $low_i$ 进行赋值。对于这题这一类边双的问题，需要去判割边，$v$ 是 $u$ 在搜索树上的儿子的情况下，若 $low_v \gt dfn_u$，则判断这条边为割边。我们一般用栈去维护当前 bcc 的边，当这条边是割边，将栈中属于当前分量的边全部弹出，构成一个边双（edge-bcc），最后每个 bcc 编号作为新图中的一个节点，桥作为新图中的边。不难发现，缩点之后，这张图就变成了一棵树，此时对于图中任意两点 $a$ 和 $b$，他们之间的必经边即为两点分别处在的边双之间的距离，因为每个边双当中的边都可任意到达，因此一定不是必经边。剩下部分就是很常规的求 LCA 然后计算两点间路径长度了，倍增，树剖理论都可行。时间复杂度 $O(n \log n)$。 ## [APIO2018] 铁人两项 [传送门](https://www.luogu.com.cn/problem/P4630) 首先引入一个概念，名曰“圆方树”。构造：将一个无向连通图的所有点双拆开后，增加一个方点将其与这个点双内所有的点连边。一个结论：每一对相邻且连通的点双之间一定有公共点，这个点即是两个点双之间的割点。证明：两个相邻且联通的点双一定会有割点将其分离，而这个割点一定与两个点双共点。由上面的结论可推出(广义)圆方树的性质之一: 圆方树上的圆点和方点一定交替出现。同时一个点是割点的充要条件是：这个点在圆方树上的度数一定大于 $1$。如果想进一步了解，请自行阅读[圆方树](https://oi-wiki.org/graph/block-forest/)。言归正传，这题简化题意就是给定一张简单无向图，问有多少对三元组 $(s,c,f)$ 满足存在一条简单路径从 $s$ 出发，经过 $c$ 到达 $f$。说到简单路径，就必须提一个关于点双很好的性质：对于一个点双中的两点，它们之间简单路径的并集，恰好完全等于这个点双。即同一个点双中的两不同点 $u,v$ 之间一定存在一条简单路径经过给定的在同一个点双内的另一点 $w$。这个结论告诉我们，考虑两圆点在圆方树上的路径，与路径上经过的方点相邻的圆点的集合，就等于原图中两点简单路径上的点集。对于这道题，考虑固定 $s,f$，求合法的 $c$ 的数量，一个易证的结论，合法的 $c$ 的数量等于 $s,f$ 之间简单路径的并集的点数减去 $s,f$本身。考虑对原图建出圆方树，两点之间简单路径的点数，就和它们在圆方树上路径经过的方点和圆点的个数有关，注意，这里的方点实际上就是点双。接下来是圆方树的一个常用技巧：路径统计时，点赋上合适的权值。就本题而言，每个方点的权值为对应点双的大小，而每个圆点权值为 $-1$。这样赋权后则有两圆点间圆方树上路径点权和，恰好等于原图中简单路径并集大小减 $2$。此时，问题就转化为统计圆方树上两圆点路径权值和之和。考虑统计每一个点对答案的贡献，即权值 $\times$ 经过它的路径的条数，可以用树形 DP 求解，需要注意，可能存在图不联通的情况，需要额外处理一下。时间复杂度 $O(n+m)$。 ### 后记可能有些地方表述不当，都是自己的一些理解，可能不够严谨，轻喷。以上题目时间复杂度的分析均为粗略分析，没有那么精准，仅供参考。若对上述题目做法有不同观点，是容许的，题目做法不为一，上述题解仅提供作者的做法，同样仅供参考。顺便吐槽一下，公式好难打！！！