专栏文章

自选题单题解

lliuzhongrui
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio9o5i5
此快照首次捕获于
2025/12/02 15:38
3 个月前
此快照最后确认于
2025/12/02 15:38
3 个月前
查看原文

前言

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

统计(count)

传送门
考虑 x=abx=a^b 的情况，其中 aa 为质数。容易发现，如果 b mod p=0b \bmod p=0，yy 可以取 abpa^{\frac{b}{p}} 和 abpa^{bp}，否则只能取 abpa^{bp}。
对于一般情况，对 x,yx,y 做只因数分解变为 p1c1p2c2…pkckp_1^{c_1}p_2^{c_2}\dots p_k^{c_k}。分开考虑所有只因数，条件等价于 p×min⁡{cx,i,cy,i}=max⁡{cx,i,cy,i}p \times \min\{c_{x,i},c_{y,i} \}=\max\{c_{x,i},c_{y,i} \}。在一个质因数上，yy 有两种取法当且仅当 cx,i mod p=0c_{x,i} \bmod p=0。答案为所有质因数分开计算后的乘法。
注意特判 p=1p=1 的情况，此时 (x,y)=[x,y](x,y)=[x,y]，又因为 [x,y]=x×y(x,y)[x,y]=\frac{x\times y}{(x,y)}，即 (x,y)2=x×y(x,y)^2=x \times y，当且仅当 x=yx=y 时成立。
时间复杂度 O(x)O(\sqrt x)。

游走(walk)

传送门
首先，我们只需要考虑整个矩形的最小值 LL 和最大值 RR 在同一侧的情况，因为当 LL 和 RR 在不同侧时，答案为 R−LR-L，而任意一条路径的答案都 ≤R−L\le R-L。
不失一般性的，令 LL 和 RR 共同位于 AA 侧，则代价可以写成 max⁡x∈Bmax⁡y∈A∣x−y∣=max⁡y∈Bmax⁡{∣y−L∣,∣y−R∣}\max \limits_{x\isin B} \max \limits_{y\isin A} |x-y|=\max \limits_{y\isin B} \max \{|y-L|,|y-R| \}。
所以，从 BB 中移除元素一定不会变的更劣，而因为 BB 集合必然包含左下角，所以 BB 集合仅包含左下角时最优。
综上所述，只需考虑两种情况：AA 只包含右上角、BB 只包含左下角。两种情况取最优即可。
时间复杂度 O(n2)O(n^2)。

叉欧二(xor)

传送门
考虑一个转化，我们令 a0=∑i=1naia_0=\sum \limits_{i=1} \limits^{n} a_i，其中 ∑\sum 表示异或。考虑操作 ii 在我们这个建模下会发生什么，注意到 ∑i=1nai=0\sum \limits_{i=1} \limits^{n} a_i = 0，也就是说在数学形式上，a0a_0 和别的 aia_i 没有地位上的差别，于是令 ai=a0a_i=a_0 后自然 a0a_0 就会变成 aia_i，这点同样可以自行计算发现。
首先对于 a1∼na_{1\sim n} 中满足 ai=bia_i=b_i 的位置可以直接删掉，显然这个操作是优的。
于是问题变成了给定两个数组 {ai}\{a_i \} 和 {bi}\{b_i \}，每次可以选中一个 1≤p≤n1\le p \le n 交换 a0a_0 和 apa_p，求最少多少步把 {ai}\{a_i \} 变成 {bi}\{b_i \}。
不妨考虑一个弱一点的问题：如果 {ai}\{a_i \} 互不相同要怎么做。此时 {ai}\{a_i \} 要进行的置换是固定已知的，我们考察每个置换环，一个大小为 szsz 的置换环通常来说需要 sz+1sz+1 才能还原，特殊情况是这个置换环里面有 00 的时候，我们只要 sz−1sz-1 步。直接把每一个置换环的答案加起来显然是可以构造出方案的，但是这是最优的吗？我们使用势能法证明，设这个步数作为一个局面的势能，我们分讨即可发现，势能最多且可以降低 11，于是这个就是对的。
考虑原问题。我们如果把置换提前确定下来，那就变成我们会做的问题了。我们考虑如何确定这个位移 最优，∑sz\sum sz 是肯定无法改变的了，我们能改变的只有置换环数量。考虑如果两个置换环里面有一个相同元素 xx 那么可以把这两个元素低位交换一下，这两个置换环就在没有任何实质性改变的情况下合并成了一个。于是对于一种元素 xx 一定全在同一个置换环中。所以我们值相同的元素看成一个数连通块就是最优的置换环数量。
复杂度 O(n)O(n)。

色(color)

传送门
涉及到树上最远点对，我们直接把原树的直径拉出来观察一下。
注意到如果直径两端同色那答案一定是直径长度。考虑异色，由于黑白地位相同，不妨钦定一端为黑，另一端为白。考察现在一个集合里面的最远点对，我们发现最远点对的一段一定是包含直径端点的。如果没有，根据点集直径具有可合并性的结论，是矛盾的。
那么每一个点选择黑白信息就被压缩成了两个数 (dis0,dis1)(dis_0,dis_1)，不妨设 dis0≤dis1dis_0 \le dis_1，由于是计数，考虑拆贡献，我们把 max⁡\max 拆掉，考虑 x=n−∑i=1n[x<i]x=n- \sum \limits_{i=1} \limits^{n} [x \lt i]，通过这个转化我们把统计 maxmax 的期望转化成统计每个变量都 <a\lt a 的方案数的和。我们枚举一个 aa，如有 dis1<adis_1 \lt a 那么 0,10,1 两种颜色就可以任选，如果有 dis0≥adis_0 \ge a，那么概率为 00。否则这个恰有一种方法。开数组统计即可。
复杂度 O(n)O(n)。

[HNOI2009] 梦幻布丁

传送门
观察到把 xx 颜色改为 yy 颜色实质上就是合并 xx 和 yy 的过程，所以我们采用启发式合并。
  • 每个颜色维护一个数组 G[c]，里面存放当前所有颜色为 cc 的位置。
  • 全局维护一个答案 ansans —— 当前有多少段。
  • 每次要把颜色 xx 改为 yy，就把 所有 G[x] 中的下标位置颜色改为 yy。
  • 在修改颜色前，如果相邻位置原本已经是 yy，那么这一段会被“连起来”，所以答案 ans--。
由于每次操作可能把很多位置移动到另一个颜色，如果我们总是把“大集合”并到“小集合”，复杂度会变得很大，几乎是 O(n2)O(n^2)。
所以采用始终把较小的那个集合并到较大的集合的策略，这种策略我们叫它启发式合并，时间复杂度是 O(nlog⁡n)O(n\log n)，因为每次移动集合大小至少翻倍，所以每个位置最多被移动 log⁡\log 次。
时间复杂度 O(nlog⁡n)O(n \log n)。

P10953 逃不掉的路

传送门
这题比较板。
转化一下问题，其实就是边双缩点，再利用最近公共祖先求所谓“必经之路”。
Tarjan 算法主要为记录两个数组 dfnidfn_i 和 lowilow_i。
dfnidfn_i 表示将图进行 dfs 遍历的时间戳，即遍历到的顺序。
lowilow_i 表示当前点及其子树通过非父边能回到的最小的 dfndfn，简单的说就是“我能通过某些回边向上回溯到的最早祖先”。
Tarjan 算法的主要流程就是利用 dfs 的方式在标记每个遍历到的点的 dfnidfn_i 的同时，对 lowilow_i 进行赋值。
对于这题这一类边双的问题，需要去判割边，vv 是 uu 在搜索树上的儿子的情况下，若 lowv>dfnulow_v \gt dfn_u，则判断这条边为割边。我们一般用栈去维护当前 bcc 的边，当这条边是割边，将栈中属于当前分量的边全部弹出，构成一个边双（edge-bcc），最后每个 bcc 编号作为新图中的一个节点，桥作为新图中的边。
不难发现，缩点之后，这张图就变成了一棵树，此时对于图中任意两点 aa 和 bb，他们之间的必经边即为两点分别处在的边双之间的距离，因为每个边双当中的边都可任意到达，因此一定不是必经边。
剩下部分就是很常规的求 LCA 然后计算两点间路径长度了，倍增，树剖理论都可行。
时间复杂度 O(nlog⁡n)O(n \log n)。

[APIO2018] 铁人两项

传送门
首先引入一个概念，名曰“圆方树”。
构造：将一个无向连通图的所有点双拆开后，增加一个方点将其与这个点双内所有的点连边。
一个结论：每一对相邻且连通的点双之间一定有公共点，这个点即是两个点双之间的割点。
证明：两个相邻且联通的点双一定会有割点将其分离，而这个割点一定与两个点双共点。
由上面的结论可推出(广义)圆方树的性质之一:
圆方树上的圆点和方点一定交替出现。
同时一个点是割点的充要条件是：这个点在圆方树上的度数一定大于 11。
如果想进一步了解，请自行阅读圆方树。
言归正传，这题简化题意就是给定一张简单无向图，问有多少对三元组 (s,c,f)(s,c,f) 满足存在一条简单路径从 ss 出发，经过 cc 到达 ff。
说到简单路径，就必须提一个关于点双很好的性质：对于一个点双中的两点，它们之间简单路径的并集，恰好完全等于这个点双。即同一个点双中的两不同点 u,vu,v 之间一定存在一条简单路径经过给定的在同一个点双内的另一点 ww。
这个结论告诉我们，考虑两圆点在圆方树上的路径，与路径上经过的方点相邻的圆点的集合，就等于原图中两点简单路径上的点集。
对于这道题，考虑固定 s,fs,f，求合法的 cc 的数量，一个易证的结论，合法的 cc 的数量等于 s,fs,f 之间简单路径的并集的点数减去 s,fs,f本身。
考虑对原图建出圆方树，两点之间简单路径的点数，就和它们在圆方树上路径经过的方点和圆点的个数有关，注意，这里的方点实际上就是点双。
接下来是圆方树的一个常用技巧：路径统计时，点赋上合适的权值。就本题而言，每个方点的权值为对应点双的大小，而每个圆点权值为 −1-1。
这样赋权后则有两圆点间圆方树上路径点权和，恰好等于原图中简单路径并集大小减 22。
此时，问题就转化为统计圆方树上两圆点路径权值和之和。考虑统计每一个点对答案的贡献，即权值 ×\times 经过它的路径的条数，可以用树形 DP 求解，需要注意，可能存在图不联通的情况，需要额外处理一下。
时间复杂度 O(n+m)O(n+m)。

后记

可能有些地方表述不当，都是自己的一些理解，可能不够严谨，轻喷。
以上题目时间复杂度的分析均为粗略分析，没有那么精准，仅供参考。
若对上述题目做法有不同观点，是容许的，题目做法不为一，上述题解仅提供作者的做法，同样仅供参考。
顺便吐槽一下，公式好难打！！！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...