CF 1325 题解

CF 1325 题解

A EhAb AnD gCd

有 \(\gcd(1,x)=1,\text{lcm}(1,x)=x\) , 因此输出 \(1 x\).

B CopyCopyCopyCopyCopy

要求严格上升子序列, 那么答案的上界当然是去重后的元素个数.

能否取到上界呢? 当然可以, 每一段内选一个你想要的就可以了.

C Ehab and Path-etic MEXs

发现 \(0,1\) 两条边一定能用一条链串起来, 因此 \(n>2\) 时答案下界为 \(2\).

想要让 \(\text{MEX}\) 尽量小, 那么我们只要把 \(0,1,2\) 的边串不成一条链就能把上界卡到 \(2\).

怎么构造这个条件呢? 找一个度数大于等于 \(3\) 的点, 找到相邻的 \(3\) 条边分配 \(0,1,2\), 剩下的随便分配即可.

不存在度数大于等于 \(3\) 的怎么办? 那一定是一条链了, 答案一定是 \(n\), 与构造无关, 因此直接随便分配即可.

D Ehab the Xorcist

首先, 我们知道, 异或和小于等于代数和, 那么 \(m>n\) 时无解.

其次, 我们知道, 如果在 \(k\) 个数中, 某个二进制位被点亮 \(p\) 次, 那么会损失掉 \(p-(p\bmod2)\) 次, 这个数一定是偶数, 因此当 \((m-n)\bmod2=1\) 时无解.

设 \(\Delta=m-n\), 那么我们想构造出来 \(\Delta\) 的损失量, 只需要重复出现两个 \(\frac{\Delta}{2}\) 即可, 那剩下的怎么办? 塞一个 \(m\) 就可以了, 不难发现这样一定合法.

答案要求数最少, 有可能有两个数的构造吗? 设这两个数为 \(a,b\), 根据 \(m=n+2\times(a \operatorname{and} b)\) 可以求出 \(a \operatorname{and} b = \frac{\Delta}{2}\).

由于 \(a \operatorname{and} b\) 和 \(a \operatorname{xor} b\) 显然不会有相同的二进制位, 而这个条件成立时也不难构造出对应的 \(a,b\) , 那么这个条件对于有解充要.

那么我们把无解判掉, 现在认为有解, 一个可能的解的构造是 \(n \operatorname{or} \frac{\Delta}{2},\frac{\Delta}{2}\).

在刚刚那个充要条件成立时, \(3\) 个元素那个方案的后两项做按位或不会对代数和以及异或和造成任何影响.

只有一个元素的方案? 这只能是 \(n=m>0\) 了.

什么也没有的方案? 那就是样例里面的 \(n=m=0\)了.

E Ehab's REAL Number Theory Problem

一个重要的条件是每个数的因数个数不超过 \(7\), 这意味着一个数最多有 \(2\) 个质因数.

一个数中如果有平方因子, 那么把它除掉则无影响.

( 经过上面的操作后 ) 一个数如果是 \(1\), 把它输出出来即可; 否则每个数都可以表示为 \(p_1p_2\) 的形式, 其中 \(p_1,p_2\in \{1\} \cap \mathbb{P}\).

考虑图论建模, 把每个数的 \(p_1\) 和 \(p_2\) 连一条边, 这样, 问题变成了: 从边集 \(E\) 中选择一个子集 \(S\) , 使得 图 \(G=<E,S>\) 中每个点的度数都是偶数, 求合法的 \(S\) 的大小的最小值.

首先, 一个环必然合法.

考虑一个更加复杂的方案, 如果这个方案中边集 \(S\) 不联通, 那么选择其中最小的那个连通块一定更优, 因此最优解的边集一定联通.

如果这个连通块, 它存在一个点的度数大于 \(2\), 那么根据边数等于度数和除以 \(2\), 那么 \(|S|\) 一定超过了点数, 所以必然含有环, 那么我找到其中的一个环必然更优.

因此最优解一定是环, 这把问题转化为了寻找一个最小的环.

这个问题并不好做, 但是发现我们的转化并不充要, 由于原题中每个数不会超过 \(10^6\), 那么每条边一定连着一个小于 \(1000\) 的数, 这样的点不会超过 \(200\) 个, 我们只要枚举这些点做 bfs, 每次有非 bfs 树边就更新答案就可以了.

F Ehab's Last Theorem

首先考虑 dfs 树.

我们记 \(sq = \lceil \sqrt n \rceil\), 那么 dfs 树上每个点的返祖边都至多有 \(sq - 3\) 条, 否则直接输出环即可.

解释: 如果一个点连出来了 \(k\) 条返祖边, 由于无重边, 那么第一条返祖边至少是它的 二级祖先 , 而最严格条件下 (也就是它向离他最近的祖先节点连边), 那么至少会存在一个大小为 \(k + 2\) 的环.

如果失败了, 那么意味着每个点至多连出 \(sq - 3\) 条返祖边, 我们寻找支配集的过程中, 每次钦定一个当前可用的最深的点在支配集中, 同时认为他自己, 他的父亲, 他的返祖边所连结点不可用, 这些点加起来不会超过 \(sq-3+1=1=sq-1=\lceil \sqrt n \rceil-1\leq \lfloor \sqrt n \rfloor\) 个, 那么这个操作至少持续 \(sq\) 轮, 一定有合法答案, 模拟即可.