11.9 Refact.ai Match 1 (Codeforces Round 985)

Solve : A~F (6/9)

Rank : 94

Rating : \(2212+136=2348\)

Perf : 2756（原来算法）2723（准确值）

发挥评价：Good+

感谢广义 Chinese Round（）愉快上分。

这场 C 和 E 各一发罚时，E 吃完之后迅速发现自己的做法问题。

F 想清楚了再开始写，没有产生罚时。如果能更快一点就更好了。

CF2029D

给你一个无向图，其中有 \(n\) 个顶点和 \(m\) 条边。

您可以执行以下操作：

• 选择三个不同的顶点 \(a\)、\(b\) 和 \(c\)，然后对每条边 \((a,b)\)、\((b,c)\) 和 \((c,a)\) 执行以下操作：
  • 如果该边不存在，则添加该边。相反，如果存在，则删除它。

当且仅当该图没有边，或该图是一棵树时，一个图才被称为酷图：

最多进行 \(2\cdot \max(n,m)\) 次操作把图变成酷图，可以证明有解。

Solution：考虑把所有不连 \(1\) 的边通过第三个选 \(1\) 清除掉，最后必然剩下一个菊花和一些孤点。

考虑如果菊花为空，直接结束，否则用菊花的一条边把剩下的孤点连起来。

CF2029E

对于两个整数 \(x\) 和 \(y\)（\(x,y\ge 2\)），当且仅当 \(x\) 可以通过下面的操作变换为 \(y\) 时，我们才说 \(x\) 是 \(y\) 的生成器：

• 选择 \(x\) 的因数 \(d\)（\(d\ge 2\)），然后将 \(x\) 增加 \(d\)。

现在，凯文给出了一个数组 \(a\)，它由 \(n\) 个互不相同 \(\ge 2\) 的整数组成。

你必须找到一个整数 \(x\ge 2\)，使得 \(x\) 是序列所有数的生成器，或报告无解。

首先发现 \(2\) 可以产生所有偶数（进一步的，所有合数）

而任何奇数会一步变回偶数，猜测只需要选 \(2\)，故不能有质数。

显然，不会这么简单。

有某个样例，我们知道可以有一个质数（两个以上绝对不行），只当这个质数可以生成所有数列中的数。

现在就剩判断这个质数能不能生成了，直接 bfs 显然超时。

考虑如果是偶数，\(\ge2p\) 即可，如果是奇数，最后一步一定是偶数生成的，这个偶数最大为它减去最小质因子，于是预处理后暴力判断即可。

CF2029F

给定一个环，边有红蓝双色，询问是否任意两点间都存在一条颜色回文路径（可以不简单）

先特判某一种颜色出现次数大于等于 \(n-1\) 的为 Yes。

这种题目，显然考虑手玩样例来找找规律。

发现样例里所有奇数都有解，大胆猜测由于奇数对路径奇偶性没有限制，可能全部有解，于是尝试手玩一些证明这个结论。

但是被 RRRBB 卡掉了，\((1,4)\)（从零标号）没有。

为啥没有？因为路径第一步必然是 R 最后一步必然是 B，包没有的。

这个很有启发性：环中不能同时存在 RR 和 BB，这个结论感觉方向很对，现在变成单个 R 和连续 B 段交替了。（考虑两种颜色反转不影响答案）

发现由于路径可以不简单，B 连续段只和奇偶性有关，可以等价为长 \(1\) 或者 \(2\)。

发现当 B 连续段长偶数时候，从两侧出的 B 段奇偶性相同。

于是出现两个偶数 B 段就坠机了。

同时由于 ABABAB 也无解，发现没有偶数段也坠机了，具体可以两边一起走，发现有时它们总得向同一方向走，无法汇合。

合理猜测，单个偶数段一定有解因为无解情况太多了。

确实如此，证明也考虑两个一起走，把一个调到偶数段旁边之后，一个跳过偶数段，另一个走个来回，然后就发现它们能汇合了。