2024 Sep

Question 1. 「LAOI-6」Yet Another Graph Coloration Problem

给定一张 \(n\) 个点 \(m\) 条边的简单无向图，求是否存在一个点的黑白染色方案使得：

• 两种颜色的点都至少各有一个。
• 任意两个颜色不同的点之间都有至少 \(2\) 条不同的简单路径。

\(n,m\leq 2\times 10^5, \sum n, \sum m\leq 2\times 10^6\)

首先不连通肯定无解，这个先判掉。

考虑连通的时候什么时候会无解，可以发现树肯定无解，因为树的一个重要性质是“任意两个点之间有唯一的简单路径”，在环上，只要两个点之间的简单路径会经过环上的边，那么肯定有至少 \(2\) 条简单路径。

换句话说，边双内的两个点之间一定有至少 \(2\) 条简单路径，考虑边双缩点后形成的树。

选择一个大于 \(1\) 的边双，从该边双内选择一个点 \(u\)，并将该边双通过 \(u\) 节点连出的子树内的所有边双染成一种颜色，其余点染成另一种颜色。

此时两个异色点肯定会跨边双，故一定有至少 \(2\) 条简单路径。

Question 2. 【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题

给定正整数 \(a\)，求出正整数 \(b,c,d\) 满足 \(a+b+c+d = \gcd(a,b) + \operatorname{lcm}(c,d)\)

\(T\leq 2\times 10^6, a\leq 10^9\)，要求 \(b,c,d\leq 1.7\times 10^9\)。

令 \(b=1\)，即有 \(\operatorname{lcm}(c,d) - c - d = a\)，考虑 \(f(c,d) = \operatorname{lcm}(c,d) - c - d\) 的性质。

从 \(a\) 为奇数开始，如果令 \(c = 2\) 而 \(d\) 为另一奇数，则 \(f(c,d) = 2d - 2 - d = d - 2\)，可以遍取所有奇数。

如果令 \(c = 4\) 而 \(d\equiv 2 \pmod 4\)，则 \(f(c,d) = 2d - 4 - d = d - 4\)，可以遍取所有满足模 \(4\) 为 \(2\) 的数字。

归纳有：令 \(c = 2^k\) 而 \(d\equiv 2^{k-1} \pmod {2^k}\)，则 \(f(c,d) = d - 2^k\)，可以遍取所有正整数 \(a\)。

此时上限为 \(1.5\times 2^{30}\leq 1.7\times 10^9\)。

Question 3. [Open Cup XXII Stage 2] M. Math

给定一个长度为 \(n\) 的正整数序列 \(a\)，求有多少个 \((i,j)\) 满足 \(a_i^2 + a_j\) 是完全平方数。

\(n, a_i\leq 10^6\)

令 \(a_i^2 + a_j = (a_i + t)^2\)，则有 \(a_j = 2a_i + 1 + 2a_i + 3 + \cdots \leq 10^6\)，故枚举 \(a_i, t\) 的值暴力即可。

时间复杂度是对的，具体是多少不想算了。

Question 4. [Open Cup XXII Stage 2] A. AND

给定一个长度为 \(n\) 的非负整数序列 \(b\)，构造一个序列长度不超过 \(5n\) 的非负整数序列 \(a\) 使得 \(a\) 的连续子序列 AND 的值集合为 \(b\)。

\(n\leq 2\times 10^5, b_i < 2^{20}\)

发现一个问题，就是 \(b\) 的最小值一定会是其它所有值的 AND，反证法显然。

所以把 \(b\) 中元素排个序，相邻两个数之间插一个最小值即可完成构造。

Question 5. [Open Cup XXII Stage 2] E. Eulerian?

给定一个 \(n\) 个点的有向连通图 \(G\)，通过不超过 \(60\) 次以如下格式构造的询问判定 \(G\) 是否具有欧拉回路。

• 选择一个点集 \(S\)，交互库给出 \(S\) 的导出子图的边数。

\(n\leq 10^4, m\leq 10^5\)

逆天问题。

首先第一次询问我们能够找出图的边数 \(m\)。

接下来，我们按照如下操作执行 \(29\) 轮：

• 对于每个点 \(u\)，等概率随机将其划分至点集 \(A\) 与点集 \(B\)，并分别询问 \(A,B\)，如果 \(A,B\) 之间的边数不为偶数则无解。

证明：