C. MEX Cycle 题解（构造法）

题目简述

有 $n$ 个龙围成一个环（相邻互为朋友），额外添加一条边 $x-y$。需要构造一个数组 $a$，满足每个位置的值 = 其所有朋友对应值的 $\boldsymbol{\operatorname{MEX}}$。

核心观察

1. 图结构：
   • 普通节点：度数为 $2$（仅左右邻居）；
   • 节点 $x/y$：度数为 $3$（多了一个额外朋友）。
2. MEX 关键性质：
   • 邻居只有 $0$ → $\operatorname{MEX}=1$；
   • 邻居只有 $1$ → $\operatorname{MEX}=0$；
   • 邻居包含 $0$ 和 $1$ → $\operatorname{MEX}=2$。

我们的思路：用 0/1 交替填充数组，特殊位置赋值为 2，完美满足 MEX 规则。

代码构造逻辑

这是一道构造题，无需复杂算法，直接按规则构造答案即可：

1. 以 $x$ 为起点，生成 0/1 交替的序列；
2. 满足特定条件时，将 $x$ 位置设为 $2$；
3. 该构造天然满足所有节点的 MEX 约束。

代码逐行解析

#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    --x; --y;          // 转为 0 下标（方便数组操作）
    vector<int> ans(n);
    // 核心构造：以 x 为起点，0/1 交替填充整个环
    for (int i = 0; i < n; ++i) ans[(x + i) % n] = i % 2;
    // 特殊条件：n 为奇数 或 x/y 奇偶性相同，将 x 设为 2
    if (n % 2 || (x - y) % 2 == 0)
        ans[x] = 2;
    // 输出答案
    for (auto x : ans)cout << x << ' ';
    cout << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}

关键代码解释

1. 下标转换 --x; --y：将题目输入的 $1$ 下标转为 $0$ 下标，适配 C++ 数组。

2. 0/1 交替构造 ans[(x + i) % n] = i % 2： 以 $x$ 为起点，沿着环依次填充 $0,1,0,1\dots$，保证相邻节点值一定不同。

3. 特殊位置赋值 2 if (n % 2 || (x - y) % 2 == 0) ans[x] = 2：

   • $n$ 为奇数：环无法完美 0/1 交替，修正 $x$ 为 $2$；
   • $x$ 和 $y$ 奇偶性相同：额外边 $x-y$ 连接了同值节点，修正 $x$ 为 $2$。

4. 输出 直接打印构造好的数组即可。

正确性证明

1. 普通节点（度数 2）： 邻居是 $0$ 和 $1$，$\operatorname{MEX}=2$（或 0/1 交替满足规则）；
2. 特殊节点 $x$（度数 3）： 赋值为 $2$，其邻居包含 $0$ 和 $1$，$\operatorname{MEX}=2$，完美匹配；
3. 额外边 $x-y$： 构造规则自动兼容这条边的约束。

题目保证一定有解，该构造是通用合法解。

复杂度分析

• 时间复杂度：$O(n)$ 每组用例，总复杂度 $O(\sum n)$，完美适配 $n \le 2\times10^5$；
• 空间复杂度：$O(n)$ 存储答案数组。

总结

这是一道经典构造题，核心是利用 0/1 交替 + 特殊点修正 的简单策略，直接满足所有 MEX 约束，代码极简且效率拉满。