圆桌聚会

GitHub跳转原题关系图返回列表

把编号看成弧、把弧的起点终点看成新图的顶点,座位圈等价于该图的欧拉回路,用 Hierholzer 迭代求出一条弧序列。

OJ: roj

题目 ID: 1738

难度:提高+/省选-

标签:图论欧拉回路构造python

创建: 2026-10-08 10:20

更新: 2026-10-08 10:20

形式化题目

有 2n2n 个人,编号恰好是 0,1,…,2n−10, 1, \dots, 2n-1(其中偶数号为男生、奇数号为女生)。要把他们 排成一个圈 x0,x1,…,x2n−1x_0, x_1, \dots, x_{2n-1},使得对每个 ii(下标模 2n2n 循环)都有

xi+1∈{ 2xi,  2xi+1,  2xi−2n,  2xi+1−2n }. x_{i+1} \in \{\, 2x_i,\; 2x_i+1,\; 2x_i-2n,\; 2x_i+1-2n \,\}.

四个候选值看起来是两对,其实在模 2n2n 意义下可以统一写成

xi+1≡2xi+k(mod2n),k∈{0,1}. x_{i+1} \equiv 2x_i + k \pmod{2n}, \qquad k \in \{0, 1\}.

输入是多组数据,每行一个整数 nn(1≤n≤5×1051 \le n \le 5\times 10^5);对每组输出一行,为空格隔开的 2n2n 个整数,表示从某个位置开始顺时针读下来的座位序列。本题有 Special Judge, 任何一组合法座位都算对。

以样例 n=4n = 4 为例,合法输出之一是 0 1 2 5 3 7 6 4。逐对检查:1=2⋅0+11 = 2\cdot 0+1, 2=2⋅12 = 2\cdot 1,5=2⋅2+15 = 2\cdot 2+1,3=2⋅5−8+13 = 2\cdot 5 - 8 + 1,7=2⋅3+17 = 2\cdot 3 + 1, 6=2⋅7−86 = 2\cdot 7 - 8,4=2⋅6−84 = 2\cdot 6 - 8,最后回到 0=2⋅4−80 = 2\cdot 4 - 8,全部落在合法集合里。

正解

思路

朴素做法。 把 0∼2n−10 \sim 2n-1 当成 2n2n 个节点,每个节点 xx 向 (2x) mod 2n(2x) \bmod 2n 与 (2x+1) mod 2n(2x+1) \bmod 2n 各连一条有向边,题目要的就是这张图上的一个哈密顿回路。 最直接的写法是 DFS 加回溯:维护已用标记,从 00 出发枚举两条出边,选满 2n2n 个数后 再验证首尾相接。搜索树规模 O(22n)O(2^{2n}),只有 n≤10n \le 10(前 20% 数据)能过; 一般图上求哈密顿回路本身是 NP-Complete 的,而本题 nn 可以到 5×1055\times 10^5, 这本身就说明图的结构特殊到能把问题降维。

关键转化:把数字从"点"改成"边"。 重新造一张只有 nn 个顶点的小图 HH,顶点集是 Zn={0,1,…,n−1}\mathbb{Z}_n = \{0, 1, \dots, n-1\}。对每个 y∈{0,…,2n−1}y \in \{0, \dots, 2n-1\} 造一条弧 aya_y:

ay:尾=⌊y2⌋  ⟶  头=y mod n. a_y: \quad \text{尾} = \left\lfloor \frac{y}{2} \right\rfloor \;\longrightarrow\; \text{头} = y \bmod n .

yy 从 00 取到 2n−12n-1,所以 HH 恰好有 2n2n 条弧,且弧的标号 a0,a1,…,a2n−1a_0, a_1, \dots, a_{2n-1} 完美覆盖了 0∼2n−10 \sim 2n-1 —— 每个座位号正好对应一条弧。

为什么这两个问题是等价的? 看两条相邻的座位号 x→yx \to y。弧 axa_x 的头是 x mod nx \bmod n; 而弧 aya_y 的尾是 ⌊y/2⌋\lfloor y/2 \rfloor。要求"站在 axa_x 的头顶点上能接着走 aya_y",即

⌊y/2⌋=x mod n  ⟺  y≡2(x mod n)+k(mod2n),  k∈{0,1}  ⟺  y≡2x+k(mod2n). \lfloor y/2 \rfloor = x \bmod n \;\Longleftrightarrow\; y \equiv 2(x \bmod n) + k \pmod{2n},\; k\in\{0,1\} \;\Longleftrightarrow\; y \equiv 2x + k \pmod{2n}.

最后一步用的是 2(x mod n)≡2x(mod2n)2(x \bmod n) \equiv 2x \pmod{2n}。这正好就是题目的相邻约束。 于是:

  • HH 中一条弧序列,其标号序列就是一圈合法的座位;
  • 反过来,一圈合法座位也唯一对应 HH 中一条弧序列。

也就是说,原问题的哈密顿回路   ⟺  \;\Longleftrightarrow\; HH 的欧拉回路。这是线图 (line graph)的经典对偶:HH 的线图正是原来那张 2n2n 个点的图,在线图上求哈密顿回路 等于在原图上求欧拉回路。

欧拉回路一定存在。 顶点 vv 的两条出弧是 a2va_{2v} 和 a2v+1a_{2v+1},所以出度为 22。 入度方面:aya_y 的头是 y mod ny \bmod n,对固定的 vv,满足 y≡v(modn)y \equiv v \pmod n 的 yy 在 [0,2n)[0, 2n) 中恰有 22 个(vv 和 v+nv+n),所以入度也是 22。 再验证连通性:从 vv 出发可以走到 2v mod n2v \bmod n 与 (2v+1) mod n(2v+1) \bmod n,把 vv 写成二进制后 不断左移一位,容易看出任意两个顶点都能经"左移"链条互相到达,HH 强连通。 入度 == 出度且弱连通的有向图必有欧拉回路,所以答案永远存在,不需要判无解。

Hierholzer 求欧拉回路。 从顶点 00 出发,能走就走(每个顶点用 used[v] 记下已经 用掉几条出弧,取 00 或 11,就决定了走 a2va_{2v} 还是 a2v+1a_{2v+1});走到某个顶点 出弧耗尽时,把它"进来的那条弧"记进 path 并回退一步。因为记录发生在回溯(后序)阶段, path 里是逆访问序,倒过来输出就是欧拉回路的弧标号序列。

以 n=2n = 2 手工走一遍:弧 a0:0→0a_0:0\to 0,a1:0→1a_1:0\to 1,a2:1→0a_2:1\to 0,a3:1→1a_3:1\to 1。 从顶点 00 出发:走 a0a_0 回到 00,走 a1a_1 到 11,走 a2a_2 回到 00,顶点 00 出弧用尽, 登记 a2a_2;回退到 11,走 a3a_3 回到 11,出弧用尽,登记 a3a_3;再回退,依次登记 a1,a0a_1, a_0 和起点哨兵。path =[a2,a3,a1,a0,哨兵]= [a_2, a_3, a_1, a_0, \text{哨兵}],逆序即 a0a1a3a2=0 1 3 2a_0 a_1 a_3 a_2 = 0\,1\,3\,2,正好是一组合法座位(1=2⋅0+11=2\cdot0+1,3=2⋅1+13=2\cdot1+1, 2=2⋅3−42=2\cdot3-4,0=2⋅2−40=2\cdot2-4)。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 10:20
# update_at: 2026-10-08 10:20

import sys

START = -1  # 栈底哨兵:起点顶点没有「进入它的弧」,回溯时跳过


def euler_cycle(n: int) -> list[int]:
    """返回顶点集 Z_n 上一条欧拉回路的弧标号序列,即一组合法座位圈。

    弧 a 从顶点 a//2 出发指向顶点 a%n,共 2n 条;每个顶点出入度都是 2,
    故必存在欧拉回路。Hierholzer 迭代写法:能走就走,走不动了把「进来的那条弧」
    压进 path,最后把 path 逆序即为答案。
    """
    used = bytearray(n)     # 顶点 v 已用掉的出弧数(0 或 1 或 2)
    stack = [START]         # 栈元素是「进入当前顶点的弧号」
    path: list[int] = []    # 回溯顺序登记的弧号(答案的逆序)
    while stack:
        arc = stack[-1]
        v = 0 if arc == START else arc % n          # 弧 arc 的头顶点
        if used[v] < 2:                             # 还有没走过的出弧,继续深入
            used[v] += 1
            stack.append(2 * v + used[v] - 1)       # 出弧编号:2v 或 2v+1
        else:                                       # 出弧走完,回溯时登记进来的弧
            path.append(arc)
            stack.pop()
    return path[-2::-1]     # 逆序,并丢掉末尾的起点哨兵


def solve() -> None:
    data = map(int, sys.stdin.buffer.read().split())
    print('\n'.join(' '.join(map(str, euler_cycle(n))) for n in data))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
// Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
// rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
// rainboy的学习导航网站: https://idx.roj.ac.cn
// create_at: 2026-10-08 10:20
// update_at: 2026-10-08 10:20
//
// ROJ 1738《圆桌聚会》
// 座位圈 x_0..x_{2n-1} 需满足 x_{i+1} ≡ 2*x_i + k (mod 2n),k∈{0,1}。
// 把数字 0..2n-1 看成边:弧 a_y 从顶点 y/2 指向顶点 y mod n(顶点集 Z_n)。
// 每个顶点出度=入度=2,故存在欧拉回路;弧标号序列即合法座位圈。
// Hierholzer 迭代实现(显式栈,防爆系统栈),每条边只走一次,O(n)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

static const int MAXN = 500000;          // n 的上界
static char used[MAXN];                  // 顶点 v 已经走过的出弧数(0..2)
static int stk[2 * MAXN + 5];            // 显式栈:栈元素是「进入当前顶点的弧号」,起点为 -1
static int path[2 * MAXN + 5];           // 回溯时记录的弧号,逆访问序

static char outbuf[1 << 23];             // 输出缓冲
static int outpos = 0;

/** 把非负整数写进输出缓冲,缓冲将满时先落盘。 */
inline void writeInt(int x) {
    if (outpos > (1 << 23) - 32) { fwrite(outbuf, 1, outpos, stdout); outpos = 0; }
    char tmp[12];
    int len = 0;
    if (x == 0) tmp[len++] = '0';
    while (x > 0) { tmp[len++] = char('0' + x % 10); x /= 10; }
    while (len--) outbuf[outpos++] = tmp[len];
}

int main() {
    // 输入只有若干行整数,整块读入后自己扫数字,比 cin/scanf 逐个解析快得多
    string inbuf;
    {
        char chunk[1 << 16];
        size_t got;
        while ((got = fread(chunk, 1, sizeof(chunk), stdin)) > 0) inbuf.append(chunk, got);
    }
    inbuf.push_back('\0');

    char *p = &inbuf[0];
    while (true) {
        while (*p && (*p < '0' || *p > '9')) ++p;   // 跳过空白等分隔符
        if (*p == '\0') break;
        int n = 0;
        while (*p >= '0' && *p <= '9') n = n * 10 + (*p++ - '0');
        if (n <= 0) continue;

        for (int i = 0; i < n; i++) used[i] = 0;    // 只清 0..n-1,避免 O(T*MAXN)

        int top = 0, cnt = 0;
        stk[top++] = -1;                            // 起点 0 没有「进入它的弧」
        while (top > 0) {
            int a = stk[top - 1];                   // 当前所在的弧
            int v = (a < 0) ? 0 : a % n;            // 弧 a 的头 = a mod n
            if (used[v] < 2) {                      // 还有没走过的出弧,就继续深入
                int y = 2 * v + used[v]++;
                stk[top++] = y;
            } else {                                // 出弧走完,回溯时登记进来的那条弧
                path[cnt++] = a;
                --top;
            }
        }

        // path 是逆访问序,最后一项是起点哨兵 -1;倒着输出即为欧拉回路的弧序列
        for (int i = cnt - 2; i >= 0; --i) {
            if (i != cnt - 2) outbuf[outpos++] = ' ';
            writeInt(path[i]);
        }
        outbuf[outpos++] = '\n';
    }

    if (outpos) fwrite(outbuf, 1, outpos, stdout);
    return 0;
}

复杂度

  • 时间:HH 有 nn 个顶点、2n2n 条弧,Hierholzer 每条弧恰好被压栈、出栈一次, 所以单组数据是严格的 O(n)O(n),多组数据总和 O(∑n)O(\sum n)。每组只清 used[0..n-1], 不能 memset 整块数组,否则会退化成 O(T⋅Nmax⁡)O(T \cdot N_{\max})。 实测 10 个数据点(最大单点 ∑n≈1.5×106\sum n \approx 1.5\times10^6)在限时 2000 ms 内余量很大。
  • 空间:used 是 nn 字节,显式栈与答案数组各 2n+22n+2 个 int,共 O(n)O(n)。 n=5×105n = 5\times10^5 时约 8 MB,远低于 256 MB。
  • 实现要点:DFS 深度最坏可达 2n=1062n = 10^6,递归写法会爆系统栈,必须用数组模拟显式栈; 输出最多有 10610^6 个整数(数十 MB),要手写缓冲输出而不是逐个 cout。

总结

  • 换一个"点/边"的视角,NP 难题变成线性算法:把 0∼2n−10\sim2n-1 从顶点降级成弧之后, “相邻约束"就变成了"弧头接弧尾”,哈密顿回路自动变成欧拉回路。这类 "在线图上求哈密顿回路 ⇔\Leftrightarrow 在原图上求欧拉回路"的对偶是构造题的常见套路, 识别信号是约束形如 y≡2x+k(mod2n)y \equiv 2x + k \pmod{2n} 这种"左移一位再加一位"的递推。
  • 存在性可以先证再写:入度 == 出度 ++ 强连通 ⇒\Rightarrow 欧拉回路存在, 所以程序里不需要任何回溯或判无解,直接一路走到底。
  • Hierholzer 的记录时机是后序:栈里存"进入当前顶点的那条弧",出弧用尽才登记, 最后整体逆序,这样天然避免了显式的路径拼接与插入。
  • 工程细节决定能不能过:显式栈防爆栈、按需清空防超时、缓冲输出防 I/O 瓶颈。

数据来源说明:素材源目录带有数据生成脚本 data.py,data/ 下的 10 个测试点是 按题面数据范围自行分层生成的(n=1n=1、n=4n=4、n=2..30n=2..30、n=2kn=2^k、随机小/中/大规模、 n=5×105n=5\times10^5 顶格与多测负载),并非官方原始数据;题面本身是从网络材料重建的, 与官方原题的评测数据可能存在偏差。本文所述算法对 1≤n≤5×1051 \le n \le 5\times10^5 的全部 nn 都给出合法构造,因此结论不受影响。