题解 CF1334D 【Minimum Euler Cycle】

AutumnKite · 2020-04-11 13:16:09 · 题解

宣传 blog（Github Pages 上不去可以用 Gitee 上的镜像）

题解

看到完全图，欧拉回路，以及字典序最小，一个很自然的想法是从 1 开始，每次走能走的最小的那个点。

模拟发现，这样走一定能恰好走出一条欧拉回路，顶点序列如下：

我们可以将这个序列分成若干组，可以更直观的看出规律：

于是我们求出 l,r 在第几组中的第几个，直接模拟即可。

注意需要特判最后的 1。

代码

const int N = 100005;

int n;
long long l, r;

std::pair<int, int> get(long long l) {
    int p = 1;
    while (p < n && l > 2 * (n - p)) {
        l -= 2 * (n - p);
        ++p;
    }
    return {p, l};
}

void solve() {
    read(n), read(l), read(r);
    bool flag = 0;
    if (r == 1ll * n * (n - 1) + 1) {
        if (l == r) {
            print(1);
            return;
        }
        flag = 1, --r;
    }
    std::pair<int, int> L = get(l), R = get(r);
    for (int k = L.first; k <= R.first; ++k) {
        int lb = k == L.first ? L.second : 1;
        int rb = k == R.first ? R.second : 2 * (n - k);
        for (int i = lb; i <= rb; ++i) {
            if (i & 1) {
                print(k, ' ');
            } else {
                print(k + i / 2, ' ');
            }
        }
    }
    if (flag) {
        print(1);
    } else {
        putchar('\n');
    }
}