提出 #75916455

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int N;
    cin >> N;

    // 需要达到的边数下界（向上取整）
    long long need_edges = ((long long)(N - 2) * (N - 2) + 1) / 2;
    if (need_edges < 2) need_edges = 2;               // 至少两条边
    int target_len = (int)need_edges + 1;              // 顶点数 = 边数 + 1

    // visited 数组，记录边是否已使用
    vector<vector<char>> used(N + 1, vector<char>(N + 1, 0));

    vector<int> path;
    path.reserve(target_len);
    path = {1, 3};
    used[1][3] = used[3][1] = 1;

    // tried[i] 表示以 path[i] 为 prev、path[i+1] 为 curr 时，
    // 已经尝试过哪一个候选 next（0 表示尚未尝试 prev+1，1 表示 prev+1 已尝试）
    vector<int> tried(path.size() - 1, 0);

    while ((int)path.size() < target_len) {
        int prev = path[path.size() - 2];
        int curr = path.back();

        // 两个候选：prev+1, prev-1
        int cands[2] = {prev + 1, prev - 1};
        int &t = tried.back();
        bool found = false;

        for (; t < 2; ++t) {
            int nxt = cands[t];
            if (nxt < 1 || nxt > N) continue;
            if (nxt == curr) continue;
            if (used[curr][nxt]) continue;

            // 前进一步
            used[curr][nxt] = used[nxt][curr] = 1;
            path.push_back(nxt);
            ++t;                        // 当前状态记录下一个要尝试的候选
            tried.push_back(0);        // 新状态尚无尝试
            found = true;
            break;
        }

        if (!found) {
            // 回溯一步
            // 题目保证一定有解，path 长度不会退到 2 以下
            int last = path.back(); path.pop_back();
            int curr_new = path.back();
            used[curr_new][last] = used[last][curr_new] = 0;
            tried.pop_back();
        }
    }

    // 输出答案
    cout << path.size() << '\n';
    for (size_t i = 0; i < path.size(); ++i) {
        if (i) cout << ' ';
        cout << path[i];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

提出情報

ジャッジ結果