题解：P17854 [LBA-OI R6 B] 凌云沐雨

jhashexcoder · 2026-11-12 17:12:36 · 题解

注意到当且仅当置换环数量等于集合大小时，答案正确。

进一步注意到允许的询问次数为 n-1，考虑每次插入一个数。

分析得：

假设当前已有 m 个数排好序，将新数放在末尾进行询问。

若新数实际应该插入第 x 个位置，则前 x-1 个元素各自形成一个置换环，剩余元素形成一个置换环。

因此置换环数量为 (x-1)+1=x。

即询问返回值就是新数应插入的位置。

于是从一个元素开始，每次询问并将新元素插入对应位置，恰好使用 n-1 次询问。

最终得到按值升序排列的下标序列，求逆排列即可得到答案。

时间复杂度 O(n^2)，空间复杂度 O(n)。

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;

    stack<int> a;
    for (int i = 1; i <= n; i++) {
        a.push(i);
    }
    vector<int> t1;
    vector<int> t2;
    t1.push_back(a.top());
    a.pop();
    while (!a.empty()) {
        cout << "? " << t1.size() + 1 << " ";
        for (auto i : t1) {
            cout << i << " ";
        }
        cout << a.top() << endl;
        int x;
        cin >> x;
        if (x == -1) {
            return 0;
        }
        int cnt = 0;
        for (auto i : t1) {
            if (cnt == x - 1) {
                t2.push_back(a.top());
            }
            t2.push_back(i);
            cnt++;
        }
        if (x == t1.size() + 1) {
            t2.push_back(a.top());
        }
        t1.clear();
        t1 = t2;
        t2.clear();
        a.pop();
    }

    t2.resize(n);
    for (int i = 0; i < n; i++) {
        t2[t1[i] - 1] = i + 1;
    }
    t1 = t2;

    cout << "! ";
    for (auto i : t1) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

如果不用 endl 记得要手动刷缓冲区。

代码极其屎山，轻喷。