题解：P15652 [省选联考 2026] 排列游戏 / perm

Register_int · 2026-03-08 16:47:58 · 题解

根据这个题的道理，等价于问出所有前后缀 \min。考虑以 0 为分界，左边只有前缀 \min，右边只有后缀 \min，所以只要问恰好 n 个位置。

还原排列贪心即可，左右两边哪边限制紧往哪边填。

upd：FJ 不发代码，自己复现了一下。QOJ 过了应该没啥问题。

#include "perm.h"
#include <bits/stdc++.h>

using namespace std;

void init(int c, int t) {}

vector<int> perm(int n) {
    vector<int> pre(n), suf(n); int pos = n - 1;
    for (int i = 0; i < n - 1; i++) {
        pre[i] = query(i + 1, n - 1);
        if (!pre[i]) {
            pos = i;
            for (int j = n - 1; j > i; j--) {
                suf[j] = query(0, j - 1);
            }
            break;
        }
    }
    vector<int> ans(n, -1), vis(n);
    ans[0] = pre[0], ans[n - 1] = suf[n - 1];
    vis[pre[0]] = vis[suf[n - 1]] = 1;
    for (int i = 1; i < n - 1; i++) {
        if (pre[i] != pre[i - 1]) ans[i] = pre[i], vis[pre[i]] = 1;
        if (suf[i] != suf[i + 1]) ans[i] = suf[i], vis[suf[i]] = 1;
    }
    for (int l = 0, r = n - 1, i = n - 1; ; i--) {
        for (; ~i && vis[i]; i--);
        if (i < 0) break;
        for (; l < pos && ~ans[l]; l++);
        for (; r > pos && ~ans[r]; r--);
        ans[pre[l] > suf[r] ? l : r] = i, vis[i] = 1;
    }
    return ans;
}