题解：CF1521C Nastia and a Hidden Permutation

haoran150 · 2026-07-24 10:19:48 · 题解

首先我们的询问有 4 个参数，但是其中 x 是一个副作用参数，会影响我们对位置上正确的数的判断。我们需要想办法减小 x 的影响，因此我们可以让 t=1 时 x 恒取 n-1，这样 t=1 的式子就可以变成 \max(\min(n-1,p_i),p_j)。同理在 t=2 时 x 取 1，得到 \min(p_i,\max(x+1,p_j))。

注意到 t=1 的式子最外层是 \max，假如我们输入 p_k=1 的 k 和一个等待求解的位置 p_x，我们得到的返回一定是 p_x 的真实值。这样整个排列在找到 1 的位置后只需要 n-1 次即可还原。

现在考虑如何找 p_k=1。我们如果要找一个最小值，我们肯定希望最外层的运算为 \min，所以我们采用 t=2 寻找 1。

我们剩余的次数还有 \lfloor\frac{n}{2}\rfloor+31 次。可以先考虑两两分组，如果最小值大于 2 ，说明里面两个数都大于 2，一下排除两个数。

遇到最小值为 1，直接说明 p_i=1，解决问题，跳出循环。

遇到最小值为 2 的情况，只有两种可能：有一个数为 2，或者 p_j 为 1。为了排除第二种情况，我们将 p_i 和 p_j 互相交换再次询问，这样可以保证不误判 2 的情况。

正反交的次数最多为 2，即 2 的所在组在 1 所在组之前，且 p_k=1 在偶数位置上。

如果想要跑满询问，1 所在组必须是最后一组，这样才能卡到最劣 \lfloor\frac{3n}{2}\rfloor+1。

代码非常简单，没有坑点难点。

:::success[code]

int n,p[N];
int ask(int type,int x,int y){
    int ex = 0;
    if(type==1) ex = n-1;
    else ex = 1;
    write("? ",type,' ',x,' ',y,' ',ex);
    cout<<endl;
    int res;
    read(res);
    return res;
}
void work(){
    read(n);
    int i1 = 0;
    for(int i=1;i<=n/2;++i){
        int res = ask(2,i*2-1,i*2);
        if(res==1){
            i1 = i*2-1;
            p[i*2-1] = 1;
            break;
        }
        if(res==2){
            if(ask(2,i*2,i*2-1)==1){
                i1 = i*2;
                p[i*2] = 1;
                break;
            }
        }
    }
    if(!i1) i1 = n,p[n] = 1;
    for(int i=1;i<=n;++i){
        if(i1==i) continue;
        p[i] = ask(1,i1,i);
    }
    write("! ");
    for(int i=1;i<=n;++i){
        write(p[i],' ');
    }cout<<endl;
    return ;
}
int T;
signed main(){
    read(T);
    while(T--) work();
    return 0;
}

:::