cf102012I. Rikka with Sorting Networks

题目描述

题解

考虑到最后的序列为 $(n-1)^2+1$ 个，所以直接枚举每个排序器有没有生效即可。效率： $O(n^2 imes 2^k)$ 。

考虑正确性，一个序列经过 $k$ 个操作后只能变成另一个序列，所以能够得到某个序列的初始序列的集合是不会重复的，所以直接做就好了。

代码

#include<bits/stdc++.h>
using namespace std;
int T,n,m,P,s,p[55],U[15],V[15];
void dfs(int x){
    if (!x){s++;return;}
    if (p[U[x]]>p[V[x]]) return;
    dfs(x-1);swap(p[U[x]],p[V[x]]);
    dfs(x-1);swap(p[U[x]],p[V[x]]);
}
void work(){
    scanf("%d%d%d",&n,&m,&P);s=0;
    for (int i=1;i<=m;i++)
        scanf("%d%d",&U[i],&V[i]);
    for (int i=1;i<=n;i++) p[i]=i;
    dfs(m);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (j==i || j==i-1) continue;
            p[j]=i;
            for (int k=1,l=1;k<=n;k++){
                if (k==j) continue;
                if (l==i) l++;
                p[k]=l++;
            }
            dfs(m);
        }
    }
    printf("%d
",s);
}
int main(){
    for (scanf("%d",&T);T--;work());
    return 0;
}