题解：P2528 [SHOI2001] 排序工作量之新任务

_std_O2 · 2025-07-16 21:39:06 · 题解

分析

注意到 n\le20 我的第一个反应是搜索，打出暴力发现第一问的答案有规律:

瞪眼大法注意到有 \Large f_{i,j}=f_{i,j-1}+f_{i-1,j}-f_{i-1,j-i} 这样的关系，其中 f_{i,j} 表示有 n 个数，j 个逆序对的序列数量。

不难发现这就是个容斥原理，所以方程的正确性也是显而易见的了。

对于第二问，硬控了我整整二十分钟，其实这就是个贪心，要求字典序最小的那个序列，所以我们反向对 a_i=i 这个序列进行swap操作，使得它有 t 个逆序对就行了，具体部分看代码。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=30;int n,t;
int f[N][500];
int a[N],vis[N];
int flag=0,ans2,b[N],num;
signed main(){
    cin>>n>>t;
    for(int i=1;i<=n;i++) a[i]=i;
    f[1][0]=1;
    for(register int i=1;i<=n;i++){
        for(register int k=0;k<=i*(i-1)/2;k++){
            if(k>0 && k-i>=0 )f[i][k]=f[i][k-1]+f[i-1][k]-f[i-1][k-i];
            else if(k>0 && k-i<0) f[i][k]=f[i][k-1]+f[i-1][k];
            else f[i][k]=1;
        }
    }
    cout<<f[n][t]<<endl;
    for(int i=n-1;i>=1;i--){
        for(int j=n;j>i;j--){
            if(num==t){
                for(int i=1;i<=n;i++) cout<<a[i]<<" ";
                return 0; 
            }
            num++;
            swap(a[i],a[j]);
            if(num==t){
                for(int i=1;i<=n;i++) cout<<a[i]<<" ";
                return 0; 
            }
        }
    }
}