首页 > 代码库 > Permutation

Permutation

2024-07-11 21:13:33   223人阅读

uva11525:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2520

题意：求1,2,3,4，.....k个数所形成的全排列中的第n个。其中n的是由  计算出，给出每个si。

题解：这一题如果知道康托展开的话，就很简单。X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!表示求第X个全排列的话，那么第一个数就是所有数中第 an+1小的数，第二个数就是剩余数中第an-1+1小的数。知道了这个结论之后，就可以用线段树来维护。每次查找第k个数，然后把这个数删除。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using   namespace std; 6 const int N=50004; 7 struct  Segtree{ 8     int l,r,sum; 9     inline int mid(){10        return  (l+r)/2;11     }12 }num[N*4];13 void pushup(int rt){14    num[rt].sum=num[rt<<1].sum+num[rt<<1|1].sum;15 }16 void build(int rt ,int l,int r){17     num[rt].l=l;18     num[rt].r=r;19     if(l==r){20        num[rt].sum=1;21        return;22     }23    int mid=num[rt].mid();24    build(rt<<1,l,mid);25    build(rt<<1|1,mid+1,r);26    pushup(rt);27 }28 int  query(int pos,int rt){29     if(num[rt].l==num[rt].r){30         num[rt].sum=0;31         return num[rt].l;32     }33       int ans;34     if(num[rt<<1].sum>=pos)ans=query(pos,rt<<1);35     else ans=query(pos-num[rt<<1].sum,rt<<1|1);36     pushup(rt);37     return ans;38 }39 int main(){40    int k, t,cas;41    scanf("%d",&cas);42    while(cas--){43       scanf("%d",&k);44       build(1,1,k);45       for(int i=1;i<=k;i++){46           scanf("%d",&t);47          int ans=query(t+1,1);48          if(i<k)printf("%d ",ans);49          else  printf("%d\n",ans);50       }51    }52 }
View Code

 


联系
我们