BZOJ3301: [USACO2011 Feb] Cow Line

题目大意:

(1)给定一个排列,问排列的序号.

(2)给定一个序号,要求构造出给定序号的排列.

题解:

首先要知道怎么得出排列的序号.

假如序列的长度为$n$,且第$i$个元素为$P_i$.

则序号为:$\sum_{i=1}^{n}(n-i)!\sum_{j=i+1}^{n}[P_i>P_j]$

这样的话可以$O(n^2)$算出排列的序号.

构造序列的话也是一个道理,我是暴力的,没管复杂度...

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

typedef unsigned long long llu;

int a[21],ans[21];
llu fac[21];
bool ok[21];
int main(){
	int n,Q,i,j;
	char s[10];
	cin>>n>>Q;
	llu x;
	for(fac[0]=i=1;i<=20;++i)
		fac[i]=fac[i-1]*i;
	int temp;
	while(Q--){
		scanf("%s",s);
		if(s[0]=='P'){
			cin>>x;
			--x;
			for(i=1;i<=n;++i)
				a[i]=x/fac[n-i],x-=a[i]*fac[n-i];
			memset(ok,1,sizeof ok);
			for(i=1;i<=n;++i){
				temp=0;
				for(j=1;j<=n;++j){
					if((temp+=ok[j])==a[i]+1)
						break;
				}
				ok[ans[i]=j]=0;
			}
			for(i=1;i<=n;++i){
				if(i!=1)
					putchar(' ');
				printf("%d",ans[i]);
			}
			puts("");
		}
		else{
			for(i=1;i<=n;++i)
				scanf("%d",&a[i]);
			for(x=0,i=1;i<=n;++i){
				for(temp=0,j=i+1;j<=n;++j)
					temp+=(a[i]>a[j]);
				x+=fac[n-i]*temp;
			}
			cout<<x+1<<endl;
		}
	}
	return 0;
}