USACO11FEB SILVER 牛线Cow Line

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Sat Oct 13 20:08:07 CST 2018

In Category: NoCategory

Description：

康托展开模板。

$1\leqslant n\leqslant 20$

Solution：

对于一个排列，康托展开的公式是： $$ x=\sum_{i=1}^n(n-i)!\sigma_i $$ $\sigma_i$ 是比 $a[i]$ 小且在 $a[i]$ 之前没有出现过的数的个数。

逆康托展开大概就是先把 $k-1$ 然后第 $i$ 位除 $(n-i)!$ ，找还没有用过的第这个数的数。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

char getc()

{

	register char c = getchar();

	while(c != 'P' && c != 'Q')c = getchar();

	return c;

}

long long fac[21];

int a[21];

void build()

{

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	long long res = 0;

	for(int i = 1;i <= n;++i)

	{

		int sum = a[i] - 1;

		for(int j = 1;j < i;++j)

		{

			if(a[j] < a[i])--sum;

		}

		res += sum * fac[n - i];

	}

	cout << res + 1 << endl;

	return;

}

int v[21];

void rever()

{

	long long k;

	scanf("%lld",&k);--k;

	for(int i = 1;i <= n;++i)v[i] = i;

	int p = n;

	for(int i = 1;i <= n;++i)

	{

		int s = k / fac[n - i];k = k % fac[n - i];

		cout << v[s + 1] << " ";

		for(int j = s + 1;j < p;++j)v[j] = v[j + 1];--p;

	}

	cout << endl;

	return;

}

int main()

{

	fac[0] = 1;

	for(int i = 1;i <= 20;++i)fac[i] = fac[i - 1] * i;

	scanf("%d%d",&n,&m);

	char c;

	for(int i = 1;i <= m;++i)

	{

		c = getc();

		if(c == 'P')rever();

		else build();

	}

	return 0;

}

In tag: 数学-康托展开

wjh15101051