专栏首页wymHDU 6628 (2019杭电第五场 1005) permutation 1 (全排列)

HDU 6628 (2019杭电第五场 1005) permutation 1 (全排列)

题意:求 n的 全排列 差值序列(后一项减前一项 n-1项) 第 k 小的全排列,2 <=n<=20, 1<= k <=min(10000,n!)

题解:8!= 40320 > max (k) 预处理大于等于8的数,8之后就是a[1] = n 的全排列。

#include <bits/stdc++.h>
using namespace std;
struct No{
	int a[10];
	char s[10];	
}no[11][1000006];
int cmp(No a,No b){
	return strcmp(a.s,b.s)<0;
}
int main()
{
	int _;
	int n,k;
	for(int i=2;i<=8;i++){
		int a[10];
		k = 0;
		char s[10];
		for(int j=1;j<=i;j++)
			a[j] = j;
		do{
			for(int j=0;j<i-1;j++)
				s[j] = a[j+2] - a[j+1] + 'A' ;
			s[i-1] = '\0';
			
			strcpy(no[i][++k].s,s);
			for(int j=1;j<=i;j++)
				no[i][k].a[j] = a[j];
		}while(next_permutation(a+1,a+i+1));
		sort(no[i]+1,no[i]+k+1,cmp);
	}
	for(scanf("%d",&_);_;_--){
		scanf("%d %d",&n,&k);
		if(n>8){
			int tt[30];
			tt[1] = n;
			for(int i=2;i<=n;i++)tt[i] = i-1;
			do{	
				k--;if(k==0)break;
			}while(next_permutation(tt+1,tt+1+n));
			printf("%d",tt[1]);
			for(int i=2;i<=n;i++){
				printf(" %d",tt[i]);
			}
			printf("\n");
			continue;
		}
		printf("%d",no[n][k].a[1]);
		for(int i=2;i<=n;i++){
			printf(" %d",no[n][k].a[i]);
		}
		printf("\n");	
	}
	return 0;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [USACO06JAN]牛的舞会 Tarjan模版

    用户2965768
  • HDU 6514 Monitor 二维前缀和

    用户2965768
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • POJ 2594 Treasure Exploration(最小路径覆盖+Floyd)

           题意是有n个点,m条单向边,然后在边上放机器人,问最少放多少个机器人能遍历到所有的点。

    Ch_Zaqdt
  • 【AtCoder - 2300】Snuke Line(树状数组)

    每隔d站停一次的列车,一定能买到购买区间的长度≥d的纪念品。 长度比d小但包含了d的倍数的纪念品也可以买到。 所以,如果按长度给纪念品排序,用树状数组维护长...

    饶文津
  • BZOJ2535: [Noi2010]Plane 航空管制2(拓扑排序 贪心)

    首先不难想到拓扑排序,但是直接对原图按\(k\)从小到大拓扑排序是错的。因为当前的\(k\)大并不意味着后面的点\(k\)也大

    attack
  • BZOJ4010: [HNOI2015]菜肴制作(拓扑排序 贪心)

    attack
  • loj#6031. 「雅礼集训 2017 Day1」字符串(SAM 广义SAM 数据分治)

    考虑K比较小的情况,可以直接暴力建SAM, 枚举w的子串算出现次数。询问用个 的vector记录一下每次在vector里二分就好。

    attack
  • 【LeetCode第 164 场周赛】回顾

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 洛谷P4723 【模板】线性递推(多项式取模 线性代数)

    attack

扫码关注云+社区

领取腾讯云代金券