首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >HDU 6628 (2019杭电第五场 1005) permutation 1 (全排列)

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

作者头像
用户2965768
发布于 2019-08-14 06:17:40
发布于 2019-08-14 06:17:40
56800
代码可运行
举报
文章被收录于专栏:wymwym
运行总次数:0
代码可运行

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

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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#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;
} 
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年08月06日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
蓝桥杯之全排列函数 next_permutation()解析
这是一个求一个排序的下一个排列的函数,可以遍历全排列,要包含头文件 下面是以前的笔记 与之完全相反的函数还有prev_permutation
Max超
2019/01/21
5620
HDOJ 1716 排列2(next_permutation函数)
例题: Problem B Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other) Total Submission(s) : 27 Accepted Submission(s) : 10 Problem Description Ray又对数字的列产生了兴趣: 现有四张卡片,用这四张卡片能排列出很多不同的4位数,要求按从小到大的顺序输出这些4位数。
谙忆
2021/01/20
4110
PTA 输出全排列(20 分)
Kindear
2017/12/29
9750
HDOJ 1716 排列2 next_permutation函数
Problem Description Ray又对数字的列产生了兴趣: 现有四张卡片,用这四张卡片能排列出很多不同的4位数,要求按从小到大的顺序输出这些4位数。
谙忆
2021/01/20
4420
排列汇总
。即。将每一个组合与一个二进制数相应起来。枚举二进制的同一时候,枚举每一个组合。如字符串:abcde,则有 00000———null 00001———a 00010 ——–b 00011———ab 00100———c … …
全栈程序员站长
2022/07/18
4750
杭电的题,输出格式卡的很严。HDU 1716 排列2
题很简单,一开始写代码,是用整数的格式写的,怎么跑都不对,就以为算法错了,去看大佬们的算法STL全排列:next_permutation(); 又双叒叕写了好几遍,PE了将近次,直到跑了大佬代码发现,原来格式是这样的。
风骨散人Chiam
2020/10/28
2850
杭电的题,输出格式卡的很严。HDU	 1716 排列2
P1706 全排列问题【STL 全排列函数】
输出自然数 11 到 nn 所有不重复的排列,即 nn 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
Lokinli
2023/03/09
3400
排列类算法问题大总结全排列分析带重复元素的全排列代码下一个排列分析上一个排列分析第k个排列分析排列序号分析排列序号II分析
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
desperate633
2018/08/22
1.4K0
排列类算法问题大总结全排列分析带重复元素的全排列代码下一个排列分析上一个排列分析第k个排列分析排列序号分析排列序号II分析
字符串的全排列和组合算法
http://blog.csdn.net/hackbuteer1/article/details/7462447
bear_fish
2018/09/19
1.5K0
字符串的全排列和组合算法
康托展开公式与全排列应用
{1,2,3,4,...,n}的排列总共有n!种,将它们从小到大排序,怎样知道其中一种排列是有序序列中的第几个?
王小明_HIT
2020/08/27
5450
HDU 6629 (2019杭电第五场 1006) string matching (扩展kmp)
题意: 求字符串 s[i…len−1] and s[0…len−1] i>0 最长公共前缀长度求解过程的比较次数
用户2965768
2019/08/14
4080
排列组合公式及排列组合算法[通俗易懂]
公式P是指排列,从N个元素取M个进行排列。 公式C是指组合,从N个元素取M个进行组合,不进行排列。 N-元素的总个数 M参与选择的元素个数 !-阶乘,如 9!=9*8*7*6*5*4*3*2*1
全栈程序员站长
2022/07/22
28.1K0
排列组合公式及排列组合算法[通俗易懂]
2014年第五届蓝桥杯C/C++B组省赛题目解析
一、啤酒和饮料 啤酒每罐2.3元,饮料每罐1.9元。小明买了若干啤酒和饮料,一共花了82.3元。 我们还知道他买的啤酒比饮料的数量少,请你计算他买了几罐啤酒。 注意:答案是一个整数。请通过浏览器提交答案。 不要书写任何多余的内容(例如:写了饮料的数量,添加说明文字等)。 分析:此题可用循环暴力求解出结果。 数值先都扩大十倍,方便计算。 全部啤酒罐数:823/23=35.78;全部饮料罐数:823/19=43.31;啤酒和饮料对半罐数:823/42=19.59 设啤酒x,饮料y,则根据上述计算可知,x<y,2
Zoctopus
2018/06/04
2.8K0
【C/C++】之组合不重复的3位数
个人主页:天寒雨落的博客_CSDN博客-C,CSDN竞赛,python领域博主 💬 刷题网站:在线刷题 (educoder.net)  特别标注:该博主将长期更新c语言内容,初学c语言的友友们,订阅我的《初学者入门C语言》专栏,关注博主不迷路! 目录 组合不重复的3位数 编程要求 测试输入 测试输出 C语言 题解 易错点 C++ 全排列函数 next_permutation 代码 执行结果 ---- 组合不重复的3位数 编程要求 给出四个不同的数字,能够组成多少个不重复的3位数,按照从小到大的顺
天寒雨落
2022/11/20
8600
【C/C++】之组合不重复的3位数
noip2013提高组_左归丸组方解析
只有一个需要注意的地方:给出的g和k不是右下角的坐标,右下角坐标应是(a+g,b+k)
全栈程序员站长
2022/09/29
2440
next_permutation(全排列算法)
 STL提供了两个用来计算排列组合关系的算法,分别是next_permutation和prev_permutation。首先我们必须了解什么是“下一个”排列组合,什么是“前一个”排列组合。考虑三个字符所组成的序列{a,b,c}。       这个序列有六个可能的排列组合:abc,acb,bac,bca,cab,cba。这些排列组合根据less-than操作符做字典顺序(lexicographical)的排序。也就是说,abc名列第一,因为每一个元素都小于其后的元素。acb是次一个排列组合,因为它是固定了a(
Angel_Kitty
2018/04/08
9760
next_permutation(全排列算法)
全排列(permutation)
显然,对于具有n个元素的集合R,R={r1,r2,r3…rn},其排列方式有n!种。 如:R = {1,2,3},其全排列如下: 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1
lexingsen
2022/02/24
5870
全排列(permutation)
hdu1069
#include <iostream> #include <algorithm> #include <cstring> using namespace std; class Data { public: int S, Height; int upl, uph; }; Data Da[100]; int n; int dp[100]; int cmp(const Data &a, const Data &b) /
@坤的
2018/06/04
7120
一个易于理解的C++全排列(permutation)实现
通常我们用这两条语句可以得到一个数组的全排列: sort(nums.begin(),nums.end()); //调用next_permutation求全排列的时候必须先给容器排序 do{ get_pirnt(nums) //这里是一个可以打印输出nums的函数 }while(next_permutation(nums.begin(),nums.end()); //调用该C++内置函数可以输出字典序大于当前nums的所有排列。 还可以自己写一个函数实现同样的功能,下面的函数使用递归,每次取出
kalifa_lau
2018/04/26
1.8K0
1833 深坑 TLE 求解
题目描述:  大家知道,给出正整数n,则1到n这n个数可以构成n!种排列,把这些排列按照从小到大的顺序(字典顺序)列出,如n=3时,列出1 2 3,1 3 2,2 1 3,2 3 1,3 1 2,3 2 1六个排列。  任务描述:  给出某个排列,求出这个排列的下k个排列,如果遇到最后一个排列,则下1排列为第1个排列,即排列1 2 3…n。  比如:n = 3,k=2 给出排列2 3 1,则它的下1个排列为3 1 2,下2个排列为3 2 1,因此答案为3 2 1。 
瑾诺学长
2018/09/21
3820
1833  深坑 TLE 求解
相关推荐
蓝桥杯之全排列函数 next_permutation()解析
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档