关键词：
题目描述
总时间限制: 5000ms 内存限制: 65536kB
描述
题目描述：
大家知道，给出正整数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。
输入
第一行是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n( 1 <= n < 1024 )和k(1<=k<=64)，第二行有n个正整数，是1，2 … n的一个排列。
输出
对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。
样例输入
3
3 1
2 3 1
3 1
3 2 1
10 2
1 2 3 4 5 6 7 8 9 10
样例输出
3 1 2
1 2 3
1 2 3 4 5 6 7 9 8 10
来源
qinlu@POJ
解题分析
问题可以转化为求一个排列的下一个排列，在stl中有现成的算法 next_permulation()，在这里我们考虑自己实现一下next_permulation。
因为一个数集的全排列需要按照字典序升序排列，这就要求两个相邻的排列之间前缀尽可能重合度高，那么可以采用这种策略：
1.从最后一个数xn开始向左查找，一直找到某个位置j，使 x[j] > x[j-1]，这么做的原因是，在x[j..n]是降序排列，那么在这段子序列是它全排列中最大的。
2.从x[j..n]中寻找比x[j-1]大的数 a，要刚刚好大，然后x[j-1]与这个数交换，因为a是第一个比x[j-1]大的数，所以交换后x[j..n]仍然保持降序
3.最后将x[j..n] reverse一下就可以
解题代码
#include <cstdio>
#include <algorithm>
using namespace std;
int a[1025];
void next_permutation(int length)
int j = length - 1;
while(j > 0 && a[j - 1] > a[j])
j -- ;
if(j == 0)
for(int i = 0; i < length; i++)
a[i] = i + 1;
return;
int i;
for( i = length - 1; i >= j; i--)
if(a[i] > a[j - 1])
int temp = a[i];
a[i] = a[j - 1];
a[j - 1] = temp;
break;
i = length - 1;
while(j < i)
int temp = a[i];
a[i] = a[j];
a[j] = temp;
j++; i--;
int main()
int t;
scanf("%d", &t);
int n, k;
while(t--)
memset(a, 0, sizeof(a));
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++)
scanf("%d", a + i);
for(int i = 0; i < k; i++)
next_permutation(n);
for(int i = 0; i < n - 1; i++)
printf("%d ", a[i]);
printf("%d
", a[n - 1]);
return 0;
bailian1835poj1835宇航员模拟(代码片段)
宇航员TimeLimit:2000MSMemoryLimit:30000KTotalSubmissions:8900Accepted:3629Description问题描述： 宇航员在太空中迷失了方向，在他的起始位置现在建立一个虚拟xyz坐标系，称为绝对坐标系，宇航员正面的方向为x轴正方向，... 查看详情
poj1833生成排列
题目链接：POJ1833/*************************************author:GrantYuan*time:2014/10/1916:38*source:POJ1833*algorithm:STL+排列的生成*************************************/#include<iostream>#include<algo 查看详情
bailian4118开餐馆dp(代码片段)
4118:开餐馆总时间限制:1000ms内存限制:65536kB描述北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这n个地点排列在同一条直线上。我们用一个整数序列m1,m... 查看详情
poj1833排列stl/next_permutation
...bsp;大家知道，给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出123，132，213，231，312，321六个排列。 任务描述： 给出某个排列，求出这个排列的下k个排... 查看详情
bailian2746约瑟夫问题(代码片段)
...即最后猴王的编号样例输入621248300样例输出517问题链接：Bailian2746约瑟夫问题问题简述：（略）问题分析：????约瑟夫问题有２种解法，一是模拟法，二是数学法。????数学法需要数学推导，这里略去推导过程，只给出程序。????模... 查看详情
bzoj1833数字计数(代码片段)
题目链接找$[1$~$a-1]$和$[1$~$b]$中各数码出现的次数之后相减就是答案上代码：/**************************************************************Problem:1833User:zhangheranLanguage:C++Result:AcceptedTime:0msMemory:1292kb*************** 查看详情
错误代码1833cannotchangecolumnusedinaforeign(代码片段)
最近修改mysql数据库表中的字段长度时报错，执行更改的sql语句：ALTERTABLEserver_listMODIFYCOLUMNserver_lipCHAR(25);报错信息：1queriesexecuted,0success,1errors,0warnings查询：altertableserver_listmodifycolumnserver_lipchar(25)错误代码：1833Can 查看详情
bzoj1833数位dp(代码片段)
很裸的数位dp。#include<bits/stdc++.h>#defineLLlonglong#definefifirst#definesesecond#definemkmake_pair#definePIIpair<int,int>#definey1skldjfskldjg#definey2skldfjsklejgusingnamespacestd;constintN= 查看详情
441.排列硬币模拟(代码片段)
https://leetcode-cn.com/problems/arranging-coins/classSolutionpublic:intarrangeCoins(intn)intcnt=0,i=1;while(n>=i)cnt++,n-=i,i++;returncnt;; 查看详情
bailian2975caesarcryptogram(代码片段)
2975:CaesarCryptogram描述JuliusCaesarinventesacryptogramthatconvertsastringtoanotherstring.Theruleisthateveryletterinanoriginalstringshouldbereplacedbytheletterwhichtakesthefifthplaceafteritinthealphabe 查看详情
codeforcesgoodbye2017b.newyearandbuggybot枚举全排列模拟(代码片段)
B.NewYearandBuggyBottimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputBobprogrammedarobottonavigatethrougha2dmaze.Themazehassomeobstacles.Emptycellsaredenotedb 查看详情
bzoj1833数字计数(代码片段)
题目大意：给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次思路：不知道黄学长他们的dp都是怎么dp的搞神的方法太强啦%%%数位乱搞。。推了公式，然后每一位直接套用公式每一位分3种情况小于该... 查看详情
bailian2796bailian3681数字求和序列处理(代码片段)
2796:数字求和总时间限制:3000ms内存限制:65536kB描述给定一个正整数a，以及另外的5个正整数，问题是：这5个整数中，小于a的整数的和是多少？输入输入一行，只包括6个小于100的正整数，其中第一个正整... 查看详情
bailian2819w的密码密码+模拟(代码片段)
2819:W的密码总时间限制:1000ms内存限制:65536kB描述加密一条信息需要三个整数码,k1,k2和k3。字符[a-i]组成一组,[j-r]是第二组,其它所有字符([s-z]和下划线)组成第三组。在信息中属于每组的字符将被循环地向左移动ki个位置。每组中的... 查看详情
动态规划：熟练度练习（poj1458最佳加法表达式bailian2755poj3624bailian1088）(代码片段)
最长公共子序列Language:DefaultCommonSubsequenceTimeLimit:1000MSMemoryLimit:10000KTotalSubmissions:47599Accepted:19562DescriptionAsubsequenceofagivensequenceisthegivensequencewithsomeelements(possiblenone)lef 查看详情
[入门组模拟赛]幸运数与排列(代码片段)
题目描述一个数是幸运数当且仅当这个数仅由4和7构成，比如47,744,4747。 在1到n的全排列中字典序第k小的排列中，有多少个幸运数在排列中的位置编号也是幸运数。输入一行两个整数n,k。输出一个整数表示答案。如... 查看详情
数位dpbzoj1833:[zjoi2010]count数字计数(代码片段)
数位dp姿势一直很差啊；顺便庆祝一下1ADescription给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。Input输入文件中仅包含一行两个整数a、b，含义如上所述。Output输出文件中包含一行10个整数，分别... 查看详情
1833:[zjoi2010]count数字计数(代码片段)
题意：给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。 经历一中午，终于TM做出来了满满的成就。。。以f[i][j][k]代表长度为i最高位为j数码k出现几次 修正：1、预处理 若最高位j==k还... 查看详情