【HDU 1027】全排列 | 逆康托展开 | std::next_permutation | 栈 + 回溯搜索 | N
【HDU 1027】Ignatius and the Princess II
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11263 Accepted Submission(s): 6484
URL
【HDU 1027】Ignatius and the Princess II
Problem Description
输入 n 和 k,输出 n 的全排列中字典序第 k 小者
逆康托展开,或者std::next_permutation,或者自写 next_permutation,或者用 栈 + 回溯搜索(容易超时)
Input
输入到EOF。每次输入 n k (1<= n <=1000, 1<= k <=10000) 保证 k 合法(存在字典序第 k 小的排列)
Output
每组输入输出一行,是 n 个数的全排列中字典序第 k 小的排列。行末不能有空格否则 PE
Sample Input
6 4
11 8
Sample Output
1 2 3 5 6 4
1 2 3 4 5 6 7 9 8 11 10
Analysis & AC code
方法① std::next_permutation :
既然是全排列,那么自然想到的就是 std::next_permutation。本题当然也可以这样水过:
#include <cstdio>
#include <algorithm>
#define sc(x) {register char _c=getchar(),_v=1;for(x=0;_c<48||_c>57;_c=getchar())if(_c==45)_v=-1;for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=getchar());x*=_v;}
#define se(x) {register char _c=getchar(),_v=1;for(x=0;_c<48||_c>57;_c=getchar())if(_c==45)_v=-1;else if(_c==-1)return 0;for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=getchar());x*=_v;}
#define PC putchar
void PRT(const int a){if(a>=10)PRT(a/10);putchar(a%10+48);}
int main()
{
int n, k, num[1005];
while (1)
{
se(n)sc(k)
for(int i=0; i<n; i++)
num[i] = i+1;
while (--k) // 进行 k-1 次
std::next_permutation(num, num+n); // 变序算法std::next_permutation
for (int i=0; i<n-1; i++)
PRT(num[i]), PC(32);
PRT(num[n-1]), PC(10);
}
}
方法② 自写 next_permutation :
稍微不那么水的解法,自己实现一个 next_permutation。不过还是属于懒人的暴力解法:
#include <cstdio>
#define sc(x) {register char _c=getchar(),_v=1;for(x=0;_c<48||_c>57;_c=getchar())if(_c==45)_v=-1;for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=getchar());x*=_v;}
#define se(x) {register char _c=getchar(),_v=1;for(x=0;_c<48||_c>57;_c=getchar())if(_c==45)_v=-1;else if(_c==-1)return 0;for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=getchar());x*=_v;}
#define PC putchar
void PRT(const int a){if(a>=10)PRT(a/10);putchar(a%10+48);}
template <typename E>
bool next_permutation(E *begin, E *end)
{
E *now = end-1, *prev = now-1, tp;
while (now > begin && *prev >= *now) // <时退出,找第一个相邻顺序对,记下prev
--now, --prev;
if (now <= begin)
return false; // 找不到,说明整体是递减的,不存在下一个排列,返回false
for (now = end-1; *now <= *prev; now--); // >时退出,从后往前找第一个大于(也是数值最小的)*prev的元素
tp = *now, *now = *prev, *prev = tp; // 然后把它和*prev交换
for (++prev, --end; prev<end; prev++,end--) // 翻转后面这部分
tp = *end, *end = *prev, *prev = tp;
return true;
}
int main()
{
int n, k, num[1005];
while (1)
{
se(n)sc(k)
for(int i=0; i<n; i++)
num[i] = i+1;
while (--k) // 进行 k-1 次
next_permutation(num, num+n); // 自己实现next_permutation
for (int i=0; i<n-1; i++)
PRT(num[i]), PC(32);
PRT(num[n-1]), PC(10);
}
}
方法③ 【正统】 逆康托展开 :
这道题的官方解法应该是逆康托展开。乍一看题,n <= 1000,似乎没法求,因为阶乘最大(用 LL)也就表示到 20 ...
然鹅再仔细一看,k <= 10000,这连8的阶乘都没超过,所以这道题稍微转化一下就可以求解。
也就是说当 n 很大的时候,由于 k <= 8!,所以实际上只有末尾 8 位数(或者更少)的顺序发生改变,前面都是原封不动
所以当 n > 8 的时候,只要记录一下 n-8 的值,然后先原封不动地输出前 n-8个数,然后再求逆康托,逆康托结果加上n-8再输出就行了
代码如下:
#include <cstdio>
#define sc(x) {register char _c=getchar(),_v=1;for(x=0;_c<48||_c>57;_c=getchar())if(_c==45)_v=-1;for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=getchar());x*=_v;}
#define se(x) {register char _c=getchar(),_v=1;for(x=0;_c<48||_c>57;_c=getchar())if(_c==45)_v=-1;else if(_c==-1)return 0;for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=getchar());x*=_v;}
#define PC putchar
void PRT(const int a){if(a>=10)PRT(a/10);putchar(a%10+48);}
void antiCantor(int n, int k, int *output)
{
static const int FAC[12+1] = {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600};
int i, j, t, vis[13]={0};
--k;
for (i=0; i<n; i++)
{
t = k / FAC[n-i-1];
for (j=1; j<=n; j++)
{
if (!vis[j])
{
if (!t) break;
--t;
}
}
output[i] = j;
vis[j] = 1;
k %= FAC[n-i-1];
}
}
int main()
{
int output[123];
int n, k, base;
while(1)
{
se(n)sc(k)
base = 0;
if (n > 8)
{
base = n-8;
n = 8;
}
antiCantor(n, k, output);
if (base) // 输入的 n>8,但是 k<8! 所以只用求1-8的第k小排列就够了
{
for (int i=1; i<=base; i++) // 输出的时候先原封不动地输出1到base
PRT(i), PC(32);
for (int i=0; i<n-1; i++) // 再输出逆康托展开的结果(记得加上base)
PRT(base + output[i]), PC(32);
PRT(base + output[n-1]), PC(10);
}
else
{
for (int i=0; i<n-1; i++)
PRT(output[i]), PC(32);
PRT(output[n-1]), PC(10);
}
}
}
方法④ 栈 + 回溯搜索 :
这里还是想冒着 TLE 的风险强行用一下这个解法。
嗯嗯,这种解法就是最美的,不接受任何反驳。
#include <cstdio>
#include <cstring>
#define sc(x) {register char _c=getchar(),_v=1;for(x=0;_c<48||_c>57;_c=getchar())if(_c==45)_v=-1;for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=getchar());x*=_v;}
#define se(x) {register char _c=getchar(),_v=1;for(x=0;_c<48||_c>57;_c=getchar())if(_c==45)_v=-1;else if(_c==-1)return 0;for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=getchar());x*=_v;}
#define PC putchar
void PRT(const int a){if(a>=10)PRT(a/10);putchar(a%10+48);}
constexpr int MN(1234);
int n, m, cnt;
int stack[MN], top;
bool used[MN], printed;
void generPermutation()
{
if (top == n) // 到达叶节点
{
++cnt; // 计数器++
if (cnt == m) // 得到第k小排列,输出
{
for (int i=0; i<top-1; i++)
PRT(stack[i]), PC(32);
PRT(stack[top-1]), PC(10);
printed = true;
return;
}
}
for (int i=1; i<=n; ++i)
{
if (!used[i])
{
used[i] = true;
stack[top++] = i;
generPermutation(); // 继续搜索
if (printed)
return;
--top; // 回溯
used[i] = false; // 回溯
}
}
}
int main()
{
while (1)
{
se(n)sc(m)
memset(used, false, (n+1) * sizeof(*used));
cnt = top = 0;
printed = false;
generPermutation();
}
}
加油!
上一篇: DOS 强行杀进程的命令