P1088 [NOIP2004 普及组] 火星人

题目链接：

[NOIP2004 普及组] 火星人 - 洛谷

---

题目描述

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为$1,2,3,\cdots$。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为$1,2,3,4$和$5$，当它们按正常顺序排列时，形成了$5$位数$12345$，当你交换无名指和小指的位置时，会形成$5$位数$12354$，当你把五个手指的顺序完全颠倒时，会形成$54321$，在所有能够形成的$120$个$5$位数中，$12345$最小，它表示$1$；$12354$第二小，它表示$2$；$54321$最大，它表示$120$。下表展示了只有$3$根手指时能够形成的$6$个$3$位数和它们代表的数字：

三进制数	代表的数字
$123$	$1$
$132$	$2$
$213$	$3$
$231$	$4$
$312$	$5$
$321$	$6$

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入格式

共三行。

第一行一个正整数$N$，表示火星人手指的数目（$1 \le N \le 10000$）。

第二行是一个正整数$M$，表示要加上去的小整数（$1 \le M \le 100$）。

下一行是$1$到$N$这$N$个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出格式

$N$个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

样例 #1

样例输入 #1

text

5
3
1 2 3 4 5

样例输出 #1

text

1 2 4 5 3

提示

对于$30\%$的数据，$N \le 15$。

对于$60\%$的数据，$N \le 50$。

对于$100\%$的数据，$N \le 10000$。

noip2004 普及组第 4 题

---

题解

在讲这道题之前，我们先来看一道模板题：https://www.luogu.com.cn/problem/P1706

简单来说，就是给出1到n的全排列。我们直接用DFS解决，上代码。

#include <bits/stdc++.h>
using namespace std;
int a[20] = {0};
int b[20] = {0};       // 用于判断当前数字是否被使用过
void dfs(int n, int k) // k表示层数
{
    if (k == n + 1)
    {
        for (int i = 1; i <= n; i++)
        {
            printf("%5d", a[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (b[i] == 0)
        {
            a[k] = i;
            b[i] = 1;
            dfs(n, k + 1);
            b[i] = 0;
        }
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    dfs(n, 1);
    return 0;
}

做完这道题，我们再来我们要讲的这道题P1088 [NOIP2004 普及组] 火星人

题目链接：https://www.luogu.com.cn/problem/P1088

简单来说，就是找到某一个排列后面的第m个排列。

用样的，我们仍然可以用DFS的方法来解决。不过这题的n到了10000，显然，光靠DFS无法完成，问需要对齐进行剪枝来优化代码，减小时间。仔细想一下，火星人给出的排列之前的排列和我们的目标排列之后的排列全是没有用的，将这部分简化可以节省很多时间。话不多说，结合代码理解。

#include <bits/stdc++.h>
using namespace std;
int a[10005] = {0};
int b[10005] = {0}; // 用于判断当前数字是否被使用过
int c[10005] = {0}; // 用于储存火星人的手指序号
int m;
bool flag = false;
void dfs(int n, int k) // k表示层数
{
    if (m < 0)
        return;
    if (k == n + 1)
    {
        flag = true;
        m--;
        if (m == 0)
        {
            for (int i = 1; i <= n; i++)
            {
                printf("%d ", a[i]);
            }
            m--;
        }
        return;
    }
    for (int i = 1; i <= n && m >= 0; i++)
    {
        if (b[i] == 0)
        {
            a[k] = i;
            if (a[k] == c[k] || flag == true) // 前半句条件用于剪枝，后半句用于m的运算
            {
                b[i] = 1;
                dfs(n, k + 1);
                b[i] = 0;
            }
        }
    }
}
int main()
{
    int n;
    scanf(" %d", &n);
    scanf(" %d", &m);
    for (int i = 1; i <= n; i++)
    {
        scanf(" %d", &c[i]);
    }
    m++;
    dfs(n, 1);
    return 0;
}

下面我们来介绍另外一个方法，有请主角登场！

$$next _ permutation$$

这个函数每运行一次就可以排列出下一个全排列的序列，用法是next_permutation（数组开头，数组结尾）。是不是很简单，直接上代码。

#include <bits/stdc++.h>
using namespace std;
int a[10005] = {0};
int main()
{
    int n, m;
    scanf(" %d", &n);
    scanf(" %d", &m);
    for (int i = 1; i <= n; i++)
    {
        scanf(" %d", &a[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        next_permutation(a + 1, a + n + 1);
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

<algorithm> 中有许多好用的函数，多背背还是有很多好处的。