P1088 [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

5
3
1 2 3 4 5

样例输出 #1

1 2 4 5 3

提示

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

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

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

noip2004 普及组第 4 题

思路

思路1

参考大佬题解，很巧妙。

思路2

参考大佬题解，也很巧妙，具体见下面代码注释。

思路3

直接调用库函数next_permutation()。

ChatGPT：

next_permutation() 是C++标准库 <algorithm> 中提供的一个函数，用于生成给定序列的字典序下一个排列。如果当前排列已经是字典序的最后一个排列，则将序列重新排列为最小的排列（即升序排列）。

函数原型

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

• first：指向序列的起始位置的迭代器。
• last：指向序列的末尾的迭代器。

返回值

• true：如果成功生成了下一个排列。
• false：如果已经到达字典序的最后一个排列，并且序列被重排为字典序的最小排列（升序排列）。

用法示例

以下是一个使用next_permutation()的简单示例：

#include <iostream>
#include <algorithm>
#include <vector>int main() {std::vector<int> vec = {1, 2, 3};// 使用next_permutation生成并打印所有排列do {for (int num : vec) {std::cout << num << " ";}std::cout << std::endl;} while (std::next_permutation(vec.begin(), vec.end()));return 0;
}

输出结果

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

工作原理

next_permutation()的工作原理是基于字典序排列算法。假设我们有一个升序排列的序列，函数会生成序列的下一个排列，遵循以下步骤：

1. 从后向前查找第一个相邻的升序对 (i, j)，使得a[i] < a[j]。

   • 这一步确定了从序列末尾开始向前找到的最长递减子序列。如果找不到这样的升序对，说明序列已经是字典序的最大排列。

2. 从后向前查找第一个元素k，使得a[i] < a[k]。

   • 这是为了找到一个比a[i]大的最小元素a[k]。

3. 交换a[i]和a[k]。

4. 反转j之后的所有元素（即使其从递减顺序变为递增顺序）。

   • 反转操作是为了将序列调整为刚好大于当前序列的下一个排列。

注意事项

• next_permutation() 函数要求序列的元素可以随机访问，并且可以通过<运算符进行比较，因此它适用于std::vector，std::string，数组等容器。
• 为了生成所有可能的排列，初始序列必须以升序排列。

典型应用

• 生成组合：通过递增的方式生成所有的排列组合。
• 全排列问题：解决数学中的排列问题或寻找字典序的下一个排列。
• 算法竞赛：常用在解答需要对所有可能的排列进行暴力求解的问题。

总结

next_permutation()是一个非常实用的工具函数，特别适合在生成所有排列、解决组合问题时使用。它的复杂度为O(n)，其中n是序列的长度，因此在实际应用中具有很高的效率。

代码

思路1

见上方思路链接。

思路2

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define endl '\n'
using namespace std;const int N = 10010;int n, m;
int a[N];
int step, flag;// flag 首先用于表示是否找到了要被加的那个排列数，找到之后用于表示已经加了几次
vector<int> path;
bool used[N];// 由于这里是加够 m 次就算找到了一个可行解，要立即返回，因此返回值不是void
bool dfs() {if (path.size() == n) {// 找到了要被加的那个排列数flag++;if (flag == m + 1) {// 还没往目标数去加的时候 flag 就是 1 了，所以是 == m + 1for (int x : path) {cout << x << " ";}cout << endl;return true;}return false;}for (int i = 1; i <= n; i++) {// 这个if相当于在一开始强行制定定在搜索树中往a[]中的元素走// 相当于剪枝// 比如1 2 4 5 3，到第三层的时候就不会先往123走，直接走4if (flag == 0) {i = a[++step];}// 下面还是一样要模拟回溯过程if (used[i] != true) {used[i] = true;path.push_back(i);if (dfs()) {return true;}used[i] = false;path.pop_back();}}return false;// 注意这里千万不能漏了！要保证每一个dfs的分支都要有返回值！
}int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}dfs();return 0;
}

思路3

#include<iostream>
#include<algorithm>// next_permutation()函数在<algorithm>头文件中
#include<cstring>
#include<vector>
#define endl '\n'
using namespace std;const int N = 10010;int n, m;
int a[N];int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}// 直接调用 next_permutation() 来生成下一个全排列for (int i = 1; i <= m; i++) {next_permutation(a + 1, a + 1 + n);}for (int i = 1; i <= n; i++) {cout << a[i] << " ";}cout << endl;return 0;
}