Gym 100781B Bell Ringing——构造

Gym 100781B Bell Ringing——构造

题意：对1~n的全排列排序，使得相邻两个排列中的数的位置变化不超过1

思路：递推构造，把i插入上一个排列的不同位置，得到上一个排列数*i种排列，具体可以跑一下我的程序看看输出

#include #include #include #include using namespace std;const int maxn = 5e4;int n, num[10], a[10][maxn][10];int main() { scanf("%d", &n); int num = 1; a[1][1][1] = 1; for (int i = 2; i <= n; i++) { for (int j = 1; j <= num; j++) { int pos = ((j & 1) ? i : 1), change = ((j & 1) ? -1 : 1); for (int k = 1; k <= i; k++) { int cnt = 0; for (int t = 1; t <= i; t++) { a[i][(j-1)*i+k][t] = (t == pos ? i : a[i-1][j][++cnt]); } pos += change; } } num *= i; } for (int i = 1; i <= num; i++) { printf("%d", a[n][i][1]); for (int j = 2; j <= n; j++) { printf(" %d", a[n][i][j]); } printf("\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。