题目描述
Time limit: 1000 ms
Memory limit: 256 MB
Standard I/O
对于给定的n，n的一个排列可以构成一种“求和金字塔”。如，n = 4时，排列（3，1，2，4）的金字塔：
3 1 2 4
4 3 6
7 9
16
即，上一层两两相邻的数值求和，构成下一层的每个数；不断进行，直到只剩一个数s。
现在，给定n和s，请你反推出原始的排列（解必定存在）。如果这样的排列有多个， 请你输出字典序最小的排列 。
【警告】不允许使用 std::next_permutation 等自动生成排列的库函数！
输入描述
输入只有一行，两个由一个空格隔开的正整数n和s，含义如题目描述所示。
输出描述
输出只有一行，为n个由空格隔开的正整数，代表原始的n的排列。多解的，输出字典序最小的那个。
【提示】
排列的字典序，如同我们一般按顺序输出排列的顺序一样。比如对于3的全排列，字典序从小到大依次为：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
“1 2 3 4 5 6 7 8 9 10” 是 n=10 时的最小字典序排列。
样例输入
10 2196
样例输出
1 6 9 4 2 3 5 10 7 8
样例解释
【数据范围】
对于100% 的数据，n≤10。
对于金字塔型数据,可以建立顶点与最底层的关系,而不需要考虑中间的过程.这一设想的基本根据是杨辉三角.我们知道,杨辉三角中的任意一个值由最顶层的值"分裂"而来.那么如果我们将整个过程"倒过来",就变成了上述的逆金字塔.
无论是正金字塔还是逆金字塔,都可以依据杨辉三角进行变换.特别地,对于逆金字塔,我们考虑第一层左数第二位(也就是1):
3 1 2 4
4 3 6
7 9
16
这个数字向第二层"传递"了两次.也就是说,它"分裂"了两次.这是不是很像杨辉三角?事实上我们可以补出一个三角形:
左侧多出来的一部分就是1"分裂"的结果.如果我们不考虑系数,把所有的数字全部视作1,那么整个金字塔就变成了多个杨辉三角的重叠.然后再基于底层乘上相应的系数,取中间的重叠部分就是答案.
故对于顶点而言,相当于解以下方程组:
的正整数解.对于这样的不定方程,可以通过特解-通解的手段给出一个解析解.不过我们不在此讨论如此深奥的数学问题,我们通过枚举来解这个方程,
对于上面的不定方程可以运用线性代数中的线性非齐次方程组解法来做.
另外,本题中将解限定为1-n中的不重复正整数,这就相当于给出1-n的全排列.
考虑到题目中要求输出最小字典序的结果,故可以使用std::next_permutation给出排列.本人在这里使用的是C语言,故没有这种便利,只好自己写了一个实现.具体代码如下:
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define SWAP(a,b) int tmp;tmp=a;a=b;b=tmp
/********************************
function:reverse the whole array
parameter:
start:the beginning of array
len:the len of array you want to reverse
no return value
*********************************/
void reverse(int* start, int len) {
int i;
for (i = 0; i < len / 2; i++) {
SWAP(*(start + i), *(start + len - 1 - i));
}
}
/***************************************
function:give a new permutation with higher dict-order
parameter:
per:the head pointer of whole array
total:the number of entries
return value:if there is a satisfied permutation,return true;
or return false.
****************************************/
bool Permutation(int* per, int total) {
int i;
for (i = total - 1; i > 0; i--) {
if (per[i] > per[i - 1]) {
i--;
break;
}
}
if (i == -1) {
return false;// no new permutations
}
int k;
for (k = total - 1; k > i; k--) {
if (per[k] > per[i]) {
break;
}
}
SWAP(per[k], per[i]);
reverse(per + i + 1, total - i - 1);
return true;
}
/************************************
function:calculate a combination.
parameter:
select:the number of elements which are chosen
total:the number of elements in a set
return value:the result
*************************************/
int Combination(int select, int total) {
int i;
int Allfac = 1, fac1 = 1, fac2 = 1;
if (select == 0) {
return 1;
}
for (i = 1; i <= total; i++) {
Allfac *= i;
}
for (i = 1; i <= select; i++) {
fac1 *= i;
}
for (i = 1; i <= total - select; i++) {
fac2 *= i;
}
return Allfac / (fac1 * fac2);
}
int main(void) {
int n, sum;
int com[10];
while (scanf("%d%d", &n, &sum) == 2) {
int i;
if (n == (n / 2) * 2) {
for (i = 0; i < n / 2; i++) {
com[i] = Combination(i, n - 1);
}
int* Per = (int*)malloc(n * sizeof(int));
for (i = 0; i < n; i++) {
Per[i] = i + 1;
}
do {
int judge=0, j;
for (j = 0; j < n / 2; j++) {
judge += com[j] * (Per[j] + Per[n - 1 - j]);
}
if (judge == sum) {
for (i = 0; i < n; i++) {
printf("%d ", Per[i]);
}
break;
}
} while (Permutation(Per, n));
free(Per);
}
else {
for (i = 0; i < n / 2 + 1; i++) {
com[i] = Combination(i, n - 1);
}
int* Per = (int*)malloc(n * sizeof(int));
for (i = 0; i < n; i++) {
Per[i] = i + 1;
}
do {
int judge = com[n / 2] * Per[n / 2];
int j;
for (j = 0; j < n / 2; j++) {
judge += com[j] * (Per[j] + Per[n - 1 - j]);
}
if (judge == sum) {
for (i = 0; i < n; i++) {
printf("%d ", Per[i]);
}
break;
}
} while (Permutation(Per, n));
free(Per);
}
}
return 0;
}
注:C语言中并没有bool型变量,这是在C++编译环境下的"四不像"语言.若有不当之处,还望各位指出.
网友评论