题意:给定一个n和m,然后你会有一个序列,里面有n个元素,且这n个元素是1到n的。按照题中树塔的形状,给出了最后的值m,问初始序列是怎样的。如果有多个答案输出字典序最小的。且没有说如果没有答案输出啥,那就默认这个肯定有解。

解法:首先我算了算最上层每个值对m的贡献,发现这是一个杨辉三角。所以先预处理一下得到一个杨辉三角,然后直接枚举上面n个数字,n最大为10,最大运算量也就10!=3e6,所以这是完全没有压力的。

代码如下:

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int num[15][15];
int n, m, a[15];

bool Check() {
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		ans += num[n][i] * a[i];
	}
	if(ans == m)
		return 1;
	return 0;
}

int main() {
	num[1][1] = 1;
	for(int i = 2; i <= 10; i++) {
		for(int j = 1; j < i; j++) {
			num[i][j] = num[i - 1][j - 1] + num[i - 1][j];			
		}
		num[i][i] = 1;
	}
	
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		a[i] = i;
	if(Check()) {
		for(int i = 1; i <= n; i++) {
			printf("%d%c", a[i], i == n ? '\n' : ' ');
		}
	} else {
		while(next_permutation(a + 1, a + n + 1)) {
			if(Check())
				break;
		}
		for(int i = 1; i <= n; i++) {
			printf("%d%c", a[i], i == n ? '\n' : ' ');
		}
	}
	
	return 0;
}


Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐