资源限制
时间限制：1.0s内存限制：256.0MB
问题描述
给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
例如:
3 1 2 4
4 3 6
7 9
16
现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。
输入格式
第1行为两个正整数n，sum
输出格式
一个1～N的一个排列
样例输入
【蓝桥杯算法训练|蓝桥杯算法训练 数字游戏 C语言实现】4 16
样例输出
3 1 2 4
数据规模和约定
0
蓝桥杯算法训练 数字游戏 组合数和暴力两种解法_王宇哲的博客-CSDN博客_蓝桥杯组合数
文章图片
https://blog.csdn.net/qq_30347475/article/details/122841196?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164603069716780265461488%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164603069716780265461488&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-8-122841196.pc_search_result_control_group&utm_term=%E8%93%9D%E6%A1%A5%E6%9D%AF+%E7%AE%97%E6%B3%95%E8%AE%AD%E7%BB%83+%E6%95%B0%E5%AD%97%E6%B8%B8%E6%88%8FC%E8%AF%AD%E8%A8%80%E3%80%80%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA1%EF%BD%9EN%E7%9A%84%E6%8E%92%E5%88%97a%5Bi%5D%EF%BC%8C%E6%AF%8F%E6%AC%A1%E5%B0%86%E7%9B%B8%E9%82%BB%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%9B%B8%E5%8A%A0%EF%BC%8C%E5%BE%97%E5%88%B0%E6%96%B0%E5%BA%8F%E5%88%97%EF%BC%8C%E5%86%8D%E5%AF%B9%E6%96%B0%E5%BA%8F%E5%88%97%E9%87%8D%E5%A4%8D%E8%BF%99%E6%A0%B7%E7%9A%84%E6%93%8D%E4%BD%9C%EF%BC%8C%E6%98%BE%E7%84%B6%E6%AF%8F%E6%AC%A1%E5%BE%97%E5%88%B0%E7%9A%84%E5%BA%8F%E5%88%97%E9%83%BD%E6%AF%94%E4%B8%8A%E4%B8%80%E6%AC%A1%E7%9A%84%E5%BA%8F%E5%88%97%E9%95%BF%E5%BA%A6%E5%B0%911%EF%BC%8C%E6%9C%80%E7%BB%88%E5%8F%AA%E5%89%A9%E4%B8%80%E4%B8%AA%E6%95%B0%E5%AD%97%E3%80%82&spm=1018.2226.3001.4187
#include
#define N 10
int n, sum;
int hasFounded = 0;
int book[N + 2];
int nums[N + 2];
int C[N + 1][N + 1];
void dfs(int depth);
int main() {
int i, j, depth = 1;
scanf_s("%d %d", &n, &sum);
//0的情况要特判，从0个数中取出0个数只有一种取法
for (i = 0;
i <= n;
i++) {
C[0][i] = C[i][i] = 1;
}
for (i = 2;
i <= n;
i++) {
for (j = 1;
j < i;
j++) {
C[j][i] = C[j - 1][i - 1] + C[j][i - 1];
}
}dfs(1);
return 0;
}void dfs(int depth) {
int i, currentSum;
//如果已经找到了排列，就不运行了
if (hasFounded) {
return;
}//如果已经枚举到了最后一位，就开始判断排列是否满足条件
if (depth == n + 1) {currentSum = 0;
for (i = 1;
i <= n;
i++) {
currentSum += C[i - 1][n - 1] * nums[i];
}//如果满足条件直接输出
if (currentSum == sum) {
for (i = 1;
i <= n;
i++) {
printf("%d ", nums[i]);
}//标记找到
hasFounded = 1;
}
return;
}for (i = 1;
i <= n;
i++) {
//该点未被访问而且排列尚未找到，就继续运行
if (!book[i] && !hasFounded) {//深搜模板
book[i] = 1;
nums[depth] = i;
dfs(depth + 1);
book[i] = 0;
}
}}
推荐阅读
- 每日刷题———蓝桥杯真题|蓝桥杯2018第九届C语言B组省赛总决赛习题题解——习题A.换零钞（暴力枚举法）
- 蓝桥杯|蓝桥杯——算法训练——进击的青蛙
- java|java 蓝桥杯 输出组合_Java蓝桥杯——排列组合
- 蓝桥杯|Java蓝桥杯——杨辉三角
- 蓝桥杯|蓝桥杯——JAVA大学C组——回文素数
- 笔记|第十二届蓝桥杯——Java软件开发（省赛）（括号序列（笔记15））
- java|Java蓝桥杯——九宫幻方
- 蓝桥杯-Java|第八届蓝桥杯大赛个人赛省赛（软件类）真题-Java语言B组
- CS241可视化分析