企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P1118 [USACO06FEB] Backward Digit Sums G/S - 洛谷

【题目描述】

FJ和他的奶牛们喜欢玩一个心算游戏。他们将数字从1 11到N ( 1 ≤ N ≤ 12 ) N(1 \le N \le 12)N(1≤N≤12)按某种顺序写下来，然后将相邻的数字相加，得到一个数字更少的新列表。他们重复这个过程，直到只剩下一个数字。例如，游戏的一种情况（当N = 4 N=4N=4时）可能是这样的：

31244367916

在FJ背后，奶牛们开始玩一个更难的游戏，她们试图从最终的总和和数字N NN中确定起始序列。不幸的是，这个游戏有点超出了FJ的心算能力。

编写一个程序来帮助FJ玩这个游戏，并跟上奶牛们的步伐。

【输入】

共一行两个正整数n , s u m n,sumn,sum。

【输出】

输出包括一行，为字典序最小的那个答案。

当无解的时候，请什么也不输出。

【输入样例】

4 16

【输出样例】

3 1 2 4

【核心思想】

1. 问题分析：给定N NN和s u m sumsum，需要找到一个1 11到N NN的排列，使得按照"相邻数字逐层相加"规则（类似杨辉三角的逐层求和）最终得到的数字等于s u m sumsum。例如N = 4 N=4N=4时，排列( 3 , 1 , 2 , 4 ) (3,1,2,4)(3,1,2,4)的逐层求和过程为：

   3 1 2 4 4 3 6 7 9 16

   这是一个DFS全排列搜索 + 剪枝优化问题，关键在于利用逐层求和过程中b [ 1 ] b[1]b[1]单调递增的特性进行提前剪枝。

2. 算法选择：

   • DFS全排列枚举：用book数组标记已使用的数字，递归生成1 11到N NN的所有排列
   • 逐层求和验证：calc()函数模拟题目描述的相邻相加过程，计算最终值
   • 前缀剪枝：在calc()中，若某层求和后b [ 1 ] > s u m b[1] > sumb[1]>sum，立即返回− 1 -1−1，避免无效搜索

3. 关键步骤：

   • DFS搜索（当前步数s t e p stepstep）：
     • 剪枝验证：调用calc()计算当前部分排列的逐层和，若返回− 1 -1−1（已超s u m sumsum）则直接返回
     • 终止条件：若s t e p > N step > Nstep>N且calc() == sum，输出当前排列并结束程序
     • 枚举尝试：遍历i ii从1 11到N NN，若b o o k [ i ] = 0 book[i] = 0book[i]=0：
       • a [ s t e p ] = i a[step] = ia[step]=i，b o o k [ i ] = 1 book[i] = 1book[i]=1
       • 递归d f s ( s t e p + 1 ) dfs(step+1)dfs(step+1)
       • 回溯：a [ s t e p ] = 0 a[step] = 0a[step]=0，b o o k [ i ] = 0 book[i] = 0book[i]=0
   • 逐层求和计算（calc()）：
     • 将a aa拷贝到c cc
     • 进行N − 1 N-1N−1轮相邻相加：b [ j ] = c [ j ] + c [ j + 1 ] b[j] = c[j] + c[j+1]b[j]=c[j]+c[j+1]
     • 每轮若b [ 1 ] > s u m b[1] > sumb[1]>sum返回− 1 -1−1
     • 将b bb拷贝回c cc继续下一轮
     • 返回最终c [ 1 ] c[1]c[1]

4. 时间/空间复杂度：

   • 时间复杂度：O ( N ! ⋅ N 2 ) O(N! \cdot N^2)O(N!⋅N2)，最坏枚举N ! N!N!个排列，每个排列验证O ( N 2 ) O(N^2)O(N2)
   • 空间复杂度：O ( N ) O(N)O(N)，排列数组、标记数组及临时数组

5. DFS剪枝的核心思想：

   • 杨辉三角系数：最终和= ∑ i = 1 N a i × C ( N − 1 , i − 1 ) = \sum_{i=1}^{N} a_i \times C(N-1, i-1)=∑i=1N​ai​×C(N−1,i−1)，即每个位置i ii的贡献系数为组合数。但代码采用直接模拟，更直观
   • 前缀单调性剪枝：逐层求和过程中，b [ 1 ] b[1]b[1]是a aa中前若干元素的加权和，随着排列增长单调不减（对于正数），一旦超过s u m sumsum可立即剪枝
   • 字典序最小保证：DFS按1 11到N NN的顺序枚举，首次找到的合法解即为字典序最小解
   • 全排列模板：标准的book标记 + 回溯框架，适用于N ≤ 12 N \le 12N≤12的小规模排列搜索
   • 适用于"排列约束满足 + 可验证目标值"类问题，核心是利用目标函数的单调性进行有效剪枝

【解题思路】

【算法标签】

#普及 #DFS-一维

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn,sum,a[15],b[15],c[15],book[15];intcalc()// 按照游戏规则计算{for(inti=1;i<=n;i++){// 将a数组拷贝至c数组c[i]=a[i];}for(inti=1;i<n;i++){// 依次遍历c数组中所有数for(intj=1;j<n;j++){// 相邻两个数相加，并赋值给b数组b[j]=c[j]+c[j+1];}if(b[1]>sum){// 如果计算后b[1]已经大于sum，则无需继续计算，返回-1return-1;}for(intj=1;j<=n;j++){// 将b数组拷贝至c数组，进行下一轮计算c[j]=b[j];}}returnc[1];// 返回c数组第1个元素的值}voiddfs(intstep){inttmp=calc();// 剪枝，每次都计算一下if(tmp==-1)return;// 如果c[1]已经超过sum，后面就不用算了if(step>n){// 搜索退出条件if(tmp==sum){// 如果等于sumfor(inti=1;i<=n;i++){// 则输出a数组cout<<a[i]<<" ";}cout<<endl;exit(0);// 并退出程序}return;// 如果不等于，即小于，还要继续搜索}for(inti=1;i<=n;i++){// 全排列模板if(book[i]==0){// 如果某个数没有被用过a[step]=i;// 就用这个数book[i]=1;// 并标记用过dfs(step+1);// 进行下一次搜索a[step]=0;// 还原现场book[i]=0;}}}intmain(){cin>>n>>sum;// 输入n和sumdfs(1);// 进行dfs深搜return0;}

【运行结果】

4 16 3 1 2 4