本文分享的必刷题目是从蓝桥云课、洛谷、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 N4N4时可能是这样的31244367916在FJ背后奶牛们开始玩一个更难的游戏她们试图从最终的总和和数字N NN中确定起始序列。不幸的是这个游戏有点超出了FJ的心算能力。编写一个程序来帮助FJ玩这个游戏并跟上奶牛们的步伐。【输入】共一行两个正整数n , s u m n,sumn,sum。【输出】输出包括一行为字典序最小的那个答案。当无解的时候请什么也不输出。【输入样例】4 16【输出样例】3 1 2 4【核心思想】问题分析给定N NN和s u m sumsum需要找到一个1 11到N NN的排列使得按照相邻数字逐层相加规则类似杨辉三角的逐层求和最终得到的数字等于s u m sumsum。例如N 4 N4N4时排列( 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]单调递增的特性进行提前剪枝。算法选择DFS全排列枚举用book数组标记已使用的数字递归生成1 11到N NN的所有排列逐层求和验证calc()函数模拟题目描述的相邻相加过程计算最终值前缀剪枝在calc()中若某层求和后b [ 1 ] s u m b[1] sumb[1]sum立即返回− 1 -1−1避免无效搜索关键步骤DFS搜索当前步数s t e p stepstep剪枝验证调用calc()计算当前部分排列的逐层和若返回− 1 -1−1已超s u m sumsum则直接返回终止条件若s t e p N step NstepN且calc() sum输出当前排列并结束程序枚举尝试遍历i ii从1 11到N NN若b o o k [ i ] 0 book[i] 0book[i]0a [ s t e p ] i a[step] ia[step]ib o o k [ i ] 1 book[i] 1book[i]1递归d f s ( s t e p 1 ) dfs(step1)dfs(step1)回溯a [ s t e p ] 0 a[step] 0a[step]0b 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[j1]b[j]c[j]c[j1]每轮若b [ 1 ] s u m b[1] sumb[1]sum返回− 1 -1−1将b bb拷贝回c cc继续下一轮返回最终c [ 1 ] c[1]c[1]时间/空间复杂度时间复杂度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)排列数组、标记数组及临时数组DFS剪枝的核心思想杨辉三角系数最终和 ∑ i 1 N a i × C ( N − 1 , i − 1 ) \sum_{i1}^{N} a_i \times C(N-1, i-1)∑i1N​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-一维【代码详解】#includebits/stdc.husingnamespacestd;intn,sum,a[15],b[15],c[15],book[15];intcalc()// 按照游戏规则计算{for(inti1;in;i){// 将a数组拷贝至c数组c[i]a[i];}for(inti1;in;i){// 依次遍历c数组中所有数for(intj1;jn;j){// 相邻两个数相加并赋值给b数组b[j]c[j]c[j1];}if(b[1]sum){// 如果计算后b[1]已经大于sum则无需继续计算返回-1return-1;}for(intj1;jn;j){// 将b数组拷贝至c数组进行下一轮计算c[j]b[j];}}returnc[1];// 返回c数组第1个元素的值}voiddfs(intstep){inttmpcalc();// 剪枝每次都计算一下if(tmp-1)return;// 如果c[1]已经超过sum后面就不用算了if(stepn){// 搜索退出条件if(tmpsum){// 如果等于sumfor(inti1;in;i){// 则输出a数组couta[i] ;}coutendl;exit(0);// 并退出程序}return;// 如果不等于即小于还要继续搜索}for(inti1;in;i){// 全排列模板if(book[i]0){// 如果某个数没有被用过a[step]i;// 就用这个数book[i]1;// 并标记用过dfs(step1);// 进行下一次搜索a[step]0;// 还原现场book[i]0;}}}intmain(){cinnsum;// 输入n和sumdfs(1);// 进行dfs深搜return0;}【运行结果】4 16 3 1 2 4