从这里一键直达题目解析哦P1019 P1025 P1037 P1406P1019 [NOIP2000提高组] 单词接龙题目大意给定n nn个单词给定一个开头字母。规则接龙两个单词拼接后一个单词的前缀 前一个单词的后缀重合的部分只保留一份。例beastastonish→ 重叠ast拼接结果beastonish。每个单词最多使用2次。拼接重叠部分不能是一个单词完全包含另一个单词。比如at和atideat是atide的前缀属于包含关系不允许拼接。龙必须以指定开头字母作为第一个单词的首字母。求拼接出来的“龙”的最大总长度。数据范围n ≤ 20 n \le 20n≤20。样例5 at touch cheat choose tact a拼接at→tact→touch→choose总长度23。✨核心思路整体暴力DFS回溯直接传拼接后的完整字符串drag代表当前的龙pd(s1,s2)函数尝试把s2接在龙s1后面。找最大重叠长度i如果可以拼接返回拼接完成后的新字符串不能拼接返回字符串0作为标记。dfs(string drag)更新全局答案ans用当前龙的长度更新最大长度。循环枚举全部单词imark[i]2该单词已经用满2次跳过。调用pd(drag,ss[i])判断能不能把ss[i]接在当前龙后面。如果s ! 0代表可以接龙mark[i]标记使用次数1递归dfs(s)传入拼接好的新龙回溯mark[i]--撤销使用标记。main入口遍历所有单词首字母等于开头字符c的单词作为龙的起点。mark[i]1调用dfs(ss[i])跑完回溯。最后输出ans即最长龙的长度。#includebits/stdc.h using namespace std; #define int long long #define endl \n #define pii pairint,int #define fi first #define se second const int N101; string ss[25]; int n, mark[25] {0}, ans 0; //【判断两字符串能否首尾相连】 string pd(string s1,string s2){ int n1s1.size(),n2s2.size(); int nummin(n1,n2); for(int i1;inum;i){ if(s1.substr(n1-i,i)s2.substr(0,i)) return s1.substr(0,n1-i)s2; } return 0; } //【更新字符串长度寻找与新字符串首尾相连的字符串】 void dfs(string drag){ if(drag.size()ans) ansdrag.size(); for(int i0;in;i){ if(mark[i]2) continue; string spd(drag,ss[i]); if(s!0){ mark[i]; dfs(s); mark[i]--; } } } void slove(){ char c; cinn; for(int i0;in;i){ cinss[i]; } cinc; for(int i0;in;i){ if(ss[i][0]c){ mark[i]1; dfs(ss[i]); mark[i]--; } } coutansendl; } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _1; //cin_; while(_--) slove(); return 0; }cP1406 方格填数 - 洛谷P1406 方格填数题意给定n ( 1 ≤ n ≤ 4 ) n(1\le n\le4)n(1≤n≤4)再给n × n n\times nn×n个整数把全部数字填入n × n n\times nn×n方格。要求每行、每列、两条主对角线上数字和全部相等。输出字典序最小的填法把矩阵每行顺次连起来整体字典序最小同时输出目标和S SS。保证至少存在一组解。样例输入3 1 2 3 4 5 6 7 8 9样例输出15 2 7 6 9 5 1 4 3 8核心思路计算目标和S所有数字总和记为total一共有n nn行每行和相等S t o t a l n S\frac{total}{n}Sntotal​每一行、每一列、两条对角线的和都必须等于S SS。字典序最小的技巧把输入数字从小到大排序DFS按从小到大优先选数。搜到第一个合法完整矩阵直接输出这就是字典序最小答案。DFS填格子按顺序( 0 , 0 ) → ( 0 , 1 ) … ( 0 , n − 1 ) → ( 1 , 0 ) … (0,0)\to(0,1)\dots(0,n-1)\to(1,0)\dots(0,0)→(0,1)…(0,n−1)→(1,0)…逐个填数vis[]标记数字是否已经被使用每个数字只能用一次。✂剪枝填完一整行立刻判断该行总和是否等于S SS不等于直接回溯。填完最后一行的某一列此时该列已经填满判断列总和是否等于S SS不满足回溯。矩阵全部填满后校验两条对角线和是否等于S SS满足就是答案。n最大为4总格子最多16个排序DFS剪枝完全可以通过。模拟当前状态pos0填1pos1填2现在来到pos2也就是第一行第三个格子(0,2)。第一行[1, 2, ?]n3y2是本行最后一列。//pos2尝试填入数字3vis[i]true;mp[0][2]3;//y n‑1校验行和summp[0][0]mp[0][1]mp[0][2]1236不等于S15→ okfalseif(ok)dfs(pos1);// ok是false**dfs(3)不会执行不会进入pos3~8**vis[i]false;//❗撤销pos2位置填的数字3if(found)return;//for循环i继续增加尝试pos2填别的数字4,5,6...9情况pos2的for循环全部i全部跑完pos2的for循环把剩下所有可用数字全部试一遍不管pos2填3、4、5、6、7、8、9第一行永远是12x12x 15 → x12但我们最大数字只有9没有任何数字可以满足行和等于15。所以每一次okfalse每一次都不会调用dfs(3)。pos2的for(i)全部循环结束退出pos2这一层dfs函数。执行return回到调用pos2的地方pos1层。回到pos1层代码片段//pos1刚才选的是数字2if(ok)dfs(2);// dfs(2)完整跑完全部分支失败返回到这里vis[i]false;//❗❗撤销pos1位置填的数字2if(found)return;//for ipos1尝试下一个数字这里vis[i]false就把pos1(0,1)位置的数字2的标记撤销数字2重新变为可用。pos1的for继续i尝试填别的数字3,4,5…。假设pos1所有数字全部试完全部走不通pos1的for循环结束return回到pos0层pos0层if(ok)dfs(1);//pos1全部搜索完毕返回vis[i]false;//❗撤销pos0(0,0)填的数字1数字1释放变回可用if(found)return;//for ipos0尝试下一个数字也就是数字2左上角换成2#includebits/stdc.husingnamespacestd;#defineintlonglongintn;inta[20];boolvis[20];intmp[5][5];intS;boolfound;//pos当前要填第pos个格子pos从0~n*n-1voiddfs(intpos){if(found)return;intxpos/n;intypos%n;if(posn*n){//全部填完校验两条对角线intd10,d20;for(inti0;in;i){d1mp[i][i];d2mp[i][n-1-i];}if(d1Sd2S){//输出答案coutSendl;for(inti0;in;i){for(intj0;jn;j){if(j0)cout ;coutmp[i][j];}coutendl;}foundtrue;}return;}//枚举选哪个数从小到大保证字典序最小for(inti0;in*n;i){if(!vis[i]){vis[i]true;mp[x][y]a[i];booloktrue;//剪枝当前这一行填满了校验行和if(yn-1){intsum0;for(intj0;jn;j)summp[x][j];if(sum!S)okfalse;}//剪枝如果是最后一行该列填满校验列和if(xn-1ok){intsum0;for(intirow0;irown;irow)summp[irow][y];if(sum!S)okfalse;}if(ok){dfs(pos1);}vis[i]false;if(found)return;}}}signedmain(){cinn;inttotal0;for(inti0;in*n;i){cina[i];totala[i];}sort(a,an*n);//从小到大排序优先选小数保证字典序最小Stotal/n;foundfalse;memset(vis,0,sizeofvis);dfs(0);return0;}[P1025 NOIP 2001 提高组] 数的划分 - 洛谷P1025 数的划分 NOIP2001提高组题目大意给定整数 (n,k)(6\le n\le2002\le k\le6)把n nn分成k kk个非空整数部分。不考虑顺序1 1 5和1 5 1视为同一种方案(6\le n\le2002\le k\le6)只算1次。求总共有多少种不同划分方案。样例(n7,k3)输出4四种分法{1,1,5}、{1,2,4}、{1,3,3}、{2,2,3}核心思路DFS回溯版本核心难点直接暴力枚举会产生大量重复方案同一组数字不同排列。去重手段强制划分出来的数满足非递减a 1 ≤ a 2 ≤ a 3 ⋯ ≤ a k a_1 \le a_2 \le a_3 \dots \le a_ka1​≤a2​≤a3​⋯≤ak​。只搜不下降序列(6\le n\le2002\le k\le6)就不会生成1 5 1这类乱序重复组合。dfs参数设计dfs(pos, last, sum)pos已经分出多少份last下一份数字必须大于等于last(6\le n\le2002\le k\le6)保证非递减(6\le n\le2002\le k\le6)去重sum已经累加的总和递归终止pos k已经分出k份。如果sum n(6\le n\le2002\le k\le6)方案数1直接返回。循环for(int i last; i n\(i\(j‑1\)1\)sum; i)i从last开始(6\le n\le2002\le k\le6)保证不下降。✅重要剪枝if(sumi*(k-pos)n)break;模拟样例 n7k3函数dfs(pos, last, sum)pos已经分好多少份last下一份数字必须 ≥ last保证不下降去重sum已经累加的总和初始调用dfs(0,1,0)ans0需要选出3个数a 1 ≤ a 2 ≤ a 3 a_1\le a_2 \le a_3a1​≤a2​≤a3​a 1 a 2 a 3 7 a_1a_2a_37a1​a2​a3​7dfs(0, 1, 0)pos0还需要分3份last1sum0循环 i 从 1开始sum i*(k‑pos) 0i*3 ≤7i1sumi*(3‑0) 1*33 ≤7可以进入调用dfs(1, 1, 011)dfs(1,1,1)pos1已经分1份还剩2份last1sum1i从1开始sum i*(2) ≤7i11 1*23 ≤7调用dfs(2,1,112)dfs(2,1,2)pos2已经分2份还剩1份last1sum2i从1开始还剩1份这一份就是最后一份要求sum i 7 → i5i1sum13≠7i2sum24≠7i3sum35≠7i4sum46≠7i5sum57调用dfs(3,5,257)dfs(3,5,7)一步步看 i1i2i3i4发生了什么pos2sum2还剩1份。i1sum i*(1)213 ≤7不触发break。调用dfs(3, 1, sumi3)。进入dfs(3,1,3)pos k(3)判断sum 73≠7不计数直接return回到dfs(2,1,2)的for循环。✅只是进入dfs但是不满足sumnans不会增加。return回来for继续i。i2调用dfs(3,2, 4)pos3sum4≠7returni。i3调用dfs(3,3,5)pos3sum5≠7returni。i4调用dfs(3,4,6)pos3sum6≠7returni。i5调用dfs(3,5,7)pos3sum7 7ansreturn。i6n‑sum5循环条件i5i6不会进来。pos k3sum7ans 1→ans1方案1,1,5return。#includebits/stdc.h using namespace std; int n,k,ans; //pos已经分了pos份last下一个数≥lastsum当前总和 void dfs(int pos,int last,int sum) { if(pos k) { if(sum n) ans; return; } for(int i last; i n - sum;i) { //剪枝后面剩下每份最少i总和超n直接不用继续 if(sum i*(k-pos) n) break; dfs(pos1,i,sumi); } } int main() { cinnk; ans0; dfs(0,1,0); //0份第一个数最小取1总和0 coutansendl; return 0; }