一、递归分治2题第1题棋盘覆盖题目名称棋盘覆盖分治递归问题描述给定一个棋盘尺寸 $2^k \times 2^k$ $1 \leq k \leq 6$棋盘上有一个特殊方格坐标给定。请用 L 型骨牌覆盖整个棋盘特殊方格不覆盖输出最终的棋盘覆盖方案用数字表示每个骨牌编号同一骨牌覆盖的三个格子用同一个正整数编号特殊方格填-1。输入格式第一行整数 k第二行两个整数 sx, sy 表示特殊方格坐标0 ≤ sx, sy 2^k输出格式$2^k$ 行每行 $2^k$ 个整数表示覆盖后的棋盘每个数占 3 位宽度右对齐。样例输入2 0 1样例输出示意不唯一2 -1 3 3 2 2 1 3 4 1 1 5 4 4 5 5推荐解法分治递归填充四个子棋盘。第2题合并排序题目名称分治法合并排序问题描述给定一个长度为 N1 ≤ N ≤ 10^5的整数数组请使用分治合并排序递归算法按从小到大排序并输出排序后的数组。不得使用内置排序函数。输入格式第一行整数 N第二行N 个整数可能是未排序的输出格式一行N 个整数按从小到大排列数与数之间用一个空格隔开。样例输入5 3 1 4 1 5样例输出1 1 3 4 5#includebits/stdc.h using namespace std; const int N1e510; int a[N]; int main(){ int n; cinn; for(int i1;in;i){ cina[i]; } int t; for(int i1;in;i){ for(int j1;jn-i;j){ if(a[j]a[j1]){ ta[j]; a[j]a[j1]; a[j1]t; } } } for(int i1;in;i){ couta[i] ; } return 0; }注意每次递归划分需打印当前 merge 后数组可选附加分二、动态规划2题第3题矩阵连乘题目名称矩阵连乘最少计算次数问题描述给定 n 个矩阵的尺寸 $p_0, p_1, \dots, p_n$其中矩阵 $A_i$ 大小为 $p_{i-1} \times p_i$请使用动态规划求出这些矩阵连乘所需的最少数乘次数并输出加括号的方案如(A1(A2A3))。输入格式第一行整数 n (1 ≤ n ≤ 100)第二行n1 个整数 $p_0, p_1, ..., p_n$输出格式第一行最少乘法次数第二行最优加括号方案用括号表示样例输入3 10 100 5 50样例输出7500 (A1(A2A3))第4题最长公共子序列题目名称最长公共子序列 (LCS)问题描述给定两个字符串 X 和 Y长度均 ≤ 1000求它们的最长公共子序列的长度并输出该子序列本身若存在多个输出序号最小的一个即从左到右第一个找到的。输入格式第一行字符串 X第二行字符串 Y输出格式第一行最长公共子序列长度第二行该最长公共子序列若无输出空行样例输入ABCBDAB BDCAB样例输出4 BCABC提示建议使用string类型和二维vector。三、贪心算法2题第5题活动安排题目名称活动选择问题问题描述设有 n 个活动1 ≤ n ≤ 10^4每个活动给出起始时间 $s_i$ 和结束时间 $f_i$。请用贪心算法按结束时间最早策略选出最大数量的互不相容活动并输出所选活动的序号原始顺序。输入格式第一行整数 n接下来 n 行每行两个整数 s_i f_i s_i f_i输出格式第一行最大活动数量第二行所选活动的序号升序排列用空格分隔样例输入5 1 3 2 5 3 6 5 7 6 8样例输出3 1 3 5#includebits/stdc.h using namespace std; const int N1e45; struct node{ int start; int end; int idx; }a[N]; bool cmp(node x,node y){ return x.endy.end; } int main(){ int n; cinn; for(int i1;in;i){ cina[i].starta[i].end; a[i].idxi; } sort(a1,an1,cmp); int last_end-1; int cnt0; int b[N];//用于存储选中的活动时间 int b_cnt0; for(int i1;in;i){ if(a[i].startlast_end){ b[b_cnt]a[i].idx; last_enda[i].end; cnt; } } coutcntendl; for(int i0;ib_cnt;i){ coutb[i]; if(ib_cnt-1)cout ; } return 0; }第6题哈夫曼编码题目名称哈夫曼树与编码问题描述给定字符集大小写字母或数字及其频率请构建哈夫曼树并输出每个字符的哈夫曼编码假设左分支为 0右分支为 1。若有相同频率按字符 ASCII 码小的优先合并。输入格式第一行整数 n2 ≤ n ≤ 26接下来 n 行每行一个字符 c 和一个整数 f频率输出格式n 行每行输出 字符:编码按字符升序排列样例输入5 a 5 b 9 c 12 d 13 e 16样例输出a:011 b:10 c:00 d:01 e:11四、回溯法2题第7题N皇后题目名称N皇后问题解的个数问题描述给定整数 n1 ≤ n ≤ 15求解 n 皇后问题有多少种不同的合法摆放方案任何两个皇后不在同一行、列、对角线。使用回溯法求解。输入格式一个整数 n输出格式一个整数表示解的个数样例输入4样例输出2提示可用位运算优化bitset 或整数位标记第8题0-1背包-回溯法题目名称0-1背包问题回溯搜索最优解问题描述给定 n 个物品每个物品有重量 w_i 和价值 v_i背包容积为 C。找到最优装载方案的最大总价值。注n ≤ 30C ≤ 10000输入格式第一行两个整数 n 和 C第二行n 个整数 w_1 ... w_n第三行n 个整数 v_1 ... v_n输出格式一个整数最大总价值样例输入4 7 2 3 4 5 3 4 5 6样例输出9#includebits/stdc.h using namespace std; const int N1e45; const int M30; int dp[M][N]; int a[N],b[N]; int main(){ int n,c; cinnc; for(int i1;in;i){ cina[i]; cinb[i]; } for(int i0;in;i){ dp[i][0]0; } for(int j0;jc;j){ dp[0][j]0; } for(int i1;in;i){ for(int j1;jc;j){ if(a[i]j){ dp[i][j]dp[i-1][j]; } else{ dp[i][j]max(dp[i-1][j],dp[i-1][j-a[i]]b[i]); } } } coutdp[n][c]endl; return 0; }五、分支限界法1题第9题单源最短路径题目名称分支限界法求单源最短路径问题描述给定带权有向图 G顶点数 n ≤ 1000边数 m ≤ 10000权重非负源点编号为 0。请用计算从源点到所有其他顶点的最短路径长度。输入格式第一行两个整数 n m接下来 m 行每行三个整数 u v w表示 u→v 的有向边权 w最后一行源点编号 s默认 0输出格式一行n 个整数dist[0] ... dist[n-1]从 s 出发到各点距离不可达输出 -1样例输入5 8 0 1 10 0 2 5 1 2 2 1 3 1 2 1 3 2 3 9 2 4 2 3 4 4样例输出0 8 5 9 7六、综合1题第10题双船装载 回溯题目名称双船装载可行性判断问题描述有 n 个集装箱1 ≤ n ≤ 20需装到两艘载重分别为 c1 和 c2 的轮船上第 i 个集装箱重量 w_i。试用回溯法判断是否存在一种装载方案将所有集装箱装完并输出其中一艘船的装载方案船1。输入格式第一行三个整数 n c1 c2第二行n 个整数 w_1 ... w_n 所有重量之和 ≤ c1c2输出格式第一行YES 或 NO若 YES第二行输出船1所装集装箱的序号1-based升序用空格分隔样例输入5 10 10 4 3 5 2 6样例输出YES 1 2 4