棋盘多项式-进阶题17

棋盘多项式题目问题描述求出区间[a,b]中所有整数的质因数分解。输入说明输入两个整数ab。2ab10000输出说明每行输出一个数的分解形如ka1a2a3…(a1a2a3…k也是从小到大的)(具体可看范例)输入范例3 10输出范例33 42*2 55 62*3 77 82*2*2 93*3 102*5解题思路本题思路是利用 深度优先搜索DFS 回溯 来枚举在棋盘上放置车的所有合法方案并统计不同车数量对应的方案数。由于棋盘大小为 n×nn≤8可以按照 从左到右、从上到下逐格搜索 的方式进行枚举。对于每一个格子有两种选择不放车 或 放车。在尝试放车之前需要先判断该位置是否合法首先该位置必须不是洞值为 1其次需要检查该格子在 同一行和同一列方向上是否存在可以攻击到的车。检查时如果在搜索过程中遇到洞值为 0则说明攻击路径被阻断不再继续向该方向检查若在未遇到洞之前发现已有车则说明当前位置不能放车。若该位置合法则在此处放置车标记当前状态并递归搜索下一个格子同时记录当前放置车的数量当搜索到所有格子都处理完时说明得到了一种完整方案此时根据当前放置车的数量更新对应的方案计数。递归结束后需要进行回溯撤销当前格子的放车状态继续尝试其他可能情况。通过这种方式枚举所有合法摆放情况最终即可得到放置 k 个车k1,2,…的所有方案数。整体代码#includeiostream#includevectorusingnamespacestd;intn;vectorvectorintboard;// 棋盘0表示洞1表示可放vectorvectorboolhasChess;// 标记哪些位置放了车vectorintresult;// result[k]表示放k个车的方案数// 检查位置(x,y)能否放车boolcanPlace(intx,inty){if(board[x][y]0)returnfalse;// 洞不能放// 检查同一行左边for(intjy-1;j0;j--){if(board[x][j]0)break;// 遇到洞阻断攻击if(hasChess[x][j])returnfalse;// 遇到车}// 检查同一行右边for(intjy1;jn;j){if(board[x][j]0)break;if(hasChess[x][j])returnfalse;}// 检查同一列上边for(intix-1;i0;i--){if(board[i][y]0)break;if(hasChess[i][y])returnfalse;}// 检查同一列下边for(intix1;in;i){if(board[i][y]0)break;if(hasChess[i][y])returnfalse;}returntrue;}// DFS搜索当前处理到第idx个格子已经放了cnt个车voiddfs(intidx,intcnt){if(idxn*n){result[cnt];return;}intxidx/n;// 当前行intyidx%n;// 当前列// 不在此格放车dfs(idx1,cnt);// 尝试在此格放车if(canPlace(x,y)){hasChess[x][y]true;dfs(idx1,cnt1);hasChess[x][y]false;// 回溯}}intmain(){cinn;board.resize(n,vectorint(n));hasChess.resize(n,vectorbool(n,false));for(inti0;in;i){for(intj0;jn;j){cinboard[i][j];}}// 最多能放n*n个车但实际受洞的限制result.resize(n*n1,0);dfs(0,0);// 输出结果从1个车到最多可放车数for(intk1;kn*n;k){if(result[k]0){coutresult[k]endl;}else{break;}}return0;}注意事项注意必须回溯。英文段落翻译自己翻译多模态学习是人工智能中的一个重要的研究方向它旨在使得模型能够同时处理不同类型的数据例如文本图像和语音。在现实世界中人们通过多感官或者信息所以来自一个单独的模态的数据通常不能完全的表现出复杂的情况。多模态学习集合了来自不同模态的信息使得模型可以获得一个更全面的理解。例如图像描述任务中模型必须理解视觉内容并且生产相应的文本描述。随着深度学习技术的发展多模态模型已经在例如视觉问题回答交叉模态检索和智能助手等领域取得了极大的进步。单词打卡下一篇待续