计算机复试学习笔记 Day44

130. 2n皇后问题问题描述给定一个n*n的棋盘棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后使任意的两个黑皇后都不在同一行、同一列或同一条对角线上任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法n小于等于8。说明同一条对角线是指包括两条主对角线的所有对角线n5时的棋盘从左上往右下有9条对角线从右上往左下也有9条对角线。比如棋盘为1 1 1 11 1 1 11 1 1 11 1 1 1表示一个4*4的棋盘所有位置都可放皇后。则可知有2种放法。输入说明输入的第一行为一个整数n表示棋盘的大小。接下来n行每行n个0或1的整数如果一个整数为1表示对应的位置可以放皇后如果一个整数为0表示对应的位置不可以放皇后。输出说明输出一个整数表示总共有多少种放法。个人总结思路使用回溯法(DFS)分别放置黑皇后(color0)和白皇后(color1)每个颜色各放置n个确保同色皇后不在同一行、列或对角线上。先从第0行开始放置黑皇后每行尝试所有可放置的列位置检查棋盘格子可用(bd[r][c]1)、列未用、两条对角线未用后标记状态并递归到下一行。放置完黑皇后所有行后切换到白皇后从第0行开始放置两个颜色都放置完时计数加一。对角线标记使用偏移数组Diag1用r-cnDiag2用rc确保覆盖所有可能对角线。棋盘位置在放置时临时设为0(不可用)回溯时恢复为1黑白皇后共享棋盘但各自有独立的列和对角线使用记录。易错点数组大小需开到20以覆盖n8的对角线范围(例如Diag1有2n-1条)开小如10会导致部分案例无法通过。必须为黑白两色分别维护独立的usedCol、usedDiag1、usedDiag2数组不能在切换颜色前清空记录否则回溯时第一个颜色状态丢失无法正确回退。set_state函数需正确处理放置(true:标记使用并设bd0)和恢复(false:取消标记并设bd1)避免棋盘状态混乱。DFS中rn时需区分颜色color0时切换到color1继续放置color1时才计数避免只放置一色就错误计数。知识点 - N皇后问题首先是了解一下 N 皇后问题到底是什么。这个题干讲得不清不楚的大概是觉得这是经典题大家都认识。很不巧我不认识。N 皇后问题是什么理解“N 皇后问题”的关键在于先搞清楚国际象棋中“皇后”这个棋子的攻击规则。简单来说N 皇后问题就是要把 N 个皇后放在一个 N×N 的棋盘上使得它们之间谁也打不到谁。以下是该题目的具体含义拆解1. 核心规则皇后怎么“打人”在国际象棋中皇后的攻击范围非常广它是最强的棋子。一个皇后可以攻击到和它处在同一行、同一列、或者同一对角线上的任何棋子。所以“N 皇后”的要求就是任意两个皇后都不能处于同一行、同一列或同一条对角线上。2. 题目的目标是什么题目会给你一个整数 N比如 N8 就是经典的八皇后问题。 你要在一个 N×N 的方格阵里摆放 N 个皇后满足上述规则。 通常题目会让你求总共有多少种摆法。或者输出所有具体的摆放方案用坐标或字符阵表示。3. 解题时的三个“翻译”当你看到这类题时可以把那个文字描述自动翻译成以下逻辑行约束每一行只能放一个皇后。由于总共有 N 行N 个皇后这意味着每行必须有且只有一个皇后。列约束每一列也只能放一个皇后。对角线约束容易卡壳的地方正对角线左上到右下这条线上所有点的行号 - 列号是个常数。反对角线右上到左下这条线上所有点的行号 列号是个常数。注在写程序时通常用数组来标记这些对角线是否已经被占用了。如何解题N皇后问题是理解回溯算法Backtracking最好的教材。掌握了它就能解决一大类“在约束条件下搜索所有可能性”的问题。1. 核心思路按行决策我们不需要在一个 N×N 的矩阵里胡乱尝试因为每一行必须且只能放一个皇后。动作从第 0 行开始依次决定每一行的皇后应该放在哪一列。约束放下的皇后不能与之前已放好的皇后在“同列”或“同对角线”同行不需要判断因为我们是一行行往下走的。回溯如果当前行所有位置都不能放说明上一行的位置选错了需要退回去重新选。2. 难点突破如何快速判断对角线冲突判断“同列”很简单用一个数组记下哪一列被占了即可。但“对角线”怎么办在 N×N 的网格中坐标为 (r,c)左上到右下的对角线主对角线在这条线上的点其row - col是一个定值。为了防止出现负数我们通常记为row - col n。右上到左下的对角线副对角线在这条线上的点其row col是一个定值。技巧我们开三个布尔数组col[],diag1[],diag2[]。每次放皇后时直接查这三个数组是否为true就能在 O(1)时间内判断是否合法。3. 标准 N 皇后代码模板这是一个标准的求 N×N 棋盘放入 N 个皇后所有方案的代码。#include iostream #include vector using namespace std; int n; int res 0; // 记录方案数 bool usedCol[20], usedDiag1[40], usedDiag2[40]; // 状态记录数组 // row 表示当前处理到第几行 (从0开始) void dfs(int row) { // 递归出口如果处理完了最后一行说明找到了一个合法解 if (row n) { res; return; } // 在当前行枚举每一列尝试放置 for (int c 0; c n; c) { // 关键检查约束 // 1. 列没被占用 2. 主对角线(r-cn)没被占用 3. 副对角线(rc)没被占用 if (!usedCol[c] !usedDiag1[row - c n] !usedDiag2[row c]) { // --- [做选择] --- usedCol[c] usedDiag1[row - c n] usedDiag2[row c] true; // --- [递归去下一行] --- dfs(row 1); // --- [撤销选择/回溯] --- // 这是回溯最核心的一步把状态改回原来的样子不影响同一行的后续尝试 usedCol[c] usedDiag1[row - c n] usedDiag2[row c] false; } } } int main() { cin n; dfs(0); cout res endl; return 0; }4. 为什么这个模板能通杀同类题回溯代码通途公式void dfs(层级/深度) { if (到达叶子节点) { 更新答案; return; } for (当前层的所有可选分叉) { if (满足约束条件) { 做标记; dfs(下一层); 撤销标记 (回溯); // 必须对称 } } }代码#include bits/stdc.h using namespace std; int n; bool usedCol[2][20], usedDiag1[2][20], usedDiag2[2][20]; int bd[10][10]; int res 0; void set_state(int r, int c, bool state, int color) { // 设置或恢复放下一枚棋子的状态 // state 为 true 时代表放下棋子为 false 时代表还原 usedCol[color][c] state; usedDiag1[color][r-cn] state; usedDiag2[color][rc] state; bd[r][c] (state) ? 0 : 1; } void dfs(int r, int color) { // 如果超过最后一行,说明找到一个放完全部单色皇后的解 // 如果只放了一个颜色就继续去放下一个。 // 如果两个颜色都放完解的数量加一 if (r n) { if (color 0) { dfs(0, 1); return; } else{ res; return; } } /* 判断本行放哪一个 条件 格子为 1 本列没有 两个对角线没有 */ for (int c 0; c n; c) { if (bd[r][c] !usedCol[color][c] !usedDiag1[color][r-cn] !usedDiag2[color][rc]) { // 找到一个可用位置标记并进入下一行 set_state(r, c, true, color); dfs(r1, color); // 结束后还原 set_state(r, c, false, color); } } return; } int main() { ios::sync_with_stdio(0); cin.tie(0); // 输入棋盘数据数组开得比较大多的位置已经被初始化为零了所以不影响 cin n; for (int i 0; i n; i) { for (int j 0; j n; j) { cin bd[i][j]; } } dfs(0,0); cout res \n; return 0; }131. 8皇后·改题目问题描述规则同8皇后问题但是棋盘上每格都有一个数字要求八皇后所在格子数字之和最大。输入说明一个8*8的棋盘。数据规模和约定棋盘上的数字范围0~99输出说明所能得到的最大数字和个人总结思路这一题比上一题还要简单直接套模板几乎都没什么要改的。代码#include bits/stdc.h using namespace std; int bd[8][8]; int max_sum 0; bool col[10], diag1[20], diag2[20]; void mark(int r, int c, bool state) { // 把状态更新和回退封装一下 col[c] state; diag1[r-c8] state; diag2[rc] state; } void dfs(int r, int pre_sum) { // 超过棋盘范围收尾并结束 if (r 8) { max_sum max(max_sum, pre_sum); return; } // 尝试每个可放置位置 for (int c 0; c 8; c) { if (!col[c] !diag1[r-c8] !diag2[rc]) { mark(r,c,true); int sum pre_sum bd[r][c]; dfs(r1, sum); mark(r,c,false); } } return; } int main() { ios::sync_with_stdio(0); cin.tie(0); for (int i 0; i 8; i) { for (int j 0; j 8; j) { cin bd[i][j]; } } dfs(0,0); cout max_sum \n; return 0; }132. 棋盘多项式题目问题描述八皇后问题是在棋盘上放皇后互相不攻击求方案。变换一下棋子还可以有八车问题八马问题八兵问题八王问题注意别念反。在这道题里棋子换成车同时棋盘也得换确切说是进行一些改造。比如现在有一张n*n的棋盘我们在一些格子上抠几个洞这些洞自然不能放棋子了会漏下去的。另外一个车本来能攻击和它的同行同列。现在你想想在攻击的过程中如果踩到一个洞便会自取灭亡。故车的攻击范围止于洞。此题给你棋盘的规模n以及挖洞情况求放k个车的方案数(k从0到最多可放车数)输入说明第一行一个整数n表示棋盘大小接下来n行每行n个用空格隔开的数字0或10的形状表示洞1表示没有洞数据规模和约定n8输出说明若干行第i行表示放i个车的方案数个人总结其实回头看这个代码写的不够好还有优化空间例如完全没必要循环 k 次而是直接在 dfs 过程中就可以把各个数量的结果增加了。就是但是写都写了就这样吧。思路代码采用DFS回溯方式枚举所有位置组合计算每种放置数量k的方案数。棋盘用bd数组记录0是洞不能放车1是可放空位放车时临时标记成2表示占用。can_put函数判断指定位置能否放车先排除洞然后沿列向上向下扫描如果遇到2就冲突遇到0就停止该方向搜索。next_pos函数定位下一个候选位置带jump参数放置车后用jumptrue会从当前位置后开始跳过同一行连续的1直到碰到0再切换非jump模式前进确保同一行被洞分隔的独立段落能分别尝试放置。dfs函数从当前r行c列出发目标放满k个车如果cnt已等于k就让res[k]加一返回否则用while循环遍历后续所有候选位置先尝试能放就放置并跳段落递归再回溯然后不放直接前进到下一个位置。主函数读入n和棋盘后用循环递增k调用dfs计算每k的方案直到出现0方案为止最后按顺序输出结果。易错点攻击范围被洞阻断所以冲突检查必须在遇到0时立即break不能继续穿过洞。同一行内被0分隔的段落可以独立放车next_pos的jump机制要正确处理跳过已放段落的1并在洞后继续否则会漏掉后续段落或重复计算。列方向只需检查上下连续段落因为行方向冲突已由搜索顺序和jump跳过处理无需额外左右扫描。代码#include bits/stdc.h using namespace std; int bd[10][10]; int n; int res[100]; int cnt 0; int pos[2]; bool can_put(int r, int c) { // 判断指定位置是否可以放下棋子 // 挖洞的位置不能放 if (bd[r][c] ! 1) return false; // 向上找 for (int i r - 1; i 0; i--) { // 碰到了其他棋子不能放 if (bd[i][c] 2) return false; // 遇到洞不用继续找了 if (bd[i][c] 0) break; } // 向下找 for (int i r 1; i n; i) { if (bd[i][c] 2) return false; if (bd[i][c] 0) break; } /* 由于 next_pos 中 jump 的存在现在同一行内会冲突的位置会被直接跳过 所以下面两段代码其实不需要了注释掉 // 向左找 for (int i c - 1; i 0; i--) { if (bd[r][i] 2) return false; if (bd[r][i] 0) break; } // 向右找 for (int i c 1; i n; i) { if (bd[r][i] 2) return false; if (bd[r][i] 0) break; } */ // 能放 return true; } void next_pos(int r, int c, bool jump) { // 找到下一个判断放棋子的位置 // 偷懒直接修改全局变量的 pos 就不用结构体传来传去了 // 小巧思之设置一个 jump 变量作为开关为 true 时会跳过同一行后面的 1 // 直接到达下一个可以放棋子的位置可以跳过一些判断 int x, y; // 首先向后走一格 if (c n - 1) { // 需要换行 x r 1; y 0; // 换行结束后不要再往后跳了 jump false; } else { // 不换行 x r; y c 1; } // 判断要不要往后跳 如果不用再继续了就更新坐标 if (jump bd[x][y] 1) { next_pos(x,y,true); } else if (jump bd[x][y] 0) { next_pos(x, y, false); } else { pos[0] x; pos[1] y; } return; } void dfs(int r, int c, int k) { if (cnt k) { // 已经放置了指定数量的棋子 res[k]; return; } if (r n) { // 走遍了所有行结束 return; } while (r n) { if (can_put(r,c)) { // 这个位置可以放 // 选择放 bd[r][c] 2; cnt; // 找到下一个位置并继续 next_pos(r, c, true); dfs(pos[0], pos[1], k); // 回退 bd[r][c] 1; cnt--; } // 切换到下一个位置 next_pos(r, c, false); r pos[0]; c pos[1]; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin n; for (int i 0; i n; i) { for (int j 0; j n; j) { cin bd[i][j]; } } // 循环记录每个 k 值的答案直到某个 k 值找不到方案 int k; do { dfs(0, 0, k); k; } while (res[k-1] ! 0); k--; for (int i 1; i k; i) { cout res[i] \n; } return 0; }计算机英语翻译练习TheTransformermodel is a neural network architecture based on the attention mechanism and has achieved great success in the field of natural language processing. Unlike traditionalrecurrentneural networks, Transformers do not rely on step-by-stepsequence processing. Instead, they useself-attention mechanismsto process the entire sequence simultaneously. This architecture not only improves the model’s ability to performparallel computationbut also enables it to capturelong-range dependenciesmore effectively. In machine translation tasks, the Transformer model can dynamically assign attention weights according to the relationships between different words in a sentence, thereby producing more accurate translations. In addition, Transformer architectures have been widely applied to tasks such as text generation, speech recognition, and even image processing. In recent years, most large-scalepre-trainedlanguage models have been built upon the Transformer architecture, which has significantly accelerated the development of artificial intelligence technologies.Transformer 模型是一种基于注意力机制的神经网络架构在自然语言处理领域取得了巨大成功。与传统的循环神经网络不同Transformer 不依赖于逐步的序列处理而是利用自注意力机制同时处理整个序列。这种架构不仅提升了模型的并行计算能力还使其能够更有效地捕捉长程依赖关系。在机器翻译任务中Transformer 模型可以根据句子中不同词语之间的关系动态分配注意力权重从而生成更准确的翻译。此外Transformer 架构已被广泛应用于文本生成、语音识别甚至图像处理等任务。近年来大多数大规模预训练语言模型都是基于 Transformer 架构构建的这显著加速了人工智能技术的发展。Reinforcement learningis a machine learning approach that learnsoptimal strategiesthrough interaction with the environment. In the reinforcement learning framework, an agent observes the state of the environment and takes corresponding actions in order to receive rewards or penalties. The goal of the agent is to find a policy that maximizes long-termcumulativerewards through continuous exploration and learning. Unlike supervised learning, reinforcement learning usually does not rely on large amounts of labeled data but improves decision-making ability through trial and error. Reinforcement learning has achieved success in many complex tasks such as robotic control, autonomous driving, and game artificial intelligence. In the famous Go program AlphaGo, reinforcement learning was combined with deep neural networks, enabling computers to reach or even surpass the level of top human players. However, in practical applications, reinforcement learning still faces challenges such aslow sample efficiencyand high training costs.强化学习是一种通过与环境交互来学习最优策略的机器学习方法。在强化学习框架中智能体观察环境状态并采取相应行动以获得奖励或惩罚。智能体的目标是通过不断的探索和学习找到一种能够使长期累积奖励最大化的策略。与监督学习不同强化学习通常不依赖大量的标注数据而是通过试错来提高决策能力。强化学习在机器人控制、自动驾驶和游戏人工智能等许多复杂任务中取得了成功。在著名的围棋程序 AlphaGo 中强化学习与深度神经网络相结合使计算机能够达到甚至超越人类顶尖选手的水平。然而在实际应用中强化学习仍面临样本效率低和训练成本高等挑战。背单词打卡