如何在vs做网站,wordpress注册评论,创意网络广告,北京app设计公司一、上机打卡 1.1 2n皇后问题 1.1.1 题目 给定一个n*n的棋盘#xff0c;棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后#xff0c;使任意的两个黑皇后都不在同一行、同一列或同一条对角线上#xff0c;任意的两个白皇后都不在同一行、同一列或同一…一、上机打卡1.1 2n皇后问题1.1.1 题目给定一个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表示对应的位置不可以放皇后。输出一个整数表示总共有多少种放法。输入范例41 0 1 11 1 1 11 1 1 11 1 1 1输出范例01.1.2 总结本题需要在n×n的棋盘上同时放置黑白两种颜色的皇后且两者均需满足不同行、不同列、不同对角线的约束同时还要避开棋盘上标记为0的障碍位置。由于n≤8可以采用深度优先搜索DFS的回溯方法求解。基本思路是先放置所有黑皇后再放置所有白皇后因为黑白皇后之间除了共享棋盘障碍外并无直接冲突因此可以分两个阶段进行搜索。具体实现时首先用三个布尔数组分别记录黑皇后放置时每一列、主对角线行-列偏移量统一加n避免负数和副对角线行列是否已被占用在成功放置完所有黑皇后后再清空这些标记并用同样的方式搜索白皇后的放置方案但此时要额外确保白皇后不能落在黑皇后已占用的位置上因此需要在第二阶段同时检查该位置是否已被黑皇后占据。搜索过程按行递归每一行尝试所有可能的列如果该位置可放棋盘值为1且无障碍且行列对角线均未被占用则放置皇后并递归下一行直到所有行处理完毕则计数加一。1.1.3 代码#include iostream #include vector using namespace std; int n; // 棋盘大小 vectorvectorint board; // 棋盘1表示可放0表示不可放 int total 0; // 总方案数 // 记录黑皇后放置的位置用于后续白皇后放置时的位置冲突检查 vectorpairint, int blackPos; // 列、主对角线、副对角线的占用标记 // 主对角线row - col n - 1 范围 [0, 2n-2] // 副对角线row col 范围 [0, 2n-2] bool colBlack[8] {false}; bool diag1Black[15] {false}; // 主对角线 bool diag2Black[15] {false}; // 副对角线 bool colWhite[8] {false}; bool diag1White[15] {false}; bool diag2White[15] {false}; // 第二阶段放置白皇后 void dfsWhite(int row) { if (row n) { // 成功放置所有白皇后 total; return; } for (int col 0; col n; col) { // 检查该位置是否可放棋盘允许、没有被黑皇后占用、行列对角线无冲突 if (board[row][col] 0) continue; // 棋盘障碍 // 检查是否被黑皇后占用 bool occupiedByBlack false; for (auto pos : blackPos) { if (pos.first row pos.second col) { occupiedByBlack true; break; } } if (occupiedByBlack) continue; // 检查白皇后自己的列和对角线冲突 int d1 row - col n - 1; int d2 row col; if (!colWhite[col] !diag1White[d1] !diag2White[d2]) { colWhite[col] diag1White[d1] diag2White[d2] true; dfsWhite(row 1); colWhite[col] diag1White[d1] diag2White[d2] false; } } } // 第一阶段放置黑皇后 void dfsBlack(int row) { if (row n) { // 黑皇后放置完毕开始放置白皇后 dfsWhite(0); return; } for (int col 0; col n; col) { if (board[row][col] 0) continue; // 棋盘障碍 int d1 row - col n - 1; int d2 row col; if (!colBlack[col] !diag1Black[d1] !diag2Black[d2]) { // 放置黑皇后 colBlack[col] diag1Black[d1] diag2Black[d2] true; blackPos.push_back({row, col}); dfsBlack(row 1); // 回溯 colBlack[col] diag1Black[d1] diag2Black[d2] false; blackPos.pop_back(); } } } int main() { cin n; board.resize(n, vectorint(n)); for (int i 0; i n; i) { for (int j 0; j n; j) { cin board[i][j]; } } total 0; dfsBlack(0); cout total endl; return 0; }1.2 8皇后·改1.2.1 题目规则同8皇后问题但是棋盘上每格都有一个数字要求八皇后所在格子数字之和最大。一个8*8的棋盘。数据规模和约定棋盘上的数字范围0~99所能得到的最大数字和输入范例1 2 3 4 5 6 7 89 10 11 12 13 14 15 1617 18 19 20 21 22 23 2425 26 27 28 29 30 31 3233 34 35 36 37 38 39 4041 42 43 44 45 46 47 4848 50 51 52 53 54 55 5657 58 59 60 61 62 63 64输出范例2601.2.2 总结本题是在经典八皇后问题的基础上增加了优化目标要求在所有满足八皇后约束条件即任意两个皇后不同行、不同列、不同对角线的布局中找出皇后所在格子数字之和最大的方案。由于棋盘固定为8×8搜索空间有限可以采用深度优先搜索回溯法枚举所有合法布局并记录最大和。算法从第0行开始逐行尝试每一列通过三个布尔数组分别标记列、主对角线和副对角线的占用情况其中主对角线用行减列再加7映射到0~14的索引副对角线直接用行加列映射。在递归过程中每放置一个皇后就将当前格子的数字累加到当前和中当成功放置完所有8行时将当前和与全局最大值比较并更新。搜索结束后输出全局最大值。由于只需要最大和而不需要输出具体布局可以在搜索过程中直接维护当前和不需要存储棋盘状态。该算法能够完整遍历92种八皇后布局并计算每种布局的数字和从而得到最大值。1.2.3 代码#include iostream #include vector #include algorithm using namespace std; int board[8][8]; // 棋盘数字 bool col[8] {false}; // 列占用 bool diag1[15] {false}; // 主对角线占用 (row - col 7) bool diag2[15] {false}; // 副对角线占用 (row col) int maxSum 0; // 最大和 // 深度优先搜索row表示当前要放置皇后的行 void dfs(int row, int currentSum) { if (row 8) { // 已经放置完所有皇后更新最大值 maxSum max(maxSum, currentSum); return; } for (int colIndex 0; colIndex 8; colIndex) { // 检查该列和对角线是否被占用 int d1 row - colIndex 7; // 主对角线索引偏移确保非负 int d2 row colIndex; if (!col[colIndex] !diag1[d1] !diag2[d2]) { // 放置皇后 col[colIndex] true; diag1[d1] true; diag2[d2] true; // 递归下一行累加当前格子的数字 dfs(row 1, currentSum board[row][colIndex]); // 回溯 col[colIndex] false; diag1[d1] false; diag2[d2] false; } } } int main() { // 读取8x8棋盘数字 for (int i 0; i 8; i) { for (int j 0; j 8; j) { cin board[i][j]; } } maxSum 0; dfs(0, 0); cout maxSum endl; return 0; }1.3 棋盘多项式1.3.1 题目八皇后问题是在棋盘上放皇后互相不攻击求方案。变换一下棋子还可以有八车问题八马问题八兵问题八王问题注意别念反。在这道题里棋子换成车同时棋盘也得换确切说是进行一些改造。比如现在有一张n*n的棋盘我们在一些格子上抠几个洞这些洞自然不能放棋子了会漏下去的。另外一个车本来能攻击和它的同行同列。现在你想想在攻击的过程中如果踩到一个洞便会自取灭亡。故车的攻击范围止于洞。此题给你棋盘的规模n以及挖洞情况求放k个车的方案数(k从0到最多可放车数)第一行一个整数n表示棋盘大小接下来n行每行n个用空格隔开的数字0或10的形状表示洞1表示没有洞数据规模和约定n8若干行第i行表示放i个车的方案数输入范例31 0 11 1 11 0 1输出范例71241.3.2 总结本题是带障碍棋盘上的车放置问题要求统计放置0个到最多可放个数的所有方案数。由于车的攻击范围会被洞阻断同一行或列被洞分割成的连续区域成为独立的放置单元。算法首先将棋盘的行和列分别按洞分割成连续段并为每个可放格子记录所属的行段和列段从而构建一个二分图其中行段和列段作为节点可放格子对应连接其行段和列段的边。放置一个车等价于选择一条边且不能有两条边共享同一个行段或列段即求二分图的所有匹配。通过深度优先搜索枚举所有匹配统计每种匹配大小对应的方案数最后按k从0到最大匹配数输出结果。该算法利用n≤8的条件确保搜索可行。1.3.3 代码#include iostream #include vector #include cstring using namespace std; int n; vectorvectorint board; // 1可放0洞 int rowSeg[8][8]; // 每个格子所属的行段编号 int colSeg[8][8]; // 每个格子所属的列段编号 int rowSegCount, colSegCount; vectorint result; // 构建行段和列段 void buildSegments() { // 行段 rowSegCount 0; for (int i 0; i n; i) { int segId -1; for (int j 0; j n; j) { if (board[i][j] 0) { segId -1; // 遇到洞重置段 } else { if (segId -1) { segId rowSegCount; } rowSeg[i][j] segId; } } } // 列段 colSegCount 0; for (int j 0; j n; j) { int segId -1; for (int i 0; i n; i) { if (board[i][j] 0) { segId -1; } else { if (segId -1) { segId colSegCount; } colSeg[i][j] segId; } } } } // 邻接表每个行段对应一系列列段 vectorvectorint adj; bool usedColSeg[64]; // 列段是否被占用 int matchRow[64], matchCol[64]; // 匹配记录这里我们不需要只是用于DFS枚举所有匹配 int matchSize; int maxSeg; void dfsMatch(int rowSegIdx, int start) { if (rowSegIdx rowSegCount) { result[matchSize]; return; } // 不选当前行段 dfsMatch(rowSegIdx 1, 0); // 尝试为当前行段选择一个列段 for (int colSegIdx : adj[rowSegIdx]) { if (!usedColSeg[colSegIdx]) { usedColSeg[colSegIdx] true; matchSize; dfsMatch(rowSegIdx 1, colSegIdx 1); matchSize--; usedColSeg[colSegIdx] false; } } } int main() { cin n; board.resize(n, vectorint(n)); for (int i 0; i n; i) { for (int j 0; j n; j) { cin board[i][j]; } } buildSegments(); // 构建邻接表 adj.resize(rowSegCount); for (int i 0; i n; i) { for (int j 0; j n; j) { if (board[i][j] 1) { int rs rowSeg[i][j]; int cs colSeg[i][j]; adj[rs].push_back(cs); } } } // 去重因为同一行段和列段可能通过多个格子相连但只需要一条边 for (int i 0; i rowSegCount; i) { sort(adj[i].begin(), adj[i].end()); adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end()); } result.resize(min(rowSegCount, colSegCount) 1, 0); memset(usedColSeg, 0, sizeof(usedColSeg)); matchSize 0; dfsMatch(0, 0); // 输出结果从0到最大匹配数 int maxMatch result.size() - 1; while (maxMatch 0 result[maxMatch] 0) maxMatch--; for (int k 0; k maxMatch; k) { cout result[k] endl; } return 0; }二、翻译打卡P1智能手机是从基本的蜂窝电话和掌上电脑演变而来的。掌上电脑personal digital assistant是一种手持设备用作电子预约簿、计算器和记事本。现代智能手机包括类似的一套应用程序但它们还可以访问各种各样的移动应用程序帮助你计算小费、播放你最喜欢的音乐以及用游戏娱乐你。P2智能手机的操作系统与平板电脑的操作系统类似。iPad和iPhone使用iOS操作系统智能手机使用与Windows笔记本电脑类似的用户体验的Windows 10 Mobile操作系统三星平板电脑使用的Android操作系统也用于三星Galaxy和摩托罗拉Droid智能手机。P3数字设备种类繁多许多设备如健身追踪器、相机和手持GPS专门用于特定任务而其他设备则执行更广泛的任务。三、单词打卡