3.22 OJ

一、题目8皇后·改作者: turbo时间限制: 1s章节: 深度优先搜索问题描述规则同8皇后问题但是棋盘上每格都有一个数字要求八皇后所在格子数字之和最大。输入说明一个8*8的棋盘。数据规模和约定棋盘上的数字范围0~99输出说明所能得到的最大数字和#include bits/stdc.h using namespace std; int pos[100][100]; int maxnum0; int col[100]; int d1[1000]; int d2[1000]; void dfs(int row,int num) { if(row8) { if(maxnumnum) { maxnumnum; } return ; } for(int j1;j8;j) { if(col[j]0d1[rowj]0d2[row-j8]0) { col[j]1; d1[rowj]1; d2[row-j8]1; dfs(row1,numpos[row][j]); col[j]0; d1[rowj]0; d2[row-j8]0; } } } int main() { for(int i1;i8;i) { for(int j1;j8;j) { cinpos[i][j]; } } maxnum0; dfs(1,0); coutmaxnum; //总结 上到n皇后同样的思路 }总结 上到n皇后同样的思路二、2n皇后问题作者: Turbo时间限制: 1s章节: 深度优先搜索问题描述给定一个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表示对应的位置不可以放皇后。输出说明输出一个整数表示总共有多少种放法。#include bits/stdc.h using namespace std; int n; int pos[10][10]; int ans 0; // 白皇后 int colW[10], d1W[20], d2W[20]; // 黑皇后 int colB[10], d1B[20], d2B[20]; // used表示这个位置是否已经被占白或黑 int used[10][10]; void dfs(int row) { if(row n) { ans; return; } // 枚举白皇后位置 for(int c1 1; c1 n; c1) { if(pos[row][c1] 0) continue; if(used[row][c1]) continue; if(colW[c1] || d1W[rowc1] || d2W[row-c1n]) continue; // 放白 used[row][c1] 1; colW[c1] d1W[rowc1] d2W[row-c1n] 1; // 枚举黑皇后位置 for(int c2 1; c2 n; c2) { if(pos[row][c2] 0) continue; if(used[row][c2]) continue; if(colB[c2] || d1B[rowc2] || d2B[row-c2n]) continue; // 放黑 used[row][c2] 1; colB[c2] d1B[rowc2] d2B[row-c2n] 1; dfs(row 1); // 回溯黑 used[row][c2] 0; colB[c2] d1B[rowc2] d2B[row-c2n] 0; } // 回溯白 used[row][c1] 0; colW[c1] d1W[rowc1] d2W[row-c1n] 0; } } int main() { cin n; for(int i 1; i n; i) for(int j 1; j n; j) cin pos[i][j]; dfs(1); cout ans endl; //总结总体思想就是递归 先条件判断是否行都递归完 如果都递归玩 num之后就是黑白两个匹配 判断条件是pos有没有被占 used有没有被占 然后判断同一列有没有 右对角线row-low 左对角线rowlow 最后递归结束一定要记得回溯 }总结总体思想就是递归 先条件判断是否行都递归完 如果都递归玩 num之后就是黑白两个匹配 判断条件是pos有没有被占 used有没有被占 然后判断同一列有没有 右对角线row-low 左对角线rowlow 最后递归结束一定要记得回溯三、芯片测试作者: Turbo时间限制: 1s章节: 深度优先搜索问题描述有n2≤n≤20块芯片有好有坏已知好芯片比坏芯片多。每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时会随机给出好或是坏的测试结果即此结果与被测试芯片实际的好坏无关。给出所有芯片的测试结果问哪些芯片是好芯片。输入说明输入数据第一行为一个整数n表示芯片个数。第二行到第n1行为n*n的一张表每行n个数据。表中的每个数据为0或1在这n行中的第i行第j列1≤i, j≤n的数据表示用第i块芯片测试第j块芯片时得到的测试结果1表示好0表示坏ij时一律为1并不表示该芯片对本身的测试结果。芯片不能对本身进行测试。输出说明按从小到大的顺序输出所有好芯片的编号#include bits/stdc.h using namespace std; int pos[1000][1000]; int good[1000]; int ans[1000]; // ? 新增 int n; bool check() { for(int i1;in;i) { if(good[i]1) { for(int j1;jn;j) { if(pos[i][j]!good[j]) return false; } } } return true; } void dfs(int row) { if(row n) { int cnt 0; for(int i1;in;i) if(good[i]) cnt; if(cnt n/2) return; // 剪枝 if(check()) { for(int i1;in;i) ans[i] good[i]; } return; } good[row]1; dfs(row1); good[row]0; dfs(row1); } int main() { cinn; for(int i1;in;i) for(int j1;jn;j) cinpos[i][j]; dfs(1); for(int i1;in;i) { if(ans[i]1) couti ; } //总结从每一行开始 假设该行正确或不正确 当所有行都取了的时候 进行判断是否正确 return 0; }总结从每一行开始 假设该行正确或不正确 当所有行都取了的时候 进行判断是否正确四、翻译Federatedlearning is a distributed machine learning approach that aims to train models while preserving user data privacy. In traditional machine learning methods, data is usually centralized onserversfor training. However, in many real-world scenarios, data is private and sensitive, making it difficult to share directly. Federated learning addresses this problem by training models locally on devices and only uploading model parameters orgradientinformation to a central server. In this way, collaborative learning can be achieved without exposingrawdata. Federated learning has attracted increasing attention in fields such as mobile computing, medical data analysis, and financial risk control.联邦学习是一种分布式机器学习方法旨在训练模型的同时保护用户数据隐私。在传统机器学习方法中数据通常集中在服务器上进行训练。然而在许多现实场景中数据具有隐私性和敏感性难以直接共享。联邦学习通过在各设备本地训练模型仅将模型参数或梯度信息上传至中央服务器来解决这一问题。通过这种方式可以在不暴露原始数据的情况下实现协作学习。联邦学习在移动计算、医疗数据分析和金融风控等领域日益受到关注。