3.22 OJ

一、

题目：

8皇后·改

作者: turbo

时间限制: 1s

章节: 深度优先搜索

问题描述

规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。

输入说明

一个8*8的棋盘。

数据规模和约定

棋盘上的数字范围0~99

输出说明

所能得到的最大数字和

#include <bits/stdc++.h> using namespace std; int pos[100][100]; int maxnum=0; int col[100]; int d1[1000]; int d2[1000]; void dfs(int row,int num) { if(row>8) { if(maxnum<num) { maxnum=num; } return ; } for(int j=1;j<=8;j++) { if(col[j]==0&&d1[row+j]==0&&d2[row-j+8]==0) { col[j]=1; d1[row+j]=1; d2[row-j+8]=1; dfs(row+1,num+pos[row][j]); col[j]=0; d1[row+j]=0; d2[row-j+8]=0; } } } int main() { for(int i=1;i<=8;i++) { for(int j=1;j<=8;j++) { cin>>pos[i][j]; } } maxnum=0; dfs(1,0); cout<<maxnum; //总结 上到n皇后同样的思路 }

总结 上到n皇后同样的思路

二、

2n皇后问题

作者: Turbo

时间限制: 1s

章节: 深度优先搜索

问题描述

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。

问总共有多少种放法？

n小于等于8。

说明：同一条对角线是指包括两条主对角线的所有对角线，n=5时的棋盘从左上往右下有9条对角线，从右上往左下也有9条对角线。

比如，棋盘为：

1 1 1 1

1 1 1 1
1 1 1 1
1 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[row+c1] || d2W[row-c1+n]) continue; // 放白 used[row][c1] = 1; colW[c1] = d1W[row+c1] = d2W[row-c1+n] = 1; // 枚举黑皇后位置 for(int c2 = 1; c2 <= n; c2++) { if(pos[row][c2] == 0) continue; if(used[row][c2]) continue; if(colB[c2] || d1B[row+c2] || d2B[row-c2+n]) continue; // 放黑 used[row][c2] = 1; colB[c2] = d1B[row+c2] = d2B[row-c2+n] = 1; dfs(row + 1); // 回溯黑 used[row][c2] = 0; colB[c2] = d1B[row+c2] = d2B[row-c2+n] = 0; } // 回溯白 used[row][c1] = 0; colW[c1] = d1W[row+c1] = d2W[row-c1+n] = 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 左对角线row+low 最后递归结束一定要记得回溯 }

总结：总体思想就是递归 先条件判断是否行都递归完 如果都递归玩 num++之后就是黑白两个匹配 判断条件是pos有没有被占 used有没有被占 然后判断同一列有没有 右对角线row-low 左对角线row+low 最后递归结束一定要记得回溯

三、

芯片测试

作者: Turbo

时间限制: 1s

章节: 深度优先搜索

问题描述

有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。
每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。
给出所有芯片的测试结果，问哪些芯片是好芯片。

输入说明

输入数据第一行为一个整数n，表示芯片个数。
第二行到第n+1行为n*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。

输出说明

按从小到大的顺序输出所有好芯片的编号

#include <bits/stdc++.h> using namespace std; int pos[1000][1000]; int good[1000]; int ans[1000]; // ? 新增 int n; bool check() { for(int i=1;i<=n;i++) { if(good[i]==1) { for(int j=1;j<=n;j++) { if(pos[i][j]!=good[j]) return false; } } } return true; } void dfs(int row) { if(row > n) { int cnt = 0; for(int i=1;i<=n;i++) if(good[i]) cnt++; if(cnt <= n/2) return; // 剪枝 if(check()) { for(int i=1;i<=n;i++) ans[i] = good[i]; } return; } good[row]=1; dfs(row+1); good[row]=0; dfs(row+1); } int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>pos[i][j]; dfs(1); for(int i=1;i<=n;i++) { if(ans[i]==1) cout<<i<<" "; } //总结：从每一行开始 假设该行正确或不正确 当所有行都取了的时候 进行判断是否正确 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.

联邦学习是一种分布式机器学习方法，旨在训练模型的同时保护用户数据隐私。在传统机器学习方法中，数据通常集中在服务器上进行训练。然而，在许多现实场景中，数据具有隐私性和敏感性，难以直接共享。联邦学习通过在各设备本地训练模型，仅将模型参数或梯度信息上传至中央服务器来解决这一问题。通过这种方式，可以在不暴露原始数据的情况下实现协作学习。联邦学习在移动计算、医疗数据分析和金融风控等领域日益受到关注。