东华复试OJ二刷复盘16
进阶23：设 F(N) 表示正整数 1 到正整数 N 中,数字 1,2 总共出现了多少次。例如 N = 10 时:1, 2, 3, 4, 5, 6, 7, 8, 9, 10 这 10 个数中,数字 1 出现了两次,数字 2 出现了 1 次,所以数字 1, 2 总共出现了 3 次,因此 F (10) = 3。
现在给你正整数 N ,请你求出 F(N) 的值。由于 F(N) 可能很大,你仅需输出 F(N) 除以 20123 的余数。
- 用遍历的形式实现，复杂度过高。
- 标准答案为动态规划
#include <bits/stdc++.h> using namespace std; int ans=0; void Count12(vector<int>&cur){ for(auto it:cur){ if(it == 1 || it==2 )ans++; } } void AddOne(vector<int>&cur){ int jin=0; cur[0]++; for(auto &it:cur){ it+=jin; jin=it/10; it%=10; if(jin==0)return; } } bool IsContinue(vector<int>&cur,string&s1){//是否继续 for(int i=0;i<s1.size();i++){ if(cur[i] != (s1[i] - '0'))return true; } return false; } int main(){ string s1;cin>>s1; reverse(s1.begin(),s1.end()); vector<int> cur(s1.size(),0); cur[0]=1; while(IsContinue(cur,s1)){ Count12(cur); AddOne(cur);//自增 } Count12(cur);//相等时退出循环，再记录一次 cout<<ans<<endl; system("pause"); }进阶24：个锁上面看起来有 N 个数字,它们排成一排,并且每个数字都在 0 到 2 之间。你发现你可以通过锁上的机关来交换相邻两个数字的顺序。这个锁在上面存在某连续四个数字是“2012”的时候会自动打开。现在,你需要计算一下,你至少需要进行多少次交换操作才能打开这把锁?如果无论如何都没有希望打开这把锁,输出 -1。
- 广度优先遍历。除了遍历的情况还需要注意写上不需要遍历和遍历得不到结果的初始边界情况。
#include <bits/stdc++.h> using namespace std; string s; struct node{ string curS; int step=0; }; int ans=0; unordered_set<string> visited; void bfs(queue<node>&q,string&target){ while(!q.empty()){//循环入队出队 node cur = q.front();q.pop(); //边界条件检查 if(cur.curS.find(target) != -1){ ans = cur.step;return; } //否则继续广度遍历 for(int i=0;i<cur.curS.size()-1;i++){ node nextN = cur; swap(nextN.curS[i],nextN.curS[i+1]);//遍历与右侧元素交换 nextN.step++; if(visited.find(nextN.curS) == visited.end()){ visited.insert(nextN.curS); q.push(nextN); } else continue; } } } int main(){ int len;cin>>len>>s; string target = "2012"; if(s.find(target) != -1){ cout<<ans<<endl;return 0; } queue<node> q; node newNode; newNode.curS = s; newNode.step = 0; q.push(newNode); bfs(q,target); if(ans!=0)cout<<ans<<endl; else cout<<-1<<endl; system("pause"); }基础123：大小为N的棋盘游戏包括N个白棋子，N个黑棋子，还有有2N+1个格子的木盒子。这里是3-棋盘游戏的解，包括初始状态，中间状态和目标状态：
WWW BBB
WW WBBB
WWBW BB
WWBWB B
WWB BWB
W BWBWB
WBWBWB
BW WBWB
BWBW WB
BWBWBW
BWBWB W
BWB BWW
B BWBWW
BB WBWW
BBBW WW
BBB WWW
在这个游戏里有两种移动方法是允许的：
1. 你可以把一个棋子移到与它相邻的空格；
2. 你可以把一个棋子跳过一个(仅一个)与它不同色的棋子到达空格。
请编一个程序解大小为N的棋盘游戏(1 <= N <= 12)。要求用最少的移动步数实现。
- 错误1：string cur = q.pop() 出队不会返回队首元素，而是需要front来访问，pop做删除。
- 错误2：parent.find(news) == parent.end()，如果使用parent[ans]来比较，会因为[] 访问会自动创建一个空字符串键值对，所以用find查键，下面回溯也是同理。
#include <bits/stdc++.h> using namespace std; unordered_map<string, string> parent; string target; void InsertParent(string&news,string&ps,queue<string>&q){ if(parent.find(news) == parent.end()){ q.push(news); parent.insert({news,ps}); } } void BFS(queue<string>&q){ while(!q.empty()){ string cur = q.front();q.pop(); //边界 if(cur == target)return; //通过map来回溯步骤 //入队遍历 int ZeroIndex = cur.find(' '); if(ZeroIndex!=0){ string newS = cur; swap(newS[ZeroIndex-1],newS[ZeroIndex]); InsertParent(newS,cur,q); } if(ZeroIndex!=cur.size()-1){ string newS = cur; swap(newS[ZeroIndex+1],newS[ZeroIndex]); InsertParent(newS,cur,q); } if(ZeroIndex>=2){ string newS = cur;//异色 if(newS[ZeroIndex-2] != newS[ZeroIndex-1]){ swap(newS[ZeroIndex],newS[ZeroIndex-2]); InsertParent(newS,cur,q); } } if(ZeroIndex<=cur.size()-3){ string newS = cur;//异色 if(newS[ZeroIndex+2] != newS[ZeroIndex+1]){ swap(newS[ZeroIndex],newS[ZeroIndex+2]); InsertParent(newS,cur,q); } } } } int main(){ int len;cin>>len; string s; for(int i=0;i<2*len+1;i++){ if(i<len){ s.push_back('W'); target.push_back('B'); } else if(i==len){ s.push_back(' '); target.push_back(' '); } else{ s.push_back('B'); target.push_back('W'); } } string start = s; // cout<<target<<endl; // cout<<s<<endl; queue<string> q; q.push(s); BFS(q); vector<int> ansSpace; string ans = target; while(ans != s) { ansSpace.push_back(ans.find(' ')+1); ans = parent[ans]; } //parent[ans]用 [] 访问会自动创建一个空字符串键值对， //导致 parent 多出一个无用条目导致死循环或错误。 reverse(ansSpace.begin(),ansSpace.end()); for(auto it:ansSpace){ cout<<it<<' '; } system("pause"); }Federated learning 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 on servers for 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 or gradient information to a central server. In this way, collaborative learning can be achieved without exposing raw data. Federated learning has attracted increasing attention in fields such as mobile computing, medical data analysis, and financial risk control.
- 联邦学习是一个分布式机器学习方法，它旨在保护用户数据隐私的情况下训练模型。在传统的机器学习方法，用于训练的数据通常是集中在服务器中。然而，在许多现实情况下，数据是敏感且隐私的，这使得直接共享数据是困难的。联邦学习通过在本地设备上训练模型并仅上传模型参数或梯度信息来解决这个问题。通过这个方式，能在不暴露原始数据的情况下实现联合学习。联邦学习已经在一些领域吸引越来越多的关注，例如移动计算，医疗数据分析，金融风险控制。
- Federated learning 联邦学习 preserving 保护/保存 scenarios 场景/情景