-
数据结构与算法训练：第二十三弹
1. 知识点总结
耗时：2h28min
得分：99/100
知识点：字符串、最大公因数、插入排序和归并排序、多叉树的层次遍历、BFS连通图体积求解
题目 难度 知识点 1088 Rational Arithmetic 🎯 字符串、最大公因数 1089 Insert or Merge 🎯🎯|✨ 插入排序和归并排序 1090 Highest Price in Supply Chain 🎯 多叉树的构建和层次遍历 1091 Acute Stroke 🎯 BFS 2. 分题题解
2.1 1088 Rational Arithmetic
不是很难，虽然代码量看着多~
主要是分数的运算，注意输出格式即可，需要留意一下除零的情况~
- 首先
getVal根据字符串获取分数的值以及正负情况 - 接着
Add和Diff这些主要是按照分数运算规则求解答案 - 对分数结构体Node输出时调用
Print注意输出格式：最简分数形式
#includeusing namespace std; typedef long long ll; string str1,str2; struct Node{ bool neg=false; ll up; ll down; }; Node num1,num2; //求最大公因数 ll gcd(ll a,ll b){ if(a<b)swap(a,b); ll temp; while(b){ temp=b; b=a%b; a=temp; } return a; } void getValue(string str,Node&num){ if(str[0]=='-'){ num.neg=true; str=str.substr(1,str.length()); } sscanf(str.c_str(),"%lld/%lld",&num.up,&num.down); ll temp=gcd(num.up,num.down); num.up/=temp; num.down/=temp; if(num.neg){ num.up=-num.up; } } void Print(Node num){ if(num.neg){ printf("(-"); } if(num.up==0){ printf("0"); }else{ ll out=num.up/num.down; ll res=num.up-out*num.down; if(out){ printf("%lld",abs(out)); } if(res){ if(out){ printf(" "); } printf("%lld/%lld",abs(res),abs(num.down)); } } if(num.neg){ printf(")"); } } void Add(Node num1,Node num2){ Node ans; // a/b + c/d= (a*d+b*c)/(b*d) ans.up=(num1.up*num2.down+num1.down*num2.up); ans.down=(num1.down*num2.down); if(ans.up<0)ans.neg=true; ll temp=gcd(abs(ans.up),ans.down); ans.up/=temp; ans.down/=temp; //输出答案 Print(num1); printf(" + "); Print(num2); printf(" = "); Print(ans); printf("\n"); } void Diff(Node num1,Node num2){ Node ans; //a/b - c/d= (a*d-b*c)/(b*d) ans.up=(num1.up*num2.down-num1.down*num2.up); ans.down=(num1.down*num2.down); if(ans.up<0)ans.neg=true; ll temp=gcd(abs(ans.up),ans.down); ans.up/=temp; ans.down/=temp; //输出答案 Print(num1); printf(" - "); Print(num2); printf(" = "); Print(ans); printf("\n"); } void Pro(Node num1,Node num2){ Node ans; //a/b * c/d= a*c/(b*d) ans.up=(num1.up*num2.up); ans.down=(num1.down*num2.down); if(ans.up<0)ans.neg=true; ll temp=gcd(abs(ans.up),ans.down); ans.up/=temp; ans.down/=temp; //输出答案 Print(num1); printf(" * "); Print(num2); printf(" = "); Print(ans); printf("\n"); } void Quo(Node num1,Node num2){ Node ans; if(num2.up==0){ Print(num1); printf(" / "); Print(num2); printf(" = "); printf("Inf"); return; } //a/b / c/d= a*d/(b*c) ans.up=(num1.up*num2.down); ans.down=(num1.down*num2.up); if(num1.neg&&!num2.neg||!num1.neg&&num2.neg){ ans.neg=true; } ll temp=gcd(abs(ans.up),ans.down); ans.up/=temp; ans.down/=temp; //输出答案 Print(num1); printf(" / "); Print(num2); printf(" = "); Print(ans); } int main(){ cin>>str1>>str2; getValue(str1,num1); getValue(str2,num2); Add(num1,num2); Diff(num1,num2); Pro(num1,num2); Quo(num1,num2); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
2.2 1089 Insert or Merge
主要考察插入排序和归并排序的具体实现步骤
模拟的时候卡在了归并排序上，最后第二个测试点被扣1分
24分代码：
#includeusing namespace std; int N; vector<int>v0,v1; vector<int>temp; bool insertSort(){ temp=v0; bool flag=false; for(int i=1;i<N;i++){ if(temp==v1){ flag=true; } //一次迭代 int pos=i; int value=temp[i]; while(pos){ temp[pos]=temp[pos-1]; if(temp[pos]<value){ break; } pos--; } temp[pos]=value; //一次迭代 if(flag){ break; } } return flag; } bool mergeSort(){ bool flag=false; temp=v0; int block=2; while(block<N){ if(temp==v1){ flag=true; } for(int i=0;i<N;i+=block){ if(i+block<=N){ sort(temp.begin()+i,temp.begin()+i+block); }else{ sort(temp.begin()+i,temp.end()); } } if(flag&&temp!=v1){ break; } block*=2; } return flag; } int main(){ scanf("%d",&N); v0.resize(N); v1.resize(N); for(int i=0;i<N;i++){ scanf("%d",&v0[i]); } for(int i=0;i<N;i++){ scanf("%d",&v1[i]); } if(mergeSort()){ printf("Merge Sort\n"); }else{ insertSort(); printf("Insertion Sort\n"); } for(int i=0;i<N;i++){ if(i){ printf(" "); } printf("%d",temp[i]); } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
看了柳神的代码依然没有找到自己的merge哪里错了，但是测试后发现好像index2测试点既是insertSort又是mergeSort，心态炸裂,重新考虑了一下可能是插入排序从第二个下标点开始，也就是说如果v1==v0的时候，默认是mergeSort，顺利AC~
#includeusing namespace std; int N; vector<int>v0,v1; vector<int>temp; //插入排序 bool insertSort(){ temp=v0; bool flag=false; for(int i=1;i<N;i++){ if(i!=1&&temp==v1){ flag=true; } //一次迭代 int pos=i; int value=temp[i]; while(pos&&temp[pos-1]>value){ temp[pos]=temp[pos-1]; pos--; } temp[pos]=value; //一次迭代 if(flag){ break; } } return flag; } bool mergeSort(){ bool flag=false; temp=v0; int block=2; while(block<=N){ if(temp==v1){ flag=true; } for(int i=0;i<N;i+=block){ if(i+block<=N){ sort(temp.begin()+i,temp.begin()+i+block); }else{ sort(temp.begin()+i,temp.end()); } } if(flag){ break; } block*=2; } return flag; } int main(){ scanf("%d",&N); v0.resize(N); v1.resize(N); for(int i=0;i<N;i++){ scanf("%d",&v0[i]); } for(int i=0;i<N;i++){ scanf("%d",&v1[i]); } if(insertSort()){ printf("Insertion Sort\n"); }else{ mergeSort(); printf("Merge Sort\n"); } for(int i=0;i<N;i++){ if(i){ printf(" "); } printf("%d",temp[i]); } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
总之排序之后需要专门整理下知识点啦~
2.3 1090 Highest Price in Supply Chain
主要是考察静态多叉树的构建和层次遍历，这里将所有节点的索引都进行了
+1处理方便利用vector存储遍历.最后输出注意从根节点所在层向下一个节点的时候不需要*(1+r/100)#includeusing namespace std; typedef long long ll; int N,tmp,root=0; double p,r; struct Node{ vector<int>childs; int level=0; }; vector<Node>nodes; vector<int>level; int max_level=0; void levelTravel(int root){ queue<int>q; q.push(root); int top; int level_cnt=0; while(!q.empty()){ top=q.front(); q.pop(); level_cnt=nodes[top].level; if(level_cnt>max_level){ max_level=level_cnt; } //printf("level %d:%d\n",level_cnt,top-1); level[level_cnt]++; for(int i=0;i<nodes[top].childs.size();i++){ int id=nodes[top].childs[i]; nodes[id].level=level_cnt+1; q.push(id); } } } int main(){ scanf("%d%lf%lf",&N,&p,&r); nodes.resize(N+1);//0-N level.resize(N+1,0); for(int i=0;i<N;i++){ scanf("%d",&tmp); nodes[tmp+1].childs.push_back(i+1); } levelTravel(root); for(int i=0;i<max_level-1;i++){ p*=(1+r/100); } printf("%.2f %d",p,level[max_level]); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
2.4 1091 Acute Stroke
题目类似于二位数组找连通图，连通图面积大于一定阈值记录到
cnt中，这里扩展到了三维的情况，值得注意的是，dfs会出现段错误，推荐使用BFS#includeusing namespace std; int N,M,L,T; int tmp,cnt=0; vector<vector<vector<bool> > >brain; vector<vector<vector<bool> > >vis; int di[]={0,0,0,0,1,-1}; int dx[]={0,0,1,-1,0,0}; int dy[]={1,-1,0,0,0,0}; int volume; void dfs(int i,int x,int y){ volume++; vis[i][x][y]=true; for(int v=0;v<6;v++){ if(i+di[v]<0||i+di[v]>=L)continue; if(x+dx[v]<0||x+dx[v]>=N)continue; if(y+dy[v]<0||y+dy[v]>=M)continue; if(!vis[i+di[v]][x+dx[v]][y+dy[v]]&&brain[i+di[v]][x+dx[v]][y+dy[v]]){ dfs(i+di[v],x+dx[v],y+dy[v]); } } } void bfs(int i,int x,int y){ queue<int>qi,qx,qy; qi.push(i); qx.push(x); qy.push(y); vis[i][x][y]=true; while(!qi.empty()){ i=qi.front();qi.pop(); x=qx.front();qx.pop(); y=qy.front();qy.pop(); volume++; for(int v=0;v<6;v++){ if(i+di[v]<0||i+di[v]>=L)continue; if(x+dx[v]<0||x+dx[v]>=N)continue; if(y+dy[v]<0||y+dy[v]>=M)continue; if(!vis[i+di[v]][x+dx[v]][y+dy[v]]&&brain[i+di[v]][x+dx[v]][y+dy[v]]){ qi.push(i+di[v]); qx.push(x+dx[v]); qy.push(y+dy[v]); vis[i+di[v]][x+dx[v]][y+dy[v]]=true; } } } } int main(){ scanf("%d%d%d%d",&N,&M,&L,&T); brain.resize(L); vis.resize(L); for(int i=0;i<L;i++){ brain[i].resize(N); vis[i].resize(N); for(int j=0;j<N;j++){ brain[i][j].resize(M); fill(brain[i][j].begin(),brain[i][j].end(),false); vis[i][j].resize(M); fill(vis[i][j].begin(),vis[i][j].end(),false); } for(int x=0;x<N;x++){ for(int y=0;y<M;y++){ scanf("%d",&tmp); if(tmp){ brain[i][x][y]=true; } } } } for(int i=0;i<L;i++){ for(int x=0;x<N;x++){ for(int y=0;y<M;y++){ if(!vis[i][x][y]&&brain[i][x][y]){ volume=0; //dfs(i,x,y);会出现段错误，25分 bfs(i,x,y); if(volume>=T){ cnt+=volume; } } } } } printf("%d",cnt); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
3. 参考资料
- 首先
-
相关阅读:
Java中几个特殊的运算符
第 2 章 线性表 （线性表的静态单链表存储结构（一个数组可生成若干静态链表）实现）
muduo网络库编程
Kafka快速实战以及基本原理详解
Pickle反序列化学习
MySQL 通过 Next-Key Locking 技术（行锁+间隙锁）避免幻读问题
一款非常专业的音乐创作编辑软件Studio One 6.6.1中文破解版
nginx部署vue项目（包括一个nginx部署多个vue项目）
xray的使用
文件上传，你还存储在应用服务器?
- 原文地址：https://blog.csdn.net/qq_45751990/article/details/126438283
